This is not a normal Medium Problem, it is Medium Hard (not in terms of implementation but a why on every step makes it Hard), skip dry run (that is longest section) ❤ Do connect on Twitter☺ : x.com/aryan_mittal007
Your effort helps us a lot ..... Explained it awesomely......i guess you also did it with greedy first ...coz this was the first test case where greedy failed for me 😄
Bhaiya, I tried this approach which was to take the abs difference of all pairs and add it to a max priority queue and according to which diff has greater frequency that queue would handle it and we would check for all the diff in the increasing order of their frequencies so that way lesser number of operations would be required. Now considering n/2 differences even in the worst case would make it nearly half the size of array that is the worst case when all pairs have different frequency and then checking minimum operations for them would make it nearly O(10^5 * 10^3) would be 10^8 in worst case and generally that is allowed but my solution is still giving TLE. Can you explain where I went wrong? class Solution { private: struct myComp { constexpr bool operator()( pair const& a, pair const& b) const noexcept { return a.second < b.second; } }; public: int minChanges(vector& nums, int k) { unordered_map freq; priority_queue pq; int n=nums.size(); int i=0,j=n-1; while(i
I solved it in Greedy way Find the difference with max freq Find the number of replacement moves to make the above difference return min(ans, (n-2)/2); This is an accepted solution in O(N)
bro why are you not checking ans for all values from 0 to k .. you are just checking difference that are already formed by pairs... because my difference value can be between 0 to k..
This is not a normal Medium Problem, it is Medium Hard (not in terms of implementation but a why on every step makes it Hard), skip dry run (that is longest section) ❤
Do connect on Twitter☺ : x.com/aryan_mittal007
Thank you I learned so much from this video!
I did it in contest with same approach
wooaaahh awesome!!
i thought about a lot of ways to get greedy approach to work during the contest.. and you tackled all of them in this video!
same here bro😢
Your explanations are getting so better!
Excellent problem, it's clear now after explaining :)
Finding this too hard 😢😢
Your effort helps us a lot ..... Explained it awesomely......i guess you also did it with greedy first ...coz this was the first test case where greedy failed for me 😄
Crazy question
Aryan Bhai >>>>
nicely explained bro, but i dont think this should be a medium qs, the prefix intuition was pretty hard man.
Bhaiya, I tried this approach which was to take the abs difference of all pairs and add it to a max priority queue and according to which diff has greater frequency that queue would handle it and we would check for all the diff in the increasing order of their frequencies so that way lesser number of operations would be required. Now considering n/2 differences even in the worst case would make it nearly half the size of array that is the worst case when all pairs have different frequency and then checking minimum operations for them would make it nearly O(10^5 * 10^3) would be 10^8 in worst case and generally that is allowed but my solution is still giving TLE. Can you explain where I went wrong?
class Solution {
private:
struct myComp {
constexpr bool operator()(
pair const& a,
pair const& b)
const noexcept
{
return a.second < b.second;
}
};
public:
int minChanges(vector& nums, int k) {
unordered_map freq;
priority_queue pq;
int n=nums.size();
int i=0,j=n-1;
while(i
Well explained 👏
What would be the difficulty of this question on codeforces
great explanation bro
thanks mittal saab
gawd lvl explanation 🔥🔥
Great Explanation!!!!!
Good one
🙇
Bheek Pro Max the title of first timeline 🤣
I solved it in Greedy way
Find the difference with max freq
Find the number of replacement moves to make the above difference
return min(ans, (n-2)/2);
This is an accepted solution in O(N)
It might have worked in contest but idts that it is the correct approach
Can u explained how is it working for this test case :
[1,1,1,1,0,0,0,5,4,3,19,17,16,15,15,15,19,19,19,19] ?
what's the n-2/2
bro why are you not checking ans for all values from 0 to k .. you are just checking difference that are already formed by pairs...
because my difference value can be between 0 to k..
Liked
bro can you tell if this problem was on codeforces what would be its approximate rating like 1600?
1400 max to max
Hold on kr kr ke kuch smjh nahi aya
Finally
Laut awo Aryan Bhai....