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
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
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..
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 😄
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)
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
Finding this too hard 😢😢
I did it in contest with same approach
We can use segment trees as well. The resason we can use prefix sum here is because the queries are offline.
Thank you I learned so much from this video!
this is a very good explanation
Crazy question
Laut awo Aryan Bhai....
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
nicely explained bro, but i dont think this should be a medium qs, the prefix intuition was pretty hard man.
What would be the difficulty of this question on codeforces
Hold on kr kr ke kuch smjh nahi aya
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..
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😢
Aryan Bhai >>>>
Your explanations are getting so better!
Excellent problem, it's clear now after explaining :)
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 😄
Liked
🙇
bro can you tell if this problem was on codeforces what would be its approximate rating like 1600?
1400 max to max
gawd lvl explanation 🔥🔥
great explanation bro
thanks mittal saab
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
Well explained 👏
Great Explanation!!!!!
Good one
Finally