In problem C of yesterday’s round, i’ve tried to optimize the soln as much as i can, and still i’m getting a TLE in test case 8. Can you please help me in resolving this issue!?
My approach :
I use a TreeMap, and for every step, i use max = map.getFirst() to get the maximum element. then i search whether (sum - max) is present in the map or not, if it is present then we go further, otherwise we’ll return.
Similar solutions, in C++, are getting accepted. ( they use multiset) however, i’m having trouble with this. Please help!!!
I did C in C++ using a multimap and I got to say, I feel you. This sucks. I had similar issues with java before (I learned coding in java) and it is one of the reasons I switched to C++.
I didn’t look at your code in detail. In my experience, many of the build-in data structures in java suck hard. I think they are just super slow to build and in this task, you have to rebuild them often. - At least that is what I did. Try out all possible positions that pair up with the maximum value …
I bet you can be a lot faster if you just build the structure once and maintain a counter of how many copies of each number are available. In this way, you only have to change the counters and the tree does not require any changes.
i’ve done exactly that… i’ve used a map in order to store elements and their frequencies ( counters, like you said). However, in order to get the max element in O(1) time, i have to delete elements from the map when their frequency becomes 0.