Can you please share your code? I thought of the same thing but couldn’t find any nice implementation of the same. Finally I solved the problem using trie. But I feel that BST would be the best solution to this problem.
Thanks
Just a doubt, Why do we need to find the smallest window which has all the odd frequency numbers, the question asks about finding the smallest difference between first and last removed numbers, shouldnt we try to find the smallest window having any two odd frequency numbers so that they can be the first and the last.
Ex. 223774775
your code will give 6 as it is difference between first 3 and last 5
but shouldnt the answer be 3, i.e. the difference between 3 and 4
like the first index be removed is 2 and then 8 and then 5 and so the difference between first and last indes removed is 5-2 = 3.
please tell me if i have misinterpreted the question.
First = leftmost, Last = Rightmost
holy shit !!! I misinterpreted it by miles 
Thanks for your help
yeah i solved two barely ;_;
I thought so too but I gave it a shot with normal BST and it worked… The test cases were such that it didn’t make it skewed, but yeah if I had gotten TLE I probably would’ve converted it to self balanced.
1 Like
Don’t have the code with me but basically I used X for ordering each node and stored another property on each node that stores the sum of Y values for the subtree rooted at that node
Wow ! Would you litterally code up a self balancing bst ?? ( I mean implementing Red-Black tree is quite tough ! ).
Haha, I had a RB Tree implementation locally that I would have modified for the question.
1 Like
Can someone provide me contest/problem link?
Ohh, no I have also done the same thing…that’s why I have passed only 4 test cases. I have wasted my so much time to debug this…
I didn’t realize that the first removal must be leftmost and last must be rightmost.