The salt is inserting into the middle of the array. Inserting into the middle of the array is O(n) because you have to copy it. So the result complexity is still O(n^2)
Yea it’s not possible to optimal solve it without a sorted array data structure that can maintain the sorted order and also insert in O(1) time. Other languages have it but Python unfortunately doesn’t out of the box
@@crackfaang Thanks a lot ! for this c++ code it is giving TLE for 3 test cases but that's okay public: vector countSmaller(vector& nums) { multiset sorted; vector ans(nums.size()); for (int i = nums.size() - 1; i >= 0; i--) { int curr = nums[i]; auto it = sorted.lower_bound(curr); ans[i] = distance(sorted.begin(), it); sorted.insert(it, curr); } return ans; } };
the only issue here is that we are using sorted containers which is not a part of default python package. OA might not accept this. Also its not available in languages like C++ where these are just AVL ..so the indexing takes O(n) time. Here its a chunk like data structure which not only inserts, deletes in log n time but indexes in O(1) time... interviewer might ask you to implement this and you get caught in rabbithole🤣..Better to use merge sort here
Bro, I just want to say thank you for the help, I watch your videos every day. I got demotivated since most companies were laying off or hiring freeze, but your consistent uploads kept me on my feet. My first FAANG paycheque is coming your way
Thanks for the kind words my friend. I know it’s tough given the current job market but this is actually the best time to Leetcode because there’s really zero time pressure on you and you can take your time to learn everything properly without worrying about a deadline. Make the most of the time since most people will just stop entirely. When hiring resumes you’ll be ready to go while everyone else starting up again
![[SOLVED!] Lowet Common Ancestor of a Binary Tree III - LeetCode 1650 - Java](http://i.ytimg.com/vi/PXIFRk4wWzc/mqdefault.jpg)
![[SOLVED!] Lowet Common Ancestor of a Binary Tree III - LeetCode 1650 - Java](/img/tr.png)
Smartest and cleanest solution I have seen for this question. Amazing job!
The salt is inserting into the middle of the array. Inserting into the middle of the array is O(n) because you have to copy it. So the result complexity is still O(n^2)
Yea it’s not possible to optimal solve it without a sorted array data structure that can maintain the sorted order and also insert in O(1) time. Other languages have it but Python unfortunately doesn’t out of the box
@@crackfaang
Thanks a lot !
for this c++ code it is giving TLE for 3 test cases but that's okay
public:
vector countSmaller(vector& nums) {
multiset sorted;
vector ans(nums.size());
for (int i = nums.size() - 1; i >= 0; i--) {
int curr = nums[i];
auto it = sorted.lower_bound(curr);
ans[i] = distance(sorted.begin(), it);
sorted.insert(it, curr);
}
return ans;
}
};
it's so simple as you explained it! Clean and ah so smart, thank you a lot!
We can avoid reversing operation & directly assign to result[r] = index;
such a fantastic video!
Wow.Shortest solution
the only issue here is that we are using sorted containers which is not a part of default python package. OA might not accept this. Also its not available in languages like C++ where these are just AVL ..so the indexing takes O(n) time. Here its a chunk like data structure which not only inserts, deletes in log n time but indexes in O(1) time... interviewer might ask you to implement this and you get caught in rabbithole🤣..Better to use merge sort here
Hiii Now hey You i have subscribes and I am loving you content and your little intimidation too don't so stop now!
Bro, I just want to say thank you for the help, I watch your videos every day. I got demotivated since most companies were laying off or hiring freeze, but your consistent uploads kept me on my feet. My first FAANG paycheque is coming your way
Thanks for the kind words my friend. I know it’s tough given the current job market but this is actually the best time to Leetcode because there’s really zero time pressure on you and you can take your time to learn everything properly without worrying about a deadline. Make the most of the time since most people will just stop entirely. When hiring resumes you’ll be ready to go while everyone else starting up again
loved the haha at 1:05 :XD
Thank you!
10K+ Subscribers by next year Feb💯
That’s the goal. I have some big plans for the channel next year… hoping for 100k by the end of next December!
bro code!
I sound nothing like that 😂