Very good explanation, but please if i may ask why do we have to increase either the upper/lower when our sum is 0? like after appending the three elements when the sum is zero
O(n log(n)) + O(n^2) = O(n^2) Even if the sorting function was O(n^2), you'd still get that the solution would have an asymptotic runtime complexity of O(n^2)
At 27:40, I don't think that assumption is correct. With the first -1, you have a triplet of -1, -1, 2 but on the second -1, you don't have this option
One question, why there should be a condition of ' if i > 0'? I know when we traversal nums from 0, so that the i cannot be negative, only can be positive and 0. why cannot it be ' if i != 0'? Thanks
In the first iteration, if i = 0, we'll be checking if nums[0] < nums[-1]. nums[-1] is not defined because indexes for lists can't be negative. To avoid that, we only check that condition if i > 0 which basically means i >= 1 here I think "if i != 0" also works fine
I am not am expert... But I have a stupid thought here. Shall we check two numbers through inner loop and add the same. When it is subtracted with 0, we will get a remainder as third number. We can search that number in the given list. If there, then that is one triplet... Similarly check for others
I believe something like that could work, but you'd have to avoid searching the entire list for the remainders. You'd probably end up having to sort the numbers and doing something similar to the solution shown here to get an n^2 solution.
![[🔴LIVE] งานประกาศรางวัล MAYA TV AWARDS 2024 : มายามหาชน](http://i.ytimg.com/vi/nwmWYXXVwBY/mqdefault.jpg)
thank you
Very good explanation, but please if i may ask why do we have to increase either the upper/lower when our sum is 0? like after appending the three elements when the sum is zero
Because there could be more possibilities to check for, can't escape that iteration of the loop just yet
well explained.
Couldn't you skip some of the uppers as well? Won't some of your decrements be the same?
That's what I was thinking, it seems possible
If we have nums= [-3,0,1,2] after sorting, we do have triplets(-3,1,2) that sum to 0. But due to the break condition this test case will fail, right?
It'll only fail when it gets to the 1, anything over 0 it automatically breaks. The -3 and 0 iteration will follow through fully
0What about the Time Complexity when you are doing the sort ?
O(n log(n)) + O(n^2) = O(n^2)
Even if the sorting function was O(n^2), you'd still get that the solution would have an asymptotic runtime complexity of O(n^2)
At 27:40, I don't think that assumption is correct. With the first -1, you have a triplet of -1, -1, 2 but on the second -1, you don't have this option
But the first -1 already checked all the possibilities that the next -1 could have.
One question, why there should be a condition of ' if i > 0'? I know when we traversal nums from 0, so that the i cannot be negative, only can be positive and 0. why cannot it be ' if i != 0'? Thanks
In the first iteration, if i = 0, we'll be checking if nums[0] < nums[-1]. nums[-1] is not defined because indexes for lists can't be negative. To avoid that, we only check that condition if i > 0 which basically means i >= 1 here
I think "if i != 0" also works fine
I am not am expert... But I have a stupid thought here. Shall we check two numbers through inner loop and add the same. When it is subtracted with 0, we will get a remainder as third number. We can search that number in the given list. If there, then that is one triplet... Similarly check for others
I believe something like that could work, but you'd have to avoid searching the entire list for the remainders. You'd probably end up having to sort the numbers and doing something similar to the solution shown here to get an n^2 solution.