why are we doing sorting whats the need ?
Why are we doing sorting whats the need?
The brute force approach is O(n^3). Where for each i in array you find j and k such that arr[i]+arr[j]+arr[k]=target. This requires 3 loop so complexity is O(n^2).
Optimized approach is to first sort the array(similar to target sum pair). Then fix each element and find the remaining 2 pairs such that total sum is equal to target.
We sort the array so that we don’t have to verify the index of each number to avoid additional counting of pairs. ie. once you fix i, you do not need to search for pairs at index less than i.
It must be explained in the video. Watch it again, dry run and try to visualize
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.