educative.io

Educative

Why do we increment and decrement right and left right after finding a match? What if left and right are right next to each other? Wouldn't right become less than left, and left become more than right?

What the title said

Hello @Kash_C,
Yes, we are incrementing and decrementing the left and right after a match because we want to find all possible triplets, not just one. We increment/decrement to skip same element to avoid duplicate triplets.
The main reason is: X + Y + Z = target.

arr = {-5, -2, -1, 2, 3 } We select Z one by one, for eg. Z = -5 and then find all possible pairs X + Y. In the next loop we select -2 and all possible pairs X + Y. At this point if you let one of X or Y be -5, you will stumble upon the same pair you already got when Z was -5, creating a duplicate. So, only let X Y be elements after i+1.

Also, I was wondering why both left++ and right++ when we find the pairSum==targetSum. The reason being: X(left) + Y(right) formed targetSum, now there is no other number with X that can form targetSum. Similarly, there is no number with Y that can form targetSum, So, we move on on both sides.
I hope this will answer your question.

1 Like