educative.io

Educative

Count += right - left; would'nt it cause duplicates?

After
count += right - left;
the code does left++
My question is since we have already counted all numbers between left to right, why are we doing left++ now?
would’nt it re-count the numbers appearing between right-left that we have already counted?


Course: Grokking the Coding Interview: Patterns for Coding Questions - Learn Interactively
Lesson: Triplets with Smaller Sum (medium) - Grokking the Coding Interview: Patterns for Coding Questions

1 Like

Hi @bee1,
left++ is used to increase the index of the arr array. It will not produce duplication.

I thought this as well and had to work through it for a while. If we have the sorted array [1, 2, 3, 4, 5] and a target of 15, we start with 1 as the first variable, 2 as the left, 5 as right. 1 + 2 + 5 < 15 so we include it, and we would also include 1 + 2 + 3 or 4 so that’s why we increment count by right-left.

we avoid duplicates because after we include all of those combos, we move the left variable so that now becomes 3 instead of 2. So the next triplet we consider is 1 + 3 + 5 and is not duplicated. Since this is less than the target we again increment count by right-left because 1 + 3 + 5 and 1 + 3 + 4 would all be less than the target, and aren’t duplicated since we moved left


Course: Grokking the Coding Interview: Patterns for Coding Questions - Learn Interactively
Lesson: Triplets with Smaller Sum (medium) - Grokking the Coding Interview: Patterns for Coding Questions