educative.io

Simple Explanation for program line : count += right - left;

Courses
,
#1

Hi Design Guru,

Could you give me simple explanation to understand why we are taking differences instead of just incrementing the counter.

count += right - left;

8 Likes
#2

curious about this as well

#3

Not sure if this helps or not (i’m still trying to figure it out myself haha) but:
I think that since we’ve sorted the list we know that if the current sum is less than the target, then all the sums in between should be too.

Ex) list is [-1,1,2,3,4] target = 6
When the left pointer is 1 and right pointer is 4, the sum (-1 + 1 + 4) is less than the target. So we know that (-1 + 1 + 2) and (-1 + 1 + 3) would also be smaller than the target.

6 Likes
#5

Was also confused. Took me a while.

Let’s say we have this.

target: 5

ptrs:  i  l        r
nums: -1, 1, 2, 3, 4
idx:   0  1  2  3  4

If we move the right pointer leftwards while left < right, then we find 3
other combinations that are less than 5.

-1 + 1 + 4 = 4
-1 + 1 + 3 = 3
-1 + 1 + 2 = 2

Turns out you can math your way to that answer too: right=4 - left=1 == 3.

The important detail here is that the numbers are sorted. So the intuition
should be

  • You have small number plus a big number that equals X.
  • If you make the big number smaller, the new number is gonna be less than X.
2 Likes
#6

Thanks for this concise explanation Kamira! Cheers!

#8

you can translate count += right - left to

    int tmp = right; 
    while (left < tmp && arr[left] + arr[tmp] < target) {
      count += 1;
      tmp--;
    }

This makes intuitively makes more sense as we can are counting each triplet in which the sum is < the target. Simply doing count += right - left isn’t clear to someone that is learning. Although, after realizing what is going on the right -left arithmetic makes sense.

#9

I am confused about line 20
left += 1;
Intuitively it seems to count duplicate since all combinations with arr[i] are handled by right - left

The following code is more intuitive since it breaks the while loop after right - left. It passes the test cases. I am not sure why this works though. See the couple of lines commented for changes

const triplet_with_smaller_sum = function(arr, target) {

  let count = 0;

  // sorting array in reverse
  arr.sort((a, b) => b - a)

  for(let i = 0; i < arr.length; i++){

    let left = i + 1, right = arr.length - 1

    const x = arr[i]

    while(left < right){      

      if(x + arr[left] + arr[right] < target) {

        count += right - left

        // rather than incrementing  breaking the loop
        break;

      } else {

        left += 1

      }

    }

  }

  return count;

};