educative.io

Educative

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

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;

5 Likes

curious about this as well

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.

4 Likes

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.