Counting triplets with smaller sum

Question

I was trying one problem to count the number of triplets in an array whose sum is less than target value.


Input: [-1, 4, 2, 1, 3], target=5 
Output: 4
Explanation: There are four triplets whose sum is less than the target: 
   [-1, 1, 4], [-1, 1, 3], [-1, 1, 2], [-1, 2, 3]

My Code

import java.util.*;

class TripletWithSmallerSum {

  public static int searchTriplets(int[] arr, int target) {
    Arrays.sort(arr);
    int count = 0;
    for(int i = 0; i < arr.length - 2; i++)
    {
      int left = i + 1;
      int right = arr.length - 1;
      while(left < right)
      {
        int targetDiff = target - arr[i] - arr[left] - arr[right];
        if (targetDiff > 0)
        {
          count++;
          right--;
        }
        else 
        {
          left++;
        }
      }
    }
    // TODO: Write your code here
    return count;
  }
}

It produces the output of 3 where as correct value should be 4 as per the above given input. My logic was , say , x + y + z < targetSum , it implies (targetSum - (x + y + z) ) > 0. If this is true I will increase the count and then decrement the right pointer , since array is sorted. If its not true then I will increment the left pointer . But my logic does not cover the triplet {-1, 2, 3}.

Below is the correct code given by author.

import java.util.*;

class TripletWithSmallerSum {

  public static int searchTriplets(int[] arr, int target) {
    Arrays.sort(arr);
    int count = 0;
    for (int i = 0; i < arr.length - 2; i++) {
      count += searchPair(arr, target - arr[i], i);
    }
    return count;
  }

  private static int searchPair(int[] arr, int targetSum, int first) {
    int count = 0;
    int left = first + 1, right = arr.length - 1;
    while (left < right) {
      if (arr[left] + arr[right] < targetSum) { 
        count += right - left;
        left++;
      } else {
        right--; // we need a pair with a smaller sum
      }
    }
    return count;
  }

  public static void main(String[] args) {
    System.out.println(TripletWithSmallerSum.searchTriplets(new int[] { -1, 0, 2, 3 }, 3));
    System.out.println(TripletWithSmallerSum.searchTriplets(new int[] { -1, 4, 2, 1, 3 }, 5));
  }
}

The author has used the concept , say x + y + z < targetSum , it implies x + y < targetSum - z . But I don't get the logic of line count += right - left; . How author use this one line to capture the count. If some one can give me the intution on how to reach this inference. Also what is wrong with my code and what can I do to correct it.

bylal · Answer

A first issue with your code is that : you only decrease the right index if the sum is inferior to the target. However, since you have ordered your list, well you will only be entering that case until left=right.

Quick example : [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], target=14
if 1+2+10 <13:
then you will only decrease 10 until you reach 2 in your array

and then you proceed to iterate to the next i-index, here going from 0 to 1. Meaning that: you will never get the solutions in between such as [1,3,9] and all the one that follows.

I hope it helps you see where there was an error in the logic, which was not from the statement : (targetSum - (x + y + z) ) > 0 but from the action you take according to the result (True/False).

Now, I am not sure there would be an easy way to adapt your code corrctly, because the main issue here is that you have iterate over 2 indexes at once (right and left).

Now regarding your author's answer :

The trick behind :

count += right - left;

goes back to the issue you had, if i tame my example, for

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

it is basically saying that, since the array is ordered, if the sum of two integers with the right one is inferior to target, then it will also be true for all integers inferior to right :

1+2+10<14 => 1+2+9<13

And this statement is true for all integers between left and right, so instead of doing a loop for which we already have the answer, he adds to count the differences between right and left, in other words, the number of integers in your array that will be greater than left and lower than right.

Now that i have explained that, you could use the same "trick" to your code:

class TripletWithSmallerSum {

  public static int searchTriplets(int[] arr, int target) {
    Arrays.sort(arr);
    int count = 0;
    for(int i = 0; i < arr.length - 2; i++)
    {
      int left = i + 1;
      int right = arr.length - 1;
      while(left < right)
      {
        int targetDiff = target -( arr[i] + arr[left] + arr[right]);
        if (targetDiff > 0)
        {
          count += right - left;
          left++;
        }
        else 
        {
          right--;
        }
      }
    }
    // TODO: Write your code here
    return count;
  }
}

I tried to be as detailed as possible, hope it helps you understand better!

Counting triplets with smaller sum

1 Answers