Solution: Triplets with Smaller Sum

Problem Statement

Given an array arr of unsorted numbers and a target sum, count all triplets in it such that arr[i] + arr[j] + arr[k] < target where i, j, and k are three different indices. Write a function to return the count of such triplets.

Example 1:

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

Example 2:

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

.....

Like the course? Get enrolled and start learning!

Hussain Zaidi

· 3 years ago

import java.util.*;

class Solution {

  public int searchTriplets(int[] arr, int target) {
    int count = 0;
    Arrays.sort(arr); //sort
    for (int i = 0; i<arr.length - 2; i++) {
      int lo = i + 1; //find pairs forward from i
      int hi = arr.length - 1;
      while (lo < hi) {
        int currSum = arr[i] + arr[lo] + arr[hi];
        if (currSum < target){
          //since sorted, all numbers from arr[lo] to arr[hi] are valid pairs 
          count = count + (hi - lo); //since decreasing hi until lo will still create sum < target
          lo++; //try new pairing from new lo to hi
        } else {
          hi--; //sum too big, we need smaller sum so decrement hi to get smaller value
        }
      } //end while loop
    }
    return count;
  }
}