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!

Isabela Vlls

· 2 years ago

class Solution:
  def searchTriplets(self, arr, target):
    count = 0
    arr.sort()

    for i in range(len(arr)-2):
      left, right = i + 1, len(arr)-1 # pointers

      while left < right:
        sum_elements = arr[i] + arr[left] + arr[right]
        
        if sum_elements < target: # if it's small then all to the left are valid
          count += (right - left)
          left += 1
        else:
          right -= 1   
          
    return count

Nabeel Keblawi

· 2 years ago

Here's what I did, no need for a second function or an additional for loop. Not sure why the solution recommended an O(N^3) solution when we could instead use two pointers to keep time complexity to O(N^2).

  def searchTriplets(self, arr, target):
    arr.sort()
    count = 0

    for i in range(0, len(arr) - 1):
      j = i + 1         # left pointer
      k = len(arr) - 1  # right pointer

      while j < k:
        if arr[i] + arr[j] + arr[k] < target:
          count += 1
      
        if j == k - 1:
          k = len(arr) - 1
          j += 1
        else:
          k -= 1

    return count

Eric Imho Jang

· 2 years ago

class Solution:
  def searchTriplets(self, arr, target):
    count = 0
    arr.sort()

    for i in range(len(arr)-1):
      fix = i
      left = i+1
      right = len(arr)-1


      while left < right:
        sum = arr[fix] + arr[left] + arr[right]
        diff = target - sum
        if diff > 0:
          right -= 1
          count += 1
        elif diff < 0:
          right -= 1
        elif diff == 0:
          right -= 1
        
        if left < len(arr)-2 and left >= right:
          left += 1
          right = len(arr)-1

    return count

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;
  }
}

azaankhan14678

· 3 years ago

So I wrote out the following:

class Solution:
  def searchTriplets(self, arr, target):
    arr.sort()
    count = 0
    for i in range(len(arr)-2):
      left = i+1
      right = len(arr)-1
      while left < right:
        curr = arr[i] + arr[left] + arr[right]
        if curr < target:
          count += right - left
          left +=1
        else:
          right -= 1
    return count

I essentially took the gist of what we did in the previous problem(Triplet Sum Close to Target) and created a solution using one function. My question is that is this soultion just as good or better, or worse than the actual solution if it is utilizing only one function rather than creating and calling upon a second one?

Show 1 reply