3Sum Smaller

Two Pointer

Problem

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.

For example:

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]

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]

Solution

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

  for i in range(len(arr)-2):
    j = i+1
    k = len(arr)-1

    while j < k:
      sums = arr[i]+arr[j]+arr[k]
      if sums < target:
      
      # since arr[k] >= arr[j], therefore, we can 
      #replace arr[k] by any number between
      #left and right to get a sum less than the target sum
        count+=k-j
        j+=1
      else: #sum is too large
        k-=1

      
      

  return count