Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

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!
A

Anonymous

· 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
A

Anonymous

· 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
A

Anonymous

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

Anonymous

· 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
A

Anonymous

· 3 years ago

I believe the time complexity of the problem would be N^2, instead of N^3 as pointed out in the solution as we go through the outer loop (N), and go through the inner while loop (N) once again, making it (N^2)

Show 1 reply
A

Anonymous

· 3 years ago

Triplet [-1,2,4]

  • Sum: -1 + 2 + 4 = 5
  • Absolute Difference from Target (|5 - 5|) = 0 (This is the closest triplet)
Show 1 reply
A

Anonymous

· 3 years ago

Why is the solution's time complexity O(n^2)?

If sorting the array takes O(nlogn) time and searchPair() takes O(n) time, why does searchTriplets() take O(n^2) time? I thought the time complexity would have been O(nlogn + n) ~= O(nlogn).

Show 2 replies
A

Anonymous

· 4 years ago

Is there a reason why the outer loop is iterating from 0 to array.length-2 instead of array.length-1?

Is it to prevent iterating through an array whose length is less than 4?

Show 2 replies
A

Anonymous

· 4 years ago

could I get some clarification please for why don't you care about skip same element to avoid duplicate triplets as you did in Triplet Sum to Zero problem?

Show 1 reply
A

Anonymous

· 5 years ago

Hi, could I get some clarification please for why we increment count by the difference between the right and left index?

count += right - left;

My expectation would be that we could increment count by 1 as we have found a new triplet and the goal is to count the number of triplets that are less than the target.

Show 2 replies

Reading Progress

0%

Vote for new content