Grokking the Engineering Manager Coding Interview

0% completed

​

Triplets with Smaller Sum (medium)

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

Jharol Rivera

· 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
Isabela Vlls

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
A

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
Hussain Zaidi

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

Micky M

· 4 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
E

Eduardo Sánchez

· 4 years ago

I need clarification on the problem statement.

It states that " i, j, and k are three different indices." and not values.

For the first example when the list is already sorted : [ -1, 0, 2, 3 ] The combinations that fulfill the formula (arr[i] + arr[j] + arr[k] < target) are: Values: [ [ -1, 0, 3 ], [ 0, -1, 3 ], [ 2, -1, 0 ] ] indexes: [ [ x: 0, y: 1, z: 3 ], [ x: 1, y: 0, z: 3 ], [ x: 2, y: 0, z: 1 ] ]

I'm confused because the indexes are different, but definitely, we have a repeating triplet in a different order ( [ -1, 0, 3 ], [ 0, -1, 3 ],...

do you have any clarification on this? what am I misreading on the problem?

Show 3 replies
D

Dee

· 4 years ago

Where does the condition i != j != k come from? This isn’t stated in the question.

Show 1 reply
I

Isam Nagi

· 4 years ago

I believe the first solution for Triplets with Smaller Sum (medium) in the two pointer section, has an error. I believe the "count" (which is the result to return) is describing the total of the triplets in value rather then the count of triplets that pass the test.

Show 1 reply
B

Ben Cornia

· 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
Jessica Liang

Jessica Liang

· 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