Find all triplets in array with sum less than or e

Question

This was recently asked to a friend in an interview and we do not know of any solution other than the simple O(n³) one.

Is there some better algorithm?

The question is to find all triplets in an integer array whose sum is less than or equal to given sum S.

Note: I have seen other such problems on SO with performance O(n²log n) but all of them were solving the easier version of this problem like where arr[i] + arr[j] + arr[k] = S or where they were only checking whether one such triplet exists.

My question is to find out all i,j,k in arr[] such that arr[i] + arr[j] + arr[k] <= S

Answer 1

I'm keeping my original answer below, but this can actually be solved in O(n). My new solution uses a Queue to keep track of the triplets. It only returns the number of triplets but you could create a list to track the triplet lists pretty easily if that is what's required.

    class Queue (object):
      def __init__ (self):
        self.queue = []
        self.itemCount = 0

      def enqueue (self, item):
        self.queue.append (item)
        self.itemCount += 1

      def dequeue (self):
        self.itemCount += 1
        return (self.queue.pop(0))


    def findAllTriplets(li,S):
      if len(li) < 3:
        return "Not enough elements for triplets"
      tQ = Queue() # Queue to keep track of data
      tripletNum = 0 # Integer to track number of triplets to be returned
      tripletSum = 0 # Value of sum of consecutive list items for tripletNum evaluation
      for number in li:
        # Add the number to the queue immediately and add it to the current triplet sum
        tQ.enqueue(number)
        tripletSum += number
        # For the first 3 numbers only enqueue and add to the sum
        if tQ.itemCount < 3:
          continue
        # Afterwards, check if the sum of the latest three is less than S
        else:
          if(tripletSum <= S):
            tripletNum += 1
          # Dequeue the oldest element in the queue and subtract it from the tracked triplet sum
          tripletSum -= tQ.dequeue()
      return tripletNum

I believe this algorithm should do the trick in O(N^2). You should sort the array beforehand though.

Essentially, I am just finding all possible triplets where the first index i is zero and the next index is j by searching through the remaining indices (k) for all sums less than or equal to x (or S in your case). After that, I increment j by 1 and repeat the process. Once j comes to the end of the array, I start the process over with my i being i + 1 now and keep going until i equals the second to last index value (since at that point there are no possible triplets left).

Python code

def numTriplets(a,x):
   if len(a) < 3:
       return None
   i = 0
   j = 1
   triplets = []
   while True:
      for k in range(j+1,len(a)):
         if a[i] + a[j] + a[k] <= x:
            triplets.append([i,j,k])
      j += 1
      if j == len(a) - 1:
         i += 1
         j = i + 1
      if i == len(a) - 2:
         return triplets

Answer 2

This can be solved in O(n^2) complexity.

First sort the numbers --> O(nlog(n))

Now starting from the front, fix one number at a time. Now problem reduces to find 2 numbers in sorted array whose sum is <= given sum. Using 2 pointers, one from start and one from end, this can be solved in O(n). So overall complexity is O(n2)

Answer 3

I have an idea, but I'm not sure if it works.

Preprocess (remove elements > S) and sort the array first.

Then, after you picking up arr[i] and arr[j] where i < j, you may binary search S - arr[i] - arr[j] in the remaining array[j+1...n]. Once you binary-searched the index m, the k could lie between j+1 and m.

I think this may reduce the complexity. What do you think?

Answer 4

From a worst-case asymptotic perspective, there is no better algorithm since the size of the output is potentially O(n^3).

e.g. Let the array be the numbers 1 through n. Let S = 3n. Clearly, any subset of three array elements will be less than S and there are (n choose 3) = O(n^3) subsets.

There are a few ways you can speed up non-worst cases though. For example, try sorting the array first. That should give you some hints.

Answer 5

What would be the complexity of this?

If applied to a sorted list (ascending), f simply lists the triplets who's sum is less than or equal to s, one by one, without creating duplicates or scanning past the first element that is too big.

Haskell code:

f []     s result = if length result == 3 then [result] else []
f (x:xs) s result
  | length result == 3   = [result]
  | x + sum result > s   = []
  | otherwise            = f xs s (x:result) ++ f xs s result

Output:

*Main> length $ f [1..300] 300 []
731375
(5.09 secs, 402637784 bytes)

*Main> f [1..10] 13 []
[[3,2,1],[4,2,1],[5,2,1],[6,2,1],[7,2,1],[8,2,1],[9,2,1],[10,2,1],[4,3,1]
,[5,3,1],[6,3,1],[7,3,1],[8,3,1],[9,3,1],[5,4,1],[6,4,1],[7,4,1],[8,4,1]
,[6,5,1],[7,5,1],[4,3,2],[5,3,2],[6,3,2],[7,3,2],[8,3,2],[5,4,2],[6,4,2]
,[7,4,2],[6,5,2],[5,4,3],[6,4,3]]