CODEWITHSUNDEEP
arrayssumtriplet
Joystick
Joystick

Reputation: 304

Three numbers in an array that sum up to a target sum in O(n)

Recently hashedin asked the triplet sum problem where three numbers are supposed to add up to a target sum. They said to do it in O(n).

I have tried doing it in O(n^2). First, i sorted the array and then for searching the combination i had to apply sliding window technique to all of the elements in the array. I'm not able to reduce it to O(n).

def threeNumberSum(array, targetSum):
    array.sort()
    l = len(array)
    trip = list()
    for i in range(l-2):
        left = i+1
        right = len(array)-1
        while left<right:
            currentSum = array[i] + array[left] + array[right]
            if currentSum == targetSum:
                trip.append([array[i], array[left], array[right]])
                left += 1
                right -= 1
            elif currentSum < targetSum:
                left += 1
            else:
                right -= 1
    return trip

This code actually returns all the combinations of sums possible. But according to the company, only one triplet is needed. All possible triplets are not needed

Upvotes: 0

Views: 1830

Answers (4)

Joystick
Joystick

Reputation: 304

Thanks, everyone for trying to help. I have come up with an initial solution to do it in O(n). I am not yet sure if it's correct, but it's running on all the test case Here is a Github link to download the python file github.com/TripletInArrayWithTargetSum

def trip(arr, target):
    d = dict()
    n = len(arr)
    for i in arr:
        d[i] = 1

    i = 0
    j = n - 1
    while i<j:
        s = arr[i] + arr[j]     # Calculate the sum of the elements at i and j position
        diff = target - s       # Calculate the difference needed to complete the table
        if arr[i] != diff and arr[j] != diff and diff in d: # Check if the difference exists in the hashtable and as we cannot reuse elements
            return [arr[i], arr[j], diff]                   # diff should not be equal to elements at i or j and  then return the triplet if exists
        else:
            if s > target:                                  # If difference dosent exists then we adjust pointers
                j -= 1
            elif s == target:
                if arr[i+1] + arr[j] < target:
                    i+=1
                else:
                    j-=1
            else:
                i += 1

    return [None]

Download full file with test cases on Github

Upvotes: 1

RightMan
RightMan

Reputation: 41

The python code mentioned as ANSWER itself have a nested for loop , hence in any case the worst case complexity would be O(n^2). Test case: 3 4 5 2 2 19 Required sum = 23. This test case can't be solved in O(n). A bit of responsibility should be there if someone is answering on stackoverflow.

Upvotes: 3

RightMan
RightMan

Reputation: 41

The best possible approach to find a single triplet is in O(n^2) only, there might be some misunderstanding between you and the interviewer. It's impossible to do it in O(n). Happy coding!

Upvotes: 1

Archit Singh
Archit Singh

Reputation: 169

This is a hashing based solution that has complexity O(n) Python3 program to find a triplet using Hashing, returns true if there is triplet with sum equal to 'sum' present in A[]. Also, prints the triplet 

def find3Numbers(A, arr_size, sum): 
  for i in range(0, arr_size-1): 
      # Find pair in subarray A[i + 1..n-1]  
      # with sum equal to sum - A[i] 
      s = set() 
      curr_sum = sum - A[i] 
      for j in range(i + 1, arr_size): 
          if (curr_sum - A[j]) in s: 
              print("Triplet is", A[i],  
                      ", ", A[j], ", ", curr_sum-A[j]) 
              return True
          s.add(A[j])  
  return False

Upvotes: -1

Related Questions