3-Sum problem in O(n^2) time and O(1) space

user_14328184 0
Viewed 604

Let A, B and C be three arrays of n integers each. I want to find 3 integers a,b,c s.t. a belongs to A, b belongs to B, c belongs to C and c=a+b.

Approach:

  1. Calculate all possible sums a+b and store it in hash map. Time Complexity = O(n^2)
  2. Parse through array C and check if element is present in hash map or not.

This approach requires O(n^2) space and O(n^2) time complexity. Can it be optimized to find a,b,c in O(n^2) time without extra space(ie- Space Complexity = O(1)) ?

space-complexity time-complexity sorting algorithm
1 Answers

I have below approach for this. Is it correct ?

Algorithm:

 1. Sort A and B. Time complexity= O(nlgn) using  HeapSort
    2. Loop through elements of C
    2.1 Take 2 pointers one at beginning of A,
 second at end of B. Let this be left and right pointers
 and make left parse A and right parse B.

        2.2 if A[left] + B[right] == C[index] 
         then break
          else if A[left] + B[right] < C[index]
              left++;
          else
              right--;

Time complexity for step 2 = O(n^2)

Overall time complexity = O(n^2)

Space complexity = O(1)

user_143281840
Related