Sunday, November 9, 2014

Facebook: Two elements sum up to a third

Given a sorted array, write a program to decide if two elements sum up a third.

Understand the problem:
The problem looks quite like the 3-sum problem, so we can apply the similar approaches. 

Use two pointers:
If the sorted array does not contain negative numbers, we can apply the two pointers approach. The idea is similar to the 3 sum. The only difference is i must start from the end, else the two sums cannot equal to the A[i].

Code (Java):
public class Solution {
    public List<List<Integer>≫ twoSum(int[] num) {
        List<List<Integer>≫ result = new ArrayList<List<Integer>>();
        if (num == null || num.length < 3) {
            return result;
        }
        
        for (int i = num.length - 1; i >= 2; i--) {
            if (i != num.length - 1 && num[i] == num[i + 1]) {
                continue;
            }
            
            int lo = 0;
            int hi = i - 1;
            
            while (lo < hi) {
                int sum = num[lo] + num[hi];
                
                if (sum == num[i]) {
                    List<Integer> temp = new ArrayList<Integer>();
                    temp.add(num[lo]);
                    temp.add(num[hi]);
                    temp.add(num[i]);
                    
                    result.add(temp);
                    
                    lo++;
                    hi--;
                    
                    // Handle duplicates
                    while (lo < i && num[lo] == num[lo - 1]) {
                        lo++;
                    }
                    
                    while (hi > 0 && num[hi] == num[hi + 1]) {
                        hi--;
                    }
                } else if (sum > num[i]) {
                    hi--;
                } else {
                    lo++;
                }
            }
        }
        return result;
    }

    public static void main(String[] args) {
      Solution sol = new Solution();
      
      int[] num = new int[]{0, 1, 1};
      List<List<Integer>> result = sol.twoSum(num);

      for (List<Integer> list : result) {
        for (Integer elem : list) {
          System.out.print(elem + " "); 
        }
        System.out.println("");
      }
    }
}


Discussion:
The time complexity is O(n^2) while the space is O(1). Noted that why we constraint that all numbers must be non-negative. That is because we assume that the num[i] is the largest number and we test if (A[lo] + A[hi] == A[i]). However, if one of the numbers are negative, the method does not hold. For e.g. [-1, 0, 1], then we cannot find -1 + 1 == 0. 
That is the major drawback of this solution.

A hash table solution:
We may use a hash table to store the array[i] as the key, and its index as the value.
So it this way, we can iterate any two possible pair of i and j, and check its sum A[i] + A[j] exists in the hash table. 

So why we need to store the index as well. That is because if 0 is existed in the hash table. 




No comments:

Post a Comment