Leetcode Amazon Interview Questions

Three Sum

Leetcode - No. 15

3 Sum

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

3 Sum

1
2
3
4
5
6
7
8
9
Example:

Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

Problem Analysis

Firstly, we need to ask about some problems with the conditions.

  • Is the answer has a duplicated number? (If no, need to deal with the repeated number in the original array)

  • Is the original array has been sorted? (If no, sorting an array take O(nlogn) time complexity)

  • Is the original array only have a unique number? (If no, again, need to consider how to deduplicated)

Algorithm Analysis - Backtracking (Fail when the input is too large)

Sort the numbers array first and Try each possible solutions. Base case will be when the size of temperatory list equal to 3 and the sum equal to 0. Used a for loop to keep adding number into temp list, we also need to record the current start Index and remove the current number after each time we backtrack to the current state.

But by using this DFS algorithm, if the input is too large there will have a time limit exceeded problem.

Algorithm - 2 Pointers + Sorting

Sort the original array first and go through the list from the first index to the third number counted from the last numbers. Get the first number and make the subproblem becomes to find the 0 - current number which is a two sum problem solving be two pointers. In this case, we need to deal with the duplicated number since they will get the same result.

To solve the two sum problem, we used a start and end pointer to find the target value. Here we also need to deal with the duplicated number after we find one of the pair numbers sums up as target number and then start looking for the second pair of the answer in the rest of list.

Time Complexity Analysis

  • Time: O(n^2)
  • Space: O(1)

Code Implementation - Backtracking

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> results = new ArrayList<>();
        backtracking(results, new ArrayList<>(), nums, 0, 0);
        return results;
    }
    
    public void backtracking(List<List<Integer>> results, List<Integer> tempList, int[] nums, 
                             int sum, int startIndex)
    {
        if(tempList.size() == 3 && sum == 0 && !results.contains(tempList) ) {
            results.add(new ArrayList<>(tempList));
        }
        
        for(int i = startIndex; i < nums.length; i++) {
            tempList.add(nums[i]);
            sum += nums[i];
            backtracking(results, tempList, nums, sum, i + 1);
            sum -= nums[i];
            tempList.remove(tempList.size() - 1);
        }
    }
}

Code Implementation - Sorting + Two Pointers

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> results = new ArrayList<>();
        for(int i = 0; i < nums.length - 2; i++) {
            int currentNumber = nums[i];
            /* Skip the duplicated number */
            if(i != 0 && currentNumber == nums[i - 1]) {
                continue;
            }
            /* Find "0 - current Number" in the rest of array */
            int start = i + 1;
            int end = nums.length - 1;
            
            while(start < end) {
                int sum = currentNumber + nums[start] + nums[end];
                if(sum == 0) {
                    results.add(Arrays.asList(currentNumber, nums[start], nums[end]));
                    /* Duplicated the numbers behind end and after start */
                    while(start < end && nums[start] == nums[start + 1]) start++;
                    while(end > start && nums[end] == nums[end - 1]) end--;
                    
                    /* Move forward to the next pairs */
                    end--; start++;
                }
                else if(sum > 0) {
                    end--;
                }
                else {
                    start++;
                }
            }
        }
        return results;
    }
}

Follow up Question - 3 Sum Closest and K Sum

16 3 Sum Closest

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int len = nums.length;
        /* Init the result as first three elements */
        int result = nums[0] + nums[1] + nums[2];
        
        for(int i = 0; i < len - 2; i++) {
            int start = i + 1;
            int end = len - 1;
            
            while(start < end) {
                /* get the current sum */
                int sum = nums[i] + nums[start] + nums[end];
                if(sum == target) return target;
                
                /* Modify two pointers */
                if(sum < target) {
                   start ++;
                } else {
                    end --;
                }
                
                /* Compare with the result to see if the current sum is the cloest*/
                if(Math.abs(target - sum) < Math.abs(target - result)) {
                    result = sum;
                }
            }

        }
        return result;
    }
}

18 K Sum

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public class Solution {
    public int kSum(int A[], int k, int target) {

        if (A == null || A.length == 0) {
            return 0;
        }

        int n = A.length;
        // state
        // f[i][j][t] take j numbers from the first i numbers, how many combinations' sum is t
        int[][][] f = new int[n + 1][k + 1][target + 1];

        // initialize
        for (int i = 0; i <= n; i++) {
            f[i][0][0] = 1;
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= k && j <= i; j++) {
                for (int t = 1; t <= target; t++) {
                    f[i][j][t] = f[i - 1][j][t];
                    /* 如果目前的 t >= A[i - 1] */
                    /* f(i,j,t) = f(i-1,j,t) + f(i-1,j-1,t) - A[i - 1] */
                    if (t >= A[i - 1]) {
                        f[i][j][t] = f[i - 1][j][t] + f[i - 1][j - 1][t - A[i - 1]];
                    }
                }
            }
        }

        return f[n][k][target];
    }
}

FEATURED TAGS
Leetcode Amazon Interview Questions