Two to K Sum

Two Sum (LC.1)

Given an array of integers, return indices of the two numbers such that they add up to the target.

Assume that each input would have exactly one solution.

Example

Input: nums = [2, 7, 11, 15], target = 9
Return: result = [2, 7]

Brute Force

The most naive approach is to try all possible combinations (for i from 0 to n-1, for j from i+1 to n -1)

If two numbers add up to the target, return those two indices.

public int[] twoSum(int[] nums, int target) {
    for (int i = 0; i < nums.length; i++)
        for (int j = i + 1; j < nums.length; j++)
            if ((nums[i] + nums[j]) == target)
                return new int[] {i,j};
    return null;
}

O(n^2) runtime O(1) space

Two Pointers

We can use an in-place sorting alg to sort the array first. Preferably quick sort because although merge sort is also O(nlogn) but recursion uses system stack which is O(n) space. Arrays.sort() uses a Dual-Pivot Quicksort.

Use left/right pointers. If nums[L] + nums[R] < target, move left to the right. If nums [L] + nums[R] > target, move R to the left. while loop L < R. if they collide return null.

public int[] twoSum(int[] nums, int target) {
    Arrays.sort(nums);
    int L = 0, R = nums.length - 1;
    while (L < R) {
        if (nums[L] + nums[R] == target)
            return new int[] {nums[L], nums[R]};
        else if (nums[L] + nums[R] > target)
            R--;
        else
            L++;
    }
    return null;
}

Since sorting is done in-place, we have O(nlogn) run time and O(1) space.

Note: Sorting is worth it when the polynomial degree is high. If you want a linear time algorithm, don't use sorting.

Note2: This solution doesn't really return what the questions is asking. It returns the actual elements instead of their indices. If we want get the indices, then we have to create a new array (O(n) space) sort it, two pointers, then find the indices in the original array.

Hashing

Now we are talking about how to solve this in linear time. We will use a data structure called hash table and its awesome property - O(1) look up.

We dump the array to a hashtbl first. Then for each element check if the complement (target - nums[i]) exists in the hashtbl. If so, return {i, hashtbl.get(target - nums[i])}.

public int[] twoSum(int[] nums, int target) {
    HashMap<Integer, Integer> hash = new HashMap<>();
    // dump array info to a hash table, elements as keys and indices as values
    for (int i = 0; i <= nums.length - 1; i++) {
        hash.put(nums[i], i);
    }

    // check if target - nums[i] is in the keyset
    for (int i = 0; i <= nums.length - 1; i++) {
        int complement = target - nums[i];
        if (hash.containsKey(complement) && hash.get(complement) != i) {
            return new int[] {i, hash.get(complement)};
        }
    }
    return null;
}

Now we finally have O(n) time but also have O(n) space because of the HashMap.

Two Sum w/ Duplicates

Return all pairs of indices that sum to target. The input might have duplicate elements.

We have relaxed our original assumption of only one solution. Notice: we want indices not values.

Example

Input: nums = [1, 2, 2, 3], target = 5
Return: result = [[1, 3], [2,3]]

Analysis

Two pointers won't work by itself because we don't know whether we should move L or R when we find an answer. Then we can try hashing. The key is how do we construct our hash structure? Same as above, values as keys and indices as a list of values.

Here is the general idea to K sum problems - reduction. We want to reduce this problem to the non-duplicate version of two sum. Now we transform the key set into a non-duplicate sorted array. Now we can safely use the two pointer method on the new array. When we find a working pair, simply do L++ and R-- because we don't have duplicates.

Code

public List<List<Integer>> twoSumDup(int[] nums, int target) {
    List<List<Integer>> result = new ArrayList<>();
    HashMap<Integer, ArrayList<Integer>> hash = new HashMap<>();
    // create the hash structure
    for (int i = 0; i < nums.length; i++) {
        if (hash.containsKey(nums[i])) {
            hash.get(nums[i]).add(i);
        } else {
            ArrayList<Integer> indexList = new ArrayList<>();
            indexList.add(i);
            hash.put(nums[i], indexList);
        }
    }
    // create nondup array
    int[] nondup = new int[hash.keySet().size()];
    int i = 0;
    for (Integer ele : hash.keySet())
        nondup[i++] = ele;
    Arrays.sort(nondup);
    // use two pointer method on the NON-duplicate array 
    // scan the duplicate array will obviously give you duplicate results...
    int L = 0, R = nondup.length - 1;
    while (L < R) {
        if (nondup[L] + nondup[R] == target) {
            for (Integer ele1 : hash.get(nondup[L]))
                for (Integer ele2 : hash.get(nondup[R])) // worse case O(n^2)
                    result.add(Arrays.asList(ele1, ele2));
            L++;
            R--;
        } else if (nondup[L] + nondup[R] > target) {
            R--;
        } else {
            L++;
        }
    }
    return result;
}

Consider the case nums = [1, 1, 1, 1, 1], target = 2 , we have 4+3+2+1=10 pairs. The worst case is unfortunately O(n^2) same as the brute force solution. But enumerating all the position combinations will have an average case of O(n^2). Hashing offers a much better average case runtime.

Two Sum Difference

Two Sum Recap

This question tests candidate's ability to write loops, understanding sorting, and taking advantage of the property of the sorted array with two pointers. Hashing is also an option. The candidate should realize the time and space trade off. Especially this case, we trade O(n) extra space to bring down runtime from O(n^2) to O(n). In short, getting value we want two pointers. Getting indices we want to use hashing.

3 Sum (LC.15)

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

We are finding triplets of elements (not indices). There might be duplicate elements. The solution set cannot contain duplicate triplets.

Example

Input: nums = [-1, 0, 1, 2, -1, -4]
Return: [[-1, 0, 1], [-1, -1, 2]]

Analysis

Brute force will be O(n^3). Again we can have three loops to enumerate all the possible combinations. We want to reduce this to the original two sum. Sorting is worth when bringing O(n^3) to O(n^2). Two pointer method is the better approach because of its constant space.

In terms of avoiding duplicates, the brute force way is to use a HashSet. But in the spirit of constant space, we want to something else that's more elegant.

Two Pointers

The two pointer gimme duplicate answers?! Wut just happened ʕ •ₒ• ʔ Read the question plz read the question... The solution set may not contain duplicates. Since we can sort the array, duplicate elements are adjacent to each other.

public List<List<Integer>> threeSum(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    Arrays.sort(nums);
    int L, R, target;
    for (int i = 0; i < nums.length - 1; i++) {
        // need to skip like a boss here as well
        if (i == 0 || nums[i] != nums[i-1]) {
            L = i + 1;
            R = nums.length - 1;
            target = 0 - nums[i];
            while (L < R) {
                if (nums[L] + nums[R] == target) {
                    result.add(Arrays.asList(new Integer[] {nums[i], nums[L], nums[R]}));
                    // skip like a boss cause the array is sorted
                    while(L < R && nums[L] == nums[L+1]) L++;
                    while(L < R && nums[R] == nums[R-1]) R--;
                    L++;
                    R--;
                } else if (nums[L] + nums[R] < target) {
                    L++;
                } else {
                    R--;
                }
            }
        }
    }
    return result;
}

This solution gives O(n^2) time and O(1) space.

Hashing

HashMap approach will require a HashSet to eliminate the duplicate triplets. It's sort of like a brute force / wasting space O(n^2) solution.

3 Sum Closest (LC.16)

Given an array of n integers, find three integers in the array such that the sum is closest to the target.

Return the sum of the three integers. Assume exactly one solution.

Example

Input: nums = [-1, 2, 1, -4], target = 1
Return: (-1 + 2 + 1) = 2

Analysis

The brute force approach will be enumerating all the possible combinations using three loops. Return the trisum with the least distance to the target. We can obviously do better with the two pointer approach from 3 sum. We want to minimize epsilon and keep track of the closest sum.

Approach: 1. sort nums 2. for i from 0 to n-1 3. use two pointers L and R 4. try to get closer to the target update epsilon and closestSum

Code

public int threeSumClosest(int[] nums, int target) {
    if (nums == null || nums.length < 3)
        return Integer.MAX_VALUE;

    Arrays.sort(nums);

    int L, R, closestSum = Integer.MAX_VALUE, epsilon = Integer.MAX_VALUE;
    for (int i = 0; i < nums.length; i++) {
        L = i + 1;
        R = nums.length - 1;

        while (L < R) {
            // update the closest sum
            if (Math.abs(target - nums[i] - nums[L] - nums[R]) < epsilon) {
                epsilon = Math.abs(target - nums[i] - nums[L] - nums[R]);
                closestSum = nums[i] + nums[L] + nums[R];
            }

            if (nums[i] + nums[L] + nums[R] == target) {
                return closestSum;
            } else if (nums[i] + nums[L] + nums[R] < target) {
                L++;
            } else {
                R--;
            }
        }
    }
    return closestSum;
}

And we are closer to finish. Hang in there. First ACE!

3 Sum Smaller (LC.259)

Given an array nums and a target, find all possible triplets such that nums[i] + nums[j] + nums[k] < target.

Return the number of triplets. Assume no duplicate element.

Example

Input: nums = [-2, 0, 1, 3], target = 2
Return: [[-2, 0, 1], [-2, 0, 3]].length = 2

Analysis

A variation from 3 sum. Simple question but can trip people up on finding all possible triplets.

Code

public int threeSumSmaller(int[] nums, int target) {
    if (nums == null || nums.length < 3)
        return 0;

    Arrays.sort(nums);

    int L, R, count = 0;
    for (int i = 0; i < nums.length; i++) {
        L = i + 1;
        R = nums.length - 1;
        while (L < R) {
            if (nums[i] + nums[L] + nums[R] < target) {
                count += R - L; // by moving L you skiped R - L pairs
                L++;
            } else {
                R--;
            }
        }
    }    
    return count;
}

3 Sum Recap

Extension from two sum. They all ask getting values instead of indices. So two pointers approach for all of them.

4 Sum (LC.18)

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

The array may contain duplicate elements. The solution set must not contain duplicate quadruplets.

Example

Input: nums = [1, 0, -1, 0, -2, 2], target = 0
Return: 
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

Analysis

Reduce 4sum to 3sum to sorted 2sum.

Approach: 1. sort nums 2. for i = 0 to n-1 //skip dup 3. for j from i + 1 to n-1 // now is 3sum skip dup 4. Two pointers L/R

Code

public List<List<Integer>> fourSum(int[] nums, int target) {
    List<List<Integer>> result = new ArrayList<>();
    if (nums == null || nums.length < 4)
        return result;
    Arrays.sort(nums);

    for (int i = 0; i < nums.length; i++) {
        if (i == 0 || nums[i] != nums[i-1]) {
            for (int j = i + 1; j < nums.length; j++) {
                if (j == i + 1 || nums[j] != nums[j-1]) {
                    int L = j + 1, R = nums.length - 1;
                    while (L < R) {
                        if (nums[i] + nums[j] + nums[L] + nums[R] == target) {
                            result.add(Arrays.asList(
                                new Integer[] {nums[i], nums[j], nums[L], nums[R]}));
                            while (L < R && nums[L+1] == nums[L]) L++;
                            while (L < R && nums[R-1] == nums[R]) R--;
                            L++;
                            R--;
                        } else if (nums[i] + nums[j] + nums[L] + nums[R] < target) {
                            L++;
                        } else {
                            R--;
                        }
                    }
                }
            }
        }
    }
    return result;
}

Follow Up

2/11/2017 update: Is this it O(n^3)? Can you do even better?

Split this question into two sums then check the answer

Time Complexity Avg O(n^2) Worst Case O(n^3)

Motivation

Can we write a function to solve 2, 3, 4, 5, ..., K sum? Here we go ʕ； •`ᴥ•´ʔ

K Sum II (LC.90)

Given n unique integers, a number k (sum) and a target. Find all possible k integers where their sum is target.

This question is testing searching recursively. We don't have to add another layer of complexity such as input might contain duplicate elements.

Example

Input: A = [1,2,3,4], k = 2, target = 5
Return: [ [1, 4], [2, 3] ]

Analysis

We want to enumerate all possible tuples that sum to target. The brute force approach is using DFS to create a DFS tree and put all the leaves that match with the target. We have (n^k) possible tuples. So the runtime will be $O(n^k)$. But as we learned from 2, 3, 4 sum, we can bring down the runtime from $O(n^k)$ to $O(n^{k-1})$ using the two pointer method with sorting. Let's investigate both approaches here.

Depth First Search All Tuples

public ArrayList<ArrayList<Integer>> kSumII(int[] A, int k, int target) {
    ArrayList<ArrayList<Integer>> results = new ArrayList<>();
    if (A == null || A.length < k)
        return results;
    ArrayList<Integer> tuple = new ArrayList<Integer>();
    searchDFS(results, A, k, target, 0, tuple);
    return results;
}

private void searchDFS(ArrayList<ArrayList<Integer>> results, 
        int[] A, int k, int target, int index, ArrayList<Integer> tuple) {
    if(k == 0 && target == 0) {
        results.add(new ArrayList<Integer>(tuple));
        return;
    }
    // target < 0 won't work for negative values
    // k < 0 works but can create an unnecessary level
    if (k <= 0 || target < 0 || index > A.length - 1) {
        return;
    }
    searchDFS(results, A, k, target, index+1, tuple); // acts like a for loop
    tuple.add(A[index]);
    searchDFS(results, A, k-1, target-A[index], index+1, tuple);
    tuple.remove(tuple.size() - 1);
}

The simplest way to understand this kind of recursive search is to visualize it as a DFS tree. And how you choose and pick which "leaf" to join your collection. This is like a follow up question for subsets.

We realized a few potential enhancements. k <= 0 can cut out the extra level. we can use a for loop instead of doubling the stack frames with another recursive call. index > A.length - 1 is already included in the for loop. if (k == 0) then check target == 0 is so elegant (but we still want target < 0 to cut down some bad paths).

private void searchDFS(ArrayList<ArrayList<Integer>> results, int[] A, int k, 
        int target, int index, ArrayList<Integer> tuple) {
    if (target < 0) {
        return;
    }
    if (k == 0) {
        if (target == 0) {
            results.add(new ArrayList<Integer>(tuple));                
        }
        return;
    }
    // searchDFS(results, A, k, target, index+1, tuple);
    for (int i = index; i < A.length; i++) {
        tuple.add(A[i]);
        searchDFS(results, A, k-1, target-A[i], i+1, tuple);
        tuple.remove(tuple.size() - 1);            
    }
}

Something like this. ʕ – ᴥ – ʔ

Reduction to Two Pointers

Look at 4sum and design this recursive algorithm. Say we need to solve 8sum. We don't want to write out all the for loops explicitly. We need to solve this recursively.

Thought process:

• What do we need for in the recursive call?

  • (results, A, k, target, startIndex yes, tuple yea it's the potential solution)

  • startIndex is for getting the subarray

• Backtracking

  • Only reset the tuple from the top level? nope it doesn't work that way.

  • you gotta do the same thing at each level. use backtracking instead

public ArrayList<ArrayList<Integer>> kSumII(int[] A, int k, int target) {
    ArrayList<ArrayList<Integer>> results = new ArrayList<>();
    if (A == null || A.length < k)
        return results;
    ArrayList<Integer> tuple = new ArrayList<Integer>();
    Arrays.sort(A);
    reduceToTS(results, A, k, target, 0, tuple);
    return results;
}

private void reduceToTS(ArrayList<ArrayList<Integer>> results, int[] A, int k, 
        int target, int startIndex, ArrayList<Integer> tuple) {
    // base case is k=2, cannot solve 1 sum test case
    if (k == 2) {
        int L = startIndex, R = A.length - 1;
        while (L < R) {
            if (A[L] + A[R] == target) {
                tuple.add(A[L]); 
                tuple.add(A[R]);
                results.add(new ArrayList<Integer>(tuple));
                // this removal helps remove when backtrack
                tuple.remove(tuple.size() - 1); 
                tuple.remove(tuple.size() - 1);
                L++;
                R--;
            } else if (A[L] + A[R] < target) {
                L++;
            } else {
                R--;
            }
        }
        return;
    }

    for (int i = startIndex; i <= A.length - k; i++) {
        tuple.add(A[i]);
        reduceToTS(results, A, k-1, target-A[i], i+1, tuple);
        tuple.remove(tuple.size() - 1); // how do i engineer a nested loop?
    }
}

This won't pass LC.90 because the base is 2sum (the test cases include 1sum). Nonetheless, a test case [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,5235,23634], 8, 87 works fine. We don't have to write 7 loops explicitly solve this 8sum problem. And we have generalized the idea of k sum that we can solve this in $O(n^{k-1})$ with sorting and two pointers.

K Sum (DP) (LC.89)

Given n distinct positive integers, integer k (sum) and a target. Find k numbers where sum is target.

Return the number of solutions. You don't have to return all the possible solutions only the number of them.

Example

Input: A = [1,2,3,4], k = 2, target = 5
Return: [ [1, 4], [2, 3] ].length = 2

Analysis

Well this certainly looks similar to KSum II. We can enumerate all the possible combinations then return the count. Ez-pez right?

Brute Force Search

public int kSum(int A[], int k, int target) {
    if (A == null || A.length < k)
        return 0;
    return sumDFS(A, k, target, 0, 0);
}

private int sumDFS(int A[], int k, int target, int startIndex, int count) {
    if (k == 0 && target == 0) {
        return count + 1;
    }       
    if (k <= 0 || target < 0) {
        return count;
    }
    for (int i = startIndex; i < A.length; i++) {
        count = sumDFS(A, k-1, target-A[i], i+1, count);
    }
    return count;
}

Input: [1,3,4,5,8,10,11,12,14,17,20,22,24,25,28,30,31,34,35,37,38,40,42,44,45,48,51,54,56,59,60,61,63,66], 24, 842
Expected: 453474
Hint: Your code ran too much time than we expected. Check your time complexity.

Ok. How can we do better than $O(n^k)$?

Overlapping Subproblems

Not that easy to see. It turns out this is really similar to the two-dimensional knapsack problem. We'll come back and finish off then.

It is a pretty obvious dp question once we get the essence of dynamic programming. We only need to store the number of solutions instead of the actual solutions. So creating states to keep track of them should not be hard. We have target value (integer) and number of items that we can put in the knapsack (discrete). By the nature of this kind of problem, the subproblems will overlap (ex. a set of items that contribute to a specific target value).

References

• Summary for ksum problems by Sigmainfy
• K Sum I & II by Welkin Lan
• K Sum I by ButterCola

Let's end with some sub-linear magic.