Twitter Interview Question Software Engineer / Developers
Country: United States
Interview Type: Phone Interview
The two pointer approach is a very common approach. This problem is a very common problem in interviews.
The idea was first used in connection with the general subset sum problem in the 1970s.
Can someone explain to me how the two-pointer method is done? I didn't quite follow the hint.
great idea! +1
Here is an explanation for that:
(1). First look at an easier problem: Given a SORTED array, find 2 elements that sum up to some value, say S.
This can be done in O(n) using two pointer approach: using two pointers that point to the start (Pstart) and the end (Pend) of the sorted array.
Depends on whether the sum values of the two pointers is smaller of not smaller than S, we increase Pstart++ or decrease Pend--, respectively. This takes O(n) time, since the range is decreasing every step.
No extra space is needed.
(2). Now come back to the original problem with 3 elements:
First, sort the array. This takes O(n logn) with no extra space if using heap-sort.
For each element x in this array, do this sub-task: Find in the remaining SORTED array two elements that sum up to -x. This sub-task is done in O(n) as in (1).
Thus, the overall solution is O(n ^2) with no extra space.
import java.util.Arrays;
import java.util.HashSet;
public class CombinationOf3Numbers {
public static void main(String[] args) {
Integer[] inputList = { 2, 3, 1, -2, -1, 0, 2, -3, 0 };
new CombinationOf3Numbers().findTheNumbers(inputList);
}
public void findTheNumbers(Integer[] inputList) {
Arrays.sort(inputList);
HashSet<Integer> m = new HashSet<Integer>();
//O(n)
for (int i = 0; i < inputList.length; i++) {
m.add(inputList[i]);
}
HashSet<DS> map = new HashSet<DS>();
for (int i = 0; i < inputList.length; i++) {
for (int j = i; j < inputList.length; j++) {
if (m.contains(-1 * (inputList[i] + inputList[j]))) {
DS a = new DS();
a.a[0] = inputList[i];
a.a[1] = inputList[j];
a.a[2] = -1 * (inputList[i] + inputList[j]);
map.add(a);
}
}
}
for (DS ds : map) {
System.out.println(ds);
}
}
class DS {
int[] a;
public DS() {
a = new int[3];
}
@Override
public int hashCode() {
return a[0]*1 + a[1]*1 + a[2]*2;
}
@Override
public boolean equals(Object obj) {
DS newInstance = (DS) obj;
return this.a[0] == newInstance.a[0]
&& this.a[1] == newInstance.a[1]
&& this.a[2] == newInstance.a[2];
}
public String toString() {
return a[0] + " , " + a[1] + ", " + a[2];
}
}
}
Just sort the numbers. And then take any possible cominations for the 1st 2 numbers(say a , b). The 3rd one(c = 0 - (a+b)) can be found in logn time in the sorted list. So the complexity would be (n*n*logn)
Calculate the sums of any two numbers, and store them in an array of length O(n^2). This takes O(n*n).
Then for each element x in the original list, do a binary search for -x in the sum array. This takes O(n log(n^2)) = O(2nlogn) = O(nlogn).
Thus, the overall will take O(n^2).
EDITED: Above is wrong!
Should store the sums in a hash table, no binary search needed.
A solution with quadratic running time.
1. Put negative of every number in a hash table with its index.
2. For every combination of two elements i and j (j>i) search for their sum in the hash table and print out i, j, and any index that is greater than j for their sum in the hash table.
A C++11 solution using STL vector and unordered_map (that is our hash table).
#include <iostream>
#include <unordered_map>
#include <vector>
#include <stdio.h>
using namespace std;
void solve(int *ary, int n)
{
unordered_map <int, vector<int> > hashtable(10000);
vector <int> tmp;
tmp.push_back(0);
for (int i = 0; i < n; i++)
{
auto x = hashtable.find(-1 * ary[i]);
if (x != hashtable.end())
x->second.push_back(i);
else
{
tmp[0] = i;
hashtable[-1 * ary[i]] = tmp;
}
}
for (int i = 0; i < n; i++)
{
for (int j = i + 1; j < n; j++)
{
auto x = hashtable.find(ary[i] + ary[j]);
if (x != hashtable.end())
{
for (auto y : x->second)
{
if (y>j)
printf("%d: %d , %d: %d , %d: %d\n", i, ary[i], j, ary[j], y, ary[y]);
}
}
}
}
}
Love the way that auto does magic in C++11.
// returns true if there is triplet with sum equal
// to 'sum' present in A[]. Also, prints the triplet
bool find3Numbers(int A[], int arr_size, int sum)
{
int l, r;
/* Sort the elements */
quickSort(A, 0, arr_size-1);
/* Now fix the first element one by one and find the
other two elements */
for (int i = 0; i < arr_size - 2; i++)
{
// To find the other two elements, start two index variables
// from two corners of the array and move them toward each
// other
l = i + 1; // index of the first element in the remaining elements
r = arr_size-1; // index of the last element
while (l < r)
{
if( A[i] + A[l] + A[r] == sum)
{
printf("Triplet is %d, %d, %d", A[i], A[l], A[r]);
return true;
}
else if (A[i] + A[l] + A[r] < sum)
l++;
else // A[i] + A[l] + A[r] > sum
r--;
}
}
// If we reach here, then no triplet was found
return false;
}
Here is my solution in Java:
package random;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
public class SumOfThreeEqualsZero {
static void getSumZero(Integer[] nums) {
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int i = 0; i < nums.length; i++) {
Integer key = nums[i];
if (map.containsKey(key))
map.put(key, map.get(key) + 1);
else
map.put(key, 1);
}
List<String> list = new ArrayList<String>();
// to get just one permutation of (i, j k) we will assume i <= j <= k
for (Integer i : map.keySet()) {
for (Integer j : map.keySet()) {
if (j >= i) {
if (i == j && i == 0) {
// i == j == k == 0 case
int count_i = map.get(i);
int count_i_choose_3 = count_i * (count_i - 1) * (count_i - 2) / 6;
for (int m = 0; m < count_i_choose_3; m++) {
list.add("[0, 0, 0]");
}
} else if (i == j) {
// i == j < k case
Integer k = -(i + j);
if (k > j) {
int count_i = map.get(i);
int count_i_choose_2 = count_i * (count_i - 1) / 2;
if (map.containsKey(k)) {
int times = count_i_choose_2 * map.get(k);
for (int m = 0; m < times; m++) {
list.add("[" + i + ", " + j + ", " + k + "]");
}
}
}
} else if (j > i) {
Integer k = -(i + j);
if (k == j) {
// i < j == k case
int count_j = map.get(j);
int count_j_choose_2 = count_j * (count_j - 1) / 2;
int times = count_j_choose_2 * map.get(i);
for (int m = 0; m < times; m++) {
list.add("[" + i + ", " + j + ", " + k + "]");
}
} else if (k > j && map.containsKey(k)) {
// i < j < k case
int times = map.get(i) * map.get(j) * map.get(k);
for (int m = 0; m < times; m++) {
list.add("[" + i + ", " + j + ", " + k + "]");
}
}
}
}
}
}
for (String str : list) {
System.out.println(str);
}
}
public static void main(String[] args) {
Integer[] a = { 2, 3, 1, -2, -1, 0, 2, -3, 0 };
getSumZero(a);
}
}
Three numbers sum to zero in 2 cases:
1) Two -ve numbers and a +ve number sum to 0
2) Two +ve numbers and a -ve number sum to 0.
So, sort the array in ascending order, that gives subarrays of +ve and -ve numbers in sorted orders.
1. Then run a double for-loop, from the start, on the negative sub-array, and for this -ve tuple, look for the corresponding positive number(that sums up to 0) in the positive sub-array from the end.
2. Also run a double for-loop, from the end, on the positive sub-array, and for this +ve tuple,
look for the corresponding negative number(that sums up to 0) in the negative sub-array from the start.
Worst-case time complexity: O(n^2), Space complexity O(1)
How can you find the corresponding number in O(1) in the double loops? It's impossible if you want keep memory usage in O(1) (other than the input). If you use a hash set, then the space complexity would be O(n). Also you must take zeros into account (if you don't, your algorithm will output duplicate combinations). Actually there are four cases where three numbers sum to zero:
1. n + n + p = 0
2. n + p + p = 0
3. n + z + p = 0
4. z + z + z = 0
where n is for negative, p for positive and z for zero. The corrected algorithm would be as follows:
1. Sort the input in ascending order. O(nlogn)
2. Find the indexes where zeros and positive numbers start. O(n)
3. Make a hash set S for negative and positive numbers. It is used to test whether a number is in the input. O(n) for both time and space.
4. Run a double for-loop on negative numbers. For a pair of two negative numbers (a, b), find the corresponding positive number c such that c = -(a + b) using the hash set S. Print the three numbers (a, b, c) if such c is found. O(n^2)
5. Run a double for-loop on positive numbers in a way similar to 4. O(n^2)
6. If there is a zero in the input, run a single loop on negative numbers. For each negative number a, find a positive number b using the hash set S which has the same absolute value, i.e. b = -a. Print (a, b, 0) if such b is found. O(n)
7. If there are three or more zeros, print (0, 0, 0). O(1)
Overall: O(n^2) for time, O(n) for space
EDIT: it still can output duplicate combinations. The algorithm should be modified to handle separately numbers appearing only once and twice or more.
Sort inputs first, the select first two a, b and then do the binary search to get the third one c with condition c=-(a+b). Java program as followed:
public void doCalculation(int a[]) {
Arrays.sort(a);
for (int i = 0; i < a.length; i++) {
for (int j = i + 1; j < a.length; j++) {
int k = Arrays.binarySearch(a, -(a[i] + a[j]));
if (k > j)
System.out.println(a[i] + " " + a[j] + " " + a[k]);
}
}
}
ArrayList<int[]> FindSumOfThreeUnique(int[] arr)
{
//sort the array
Arrays.sort(arr);
//unique value in order
Set<Integer> set = new LinkedHashSet<Integer>(Arrays.asList(arr));
//FindSumOfThree
return FindSumOfThree(set.toArray(),0);
}
ArrayList<int[]> FindSumOfThree(int[] arr, int sum)
{
ArrayList<int[]> results = new ArrayList<int[]>();
int i,j,k;
for(i = 0; i<arr.length(); i++)
for(j = 0; j<arr.length(); j++)
for(k = 0; k<arr.length(); k++)
if(arr[i]+arr[j]+arr[k] == sum)
{
results.add(new int[3]);
results.get(result.size())[0] = arr[i];
results.get(result.size())[1] = arr[j];
results.get(result.size())[2] = arr[k];
}
return results;
}
def find_zero_for_three(input)
input.sort!
input.each_with_index do |item, index|
i_start = index + 1
i_end = input.size - 1
while i_start < i_end do
if item * (-1) > input[i_start] + input[i_end]
i_start += 1
elsif item * (-1) < input[i_start] + input[i_end]
i_end -= 1
else
print [item, input[i_start], input[i_end]].join(",") + "\n"
i_start += 1
end
end
end
end
Solution: sort the input, then take the sum from the first and last element, try to find the opposite number in the list, if true, add the list, else move from tail of the list up to 0. After this, remove the first element, repeat process.
This has the assumption that first 2 and second 2 are different. Otherwise, needs to change list to set.
public class ZeroSum {
public List<List<Integer>> sumZero(List<Integer> input){
Collections.sort(input, Collections.reverseOrder());
List<List<Integer>> result = new ArrayList<List<Integer>>();
while(!input.isEmpty()){
int firstElement = input.get(0);
if(firstElement<=0) break;
int index = input.size()-1;
System.out.println("index is -> "+ index);
while(input.get(index)<0){
int twoSum = 0 - (firstElement + input.get(index));
if(input.contains(twoSum)) {
List<Integer> resultList = new ArrayList<Integer>();
resultList.add(firstElement);
resultList.add(input.get(index));
resultList.add(twoSum);
result.add(resultList);
}
index--;
}
input.remove(0);
}
return result;
}
}
package com.mj.algo.misc;
public class ZeroSumCombination {
void printCombinationZeroSum(int arr[], int n, int r)
{
int [] data= new int[r];
// Print all combination using temprary array 'data[]'
combinationUtilZeroSum(arr, n, r, 0, data, 0);
}
void combinationUtil(int arr[], int n, int r, int index, int data[], int i)
{
if(index == r){
for(int pos = 0; pos<r; pos++){
System.out.print(data[pos] + " ");
}
System.out.println();
return;
}
if(i>=n){
return;
}
data[index]=arr[i];
// current is included, put next at next location
combinationUtil(arr,n, r, index+1, data, i+1);
// current is excluded, replace it with next (Note that
// i+1 is passed, but index is not changed)
combinationUtil(arr,n, r, index, data, i+1);
}
void combinationUtilZeroSum(int arr[], int n, int r, int index, int data[], int i)
{
if(index == r){
if(checkSumtoZero(data)){
System.out.println();
}
return;
}
if(i>=n){
return;
}
data[index]=arr[i];
// current is included, put next at next location
combinationUtil(arr,n, r, index+1, data, i+1);
// current is excluded, replace it with next (Note that
// i+1 is passed, but index is not changed)
combinationUtil(arr,n, r, index, data, i+1);
}
private boolean checkSumtoZero(int[] input){
if(input == null){
return false;
}
int sum = 0;
for(int index = 0; index<input.length; index++){
sum = sum + input[index];
}
if(sum == 0){
return true;
}
return false;
}
private void findSumToZero(int[] input){
for(int index = 0; index<input.length; index++){
printCombinationZeroSum(input, input.length, index);
}
}
public static final void main(String args[]){
ZeroSumCombination zeroSumCombination = new ZeroSumCombination();
int[] input = {2, 3, 1, -2, -1, 0, 2, -3, 0};
zeroSumCombination.findSumToZero(input);
}
}
We can get down to O(n^2) worst case and no additional memory by using two pointers to scan the remainder of the array rather than searching for the missing element. I think we can do even better for a best case. However, duplicates are annoying. Your own example is confusing: you print both combinations of [3,0,-3] but you do not print all four combinations of [2,-2,0].
- Sir CodesALot April 19, 2014