CareerCup

Optimized solution using Bucket sort based approach. The integer includes negative integer as well.

For example, if the array is [3, 5, 2, -4, 8, 11] and the sum is 7, your program should return [[11, -4], [2, 5]] because 11 + -4 = 7 and 2 + 5 = 7.


My approach

/**
* Approach 1: Print all the subset and find the matching sum
* Approach 2: Apply subset sum problem which 0(cnt * a.length)
* Approach 3: 0(n) how is it possible. Bucket sort based logic
*/

Approach 3 implementation is here

public class TwoSumProblem {

private static void findTwoSum(int[] a, int cnt)
{

int[] b = new int[100];
for(int i = 0 ; i < a.length ; i++)
{
b[a[i] + 50] = b[a[i] + 50] + 1;
}
int t1 = 0;
for(int i = 0 ; i < a.length ; i++)
{
if(b[a[i] + 50] == 1 && b[cnt - a[i] + 50] == 1 && cnt - a[i] + 50 != a[i] + 50)
{
b[a[i] + 50] = b[a[i] + 50] - 1;
b[cnt - a[i] + 50] = b[cnt - a[i] + 50] - 1;
t1 = cnt - a[i];
System.out.println("Pair is " + a[i] + " and " + t1);
}

}
}

public static void main(String[] args) {
int[] a = {3, 5, 2, -4, 8, 11} ;
findTwoSum(a, 7);

}

}

# This solution supports negative integers and elements duplication (e.g. [3, 5, 2, -4, 8, -4, 11, 11]).
# With `n` = number of elements in arr and `m` = number of indices of a certain complement
# Time complexity = O(n * m)
# Space complexity = O(n * m)
def twoSum(arr, sum):
    compl = {}
    result = []
    for i in range(len(arr)):          # O(n)
        n = arr[i]
        if sum-n in compl:
            for j in compl[sum-n]:     # O(m)
                result.append([arr[j], n])
        if n in compl:
            compl[n].append(i)
        else:
            compl[n] = [i]
    return result

// C++ solution:
vector<pair<int,int>> twoSum(const vector<int> & A,int B) {
	unordered_map<int> ump;
	vector<pair<int,int>> result;
	for(auto e:A) {
		if(ump.find(e)!=ump.end()) result.emplace({B-e,e});
		else	ump.emplace(B-e);
	}
	return result;
}