Two Sum Editorial

Practice Problem Link: Two Sum | Practice Problem

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given an array A and an integer target, find the indices of the two numbers in the array whose sum is equal to the given target.

Naive Approach

We can iterate over all possible pairs of elements in the array, and check if their sum is equal to the target sum. If yes, we can return the indices of those two pairs.

Analysis

• Time Complexity: O(n²)
• Space Complexity: O(1)

Implementation

C++

pair<int,int> twoSum(vector<int> &A, int target) {
   pair<int, int> indicesOfSum;
   for (int i = 0; i < A.size(); i++) {
       for (int j = i + 1; j < A.size(); j++) {
           if(A[i] + A[j] == target) {
               return {i, j};
           }
       }
   }
}

Java

class Solution {
   int[] twoSum(int[] A, int target) {
       int indicesOfSum[] = new int[2];
       for (int i = 0; i < A.length; i++) {
           for (int j = i + 1; j < A.length; j++) {
               if(A[i] + A[j] == target) {
                   indicesOfSum[0] = i;
                   indicesOfSum[1] = j;
                   return indicesOfSum;
               }
           }
       }
       return indicesOfSum;
   }
}

Improved Approach

We observe that sorting the array doesn’t change the answer. So, we can sort the array, and use the 2 pointers technique to find the target sum.

• We keep two pointers, left and right at the end-points of the array.
• If the sum of the values at those points is equal to the target sum, we return the pointers.
• Else if the sum is less than the target, we increment the left pointer by one and check again.
• Similarly, if the sum is greater than the target, we decrement the right pointer by one, and check again, till we get our solution.

Analysis

• Time Complexity: O(n * logn)
• Space Complexity: O(n) // for auxiliary array

Implementation

C++

pair<int,int> twoSum(vector<int> &A, int target) {
   vector<pair<int, int>> sortedAux;
   for (int i = 0; i < A.size(); i++) {
       sortedAux.push_back({A[i], i});
   }
   sort(sortedAux.begin(), sortedAux.end());
   int left = 0, right = A.size() - 1;
   while (left < right) {
       if(sortedAux[left].first + sortedAux[right].first == target) {
           return {sortedAux[left].second, sortedAux[right].second};
       } else if(sortedAux[left].first + sortedAux[right].first < target) {
           left++;
       } else {
           right--;
       }
   }
}

Java

class Solution {
   class Pair implements Comparator<Pair> {
       int first, second;
       Pair(int first,int second) {
           this.first = first;
           this.second = second;
       }
       @Override
       public int compare(Solution.Pair o1, Solution.Pair o2) {
           return ((int) (o1.first - o2.first));
       }
       
   }
   int[] twoSum(int[] A, int target) {
       ArrayList<Pair> sortedAux = new ArrayList<>();
       int n = A.length;
       for (int i = 0; i < n; i++) {
           sortedAux.add(new Pair(A[i],i));
       }
       Collections.sort(sortedAux, new Pair());
       int first = 0, last = n - 1;
       int answer[] = new int[2];
       while (first < last) {
           int sum = sortedAux.get(first).first + sortedAux.get(last).first;
           if(sum == target){
               answer[0] = sortedAux.get(first).second;
               answer[1] = sortedAux.get(last).second;
               return answer;
           } else if(sum < target) {
               first++;
           } else {
               last--;
           }
       }
       return answer;
   }
}

Optimal Approach

To solve this problem in linear time, we can use hashing. We can observe that if A[i] and A[j] make up the target sum, that basically means that A[j] = target - A[i], so both A[i] and target - A[i] should be present in the array. We can hash all the elements in the array beforehand, to check for such valid pairs in linear time.

Analysis

• Time Complexity: O(n)
• Space Complexity: O(n)

Implementation

C++

pair<int,int> twoSum(vector<int> &A, int target) {
    unordered_map<int, int> hashMap;
	for (int i = A.size() - 1; i >= 0; i--) {
		auto it = hashMap.find(target - A[i]);
		if (it != hashMap.end()) {
			return make_pair(it->second, i);
		}
		hashMap[A[i]] = i;
	}
}

Java

class Solution {
	int[] twoSum(int[] A, int target) {
		Map<Integer, Integer> hashMap = new HashMap<Integer, Integer>();
		int[] ans = new int[2];
		for (int i = A.length - 1; i >= 0; i--) {
			int indexPrev = hashMap.getOrDefault(target - A[i], -1);
			if (indexPrev > -1) {
				ans[0] = indexPrev;
				ans[1] = i;
				break;
			}
			hashMap.put(A[i], i);
		}
		return ans;
	}
}