Two Sum Problems
The Two Sum problem is a classic interview question: Given an array of integers and a target, return indices of two numbers that add up to the target. Using a HashMap, we can solve it in O(n) time.
Algorithm:
1. Iterate through array.
2. For each element, compute complement = target - current.
3. If complement exists in map, return indices.
4. Else, store current element and its index in map.
Java implementation:
public static int[] twoSum(int[] nums, int target) {
Map map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (map.containsKey(complement)) {
return new int[]{map.get(complement), i};
}
map.put(nums[i], i);
}
return new int[]{-1, -1};
}
Variants:
- Three Sum: sort array, use two pointers (but can also use HashMap).
- Two Sum with duplicates: need careful handling; usual solution returns indices of first occurrence.
- Two Sum in sorted array: can use two pointers without extra space.
Two Minute Drill
- Two Sum is solved using HashMap to store seen values and indices.
- Time O(n), space O(n).
- Complement = target - current.
- Classic interview problem, foundational for many other problems.
Need more clarification?
Drop us an email at career@quipoinfotech.com