The "Two Sum" problem is a popular coding challenge that tests your ability to find pairs in an array that sum up to a specific target. Letβs dive into various methods to solve this problem efficiently.
Problem Statement π―
Given an array of integers nums
and an integer target
, return indices of the two numbers such that they add up to target
. You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example
Input: nums = [2, 7, 11, 15], target = 9
Output: [0, 1]
(because nums[0] + nums[1] == 9
)
1. Brute Force Approach βοΈ
Python:
def two_sum_bruteforce(nums, target):
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
if nums[i] + nums[j] == target:
return [i, j]
return []
Java:
public int[] twoSumBruteforce(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 new int[] {}; // If no solution is found
}
Explanation:
- Iterate over each pair of indices and check if their sum equals the target.
2. Hash Map Approach π
Python:
def two_sum_hash_map(nums, target):
num_to_index = {}
for i, num in enumerate(nums):
complement = target - num
if complement in num_to_index:
return [num_to_index[complement], i]
num_to_index[num] = i
return []
Java:
import java.util.HashMap;
public int[] twoSumHashMap(int[] nums, int target) {
HashMap<Integer, Integer> numToIndex = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (numToIndex.containsKey(complement)) {
return new int[] { numToIndex.get(complement), i };
}
numToIndex.put(nums[i], i);
}
return new int[] {}; // If no solution is found
}
Explanation:
- Use a hash map to store the index of each number.
- For each element, check if its complement (target - current number) exists in the hash map.
3. Two-Pointer Approach πββοΈ
Python:
def two_sum_two_pointer(nums, target):
nums_with_index = list(enumerate(nums))
nums_with_index.sort(key=lambda x: x[1])
left, right = 0, len(nums) - 1
while left < right:
current_sum = nums_with_index[left][1] + nums_with_index[right][1]
if current_sum == target:
return [nums_with_index[left][0], nums_with_index[right][0]]
elif current_sum < target:
left += 1
else:
right -= 1
return []
Java:
import java.util.Arrays;
import java.util.Comparator;
public int[] twoSumTwoPointer(int[] nums, int target) {
int[][] numsWithIndex = new int[nums.length][2];
for (int i = 0; i < nums.length; i++) {
numsWithIndex[i][0] = i;
numsWithIndex[i][1] = nums[i];
}
Arrays.sort(numsWithIndex, Comparator.comparingInt(a -> a[1]));
int left = 0, right = nums.length - 1;
while (left < right) {
int currentSum = numsWithIndex[left][1] + numsWithIndex[right][1];
if (currentSum == target) {
return new int[] { numsWithIndex[left][0], numsWithIndex[right][0] };
} else if (currentSum < target) {
left++;
} else {
right--;
}
}
return new int[] {}; // If no solution is found
}
Explanation:
- First, sort the array while keeping track of the original indices.
- Use two pointers to find the pair that sums up to the target.
4. Optimized Space Approach π
Python:
def two_sum_optimized(nums, target):
seen = {}
for i, num in enumerate(nums):
diff = target - num
if diff in seen:
return [seen[diff], i]
seen[num] = i
return []
Java:
import java.util.HashMap;
public int[] twoSumOptimized(int[] nums, int target) {
HashMap<Integer, Integer> seen = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int diff = target - nums[i];
if (seen.containsKey(diff)) {
return new int[] { seen.get(diff), i };
}
seen.put(nums[i], i);
}
return new int[] {}; // If no solution is found
}
Explanation:
- Iterate through the array while maintaining a hash map of the numbers seen so far.
- Check if the complement of the current number exists in the hash map.
Conclusion π
These methods offer various ways to solve the Two Sum problem, each with its advantages and trade-offs. Whether you prefer the straightforward brute force method or the efficient hash map approach, understanding these techniques will enhance your problem-solving skills.
Feel free to share your thoughts or additional methods in the comments!
Connect with me:
- LinkedIn: https://www.linkedin.com/in/nikko-ferwelo-358b11213
- GitHub: https://github.com/NullVoidKage
Happy coding! π
Top comments (0)