Two Sum | LeetCode in C# | Hash Table Solution
Another solution for Two Sum problem on LeetCode by utilizing Hash Table for faster process
Problem
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.
You can return the answer in any order.
Example 1:
- Input:
nums = [2,7,11,15], target = 9 - Output:
[0,1] - Explanation: Because
nums[0] + nums[1] == 9, we return[0, 1].
Example 2:
- Input:
nums = [3,2,4], target = 6 - Output:
[1,2]
Example 3:
- Input:
nums = [3,3], target = 6 - Output:
[0,1]
Constraints:
2 <= nums.length <= 104-109 <= nums[i] <= 109-109 <= target <= 109- Only one valid answer exists.
Follow-up: Can you come up with an algorithm that is less than O(n2) time complexity?
Intuition
Upon revisiting the Two Sum problem, my initial thought was that while a brute force method can solve it, there should be a more efficient way to leverage the data itself to keep track of needed values. A hash table seemed promising, as it could allow for quick look-ups to find whether the complement needed to reach the target sum has been encountered before.
Approach
The approach involves using a dictionary to store each number in the array as a key, and its index as the value. As we iterate through the array, for each number ‘a’, we calculate its complement ‘b’ such that b = target - a. We then check if ‘b’ already exists in the dictionary. If it does, it means we have found the two numbers that make up the target sum, and we can return their indices. If ‘b’ is not found, we add ‘a’ to the dictionary with its index. This way, we only traverse the list once, making it much more efficient than the brute force approach.
Complexity
- Time complexity: The time complexity is \(O(n)\), where ’n’ is the number of elements in the input array, since we make a single pass over the array and look up operations have constant time complexity.
- Space complexity: The space complexity is also \(O(n)\) because, in the worst case, we might store all the numbers in the dictionary.
Code
public class Solution {
public int[] TwoSum(int[] nums, int target) {
var dict = new Dictionary<int, int>();
for(var i=0; i<nums.Length; i++) {
var a = nums[i];
var b = target - a;
if(dict.ContainsKey(b))
return new int[]{dict[b], i};
if(!dict.ContainsKey(a))
dict.Add(a, i);
}
return new int[]{0,1};
}
}Video
Conclusion
This approach efficiently solves the problem by reducing the number of operations needed to find the solution, making it suitable for larger datasets compared to the brute force method. Using a dictionary allows for fast look-up times to check the presence of complements, thereby optimizing the solution.
