1. Two Sum | LeetCode in C# | Hash Table Solution

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.

References

• Two Sum - LeetCode