DEV Community

Cover image for 1. Two Sum | LeetCode in C# | Hash Table Solution
junian
junian

Posted on • Originally published at junian.net on

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};
    }
}
Enter fullscreen mode Exit fullscreen mode

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

AWS Security LIVE!

Tune in for AWS Security LIVE!

Join AWS Security LIVE! for expert insights and actionable tips to protect your organization and keep security teams prepared.

Learn More

Top comments (0)

AWS Security LIVE!

Tune in for AWS Security LIVE!

Join AWS Security LIVE! for expert insights and actionable tips to protect your organization and keep security teams prepared.

Learn More

👋 Kindness is contagious

Dive into an ocean of knowledge with this thought-provoking post, revered deeply within the supportive DEV Community. Developers of all levels are welcome to join and enhance our collective intelligence.

Saying a simple "thank you" can brighten someone's day. Share your gratitude in the comments below!

On DEV, sharing ideas eases our path and fortifies our community connections. Found this helpful? Sending a quick thanks to the author can be profoundly valued.

Okay