00001. Leetcode: Two Sum – Problem and Solutions

The Two Sum Problem

The Two Sum problem is a classic algorithmic problem from leetcode that goes like this: given an array of integers nums and an integer target, return indices of the two numbers such that they add up to the target. You may assume that each input would have exactly one solution, and you may not use the same element twice.

Solution 1: Two Sum with Hash Table

public class Solution {
    public int[] TwoSum(int[] nums, int target) {
        Dictionary<int, int> table = new Dictionary<int, int>();
        for (int i = 0; i < nums.Length; i++)
        {
            int complement = target - nums[i];
            if (table.ContainsKey(complement))
            {
                return new int[] { table[complement], i };
            }
            table[nums[i]] = i;
        }
        return null;
    }
}

Explanation:

This solution utilizes a hash table to store the complement of each element along with its index. The algorithm iterates through the array, and for each element, it checks if the complement (the difference between the target and the current element) exists in the hash table. If it does, the function returns the indices of the two elements that add up to the target.

Pros:

• Time complexity: O(n) – the algorithm makes a single pass through the array.
• Space complexity: O(n) – additional space is used for the hash table.

Cons:

• Relies on additional space due to the hash table.

Solution 2: Two Sum with Nested Loop

public class Solution {
    public int[] TwoSum(int[] nums, int target) {

            int n = nums.Length;

            for (int i = 0; i < n - 1; i++)
            {
                for (int j = i + 1; j < n; j++)
                {      
                    if (nums[i] + nums[j] == target)
                    {
                        return new int[] { i, j };
                    }
                }
            }
            return null;
    }
}

Explanation:

This solution uses a nested loop to iterate through pairs of elements in the array, checking if their sum equals the target. If a match is found, the function returns the indices of the two elements.

Pros:

• Simple and easy to understand.
• No additional space used.

Cons:

• Time complexity: O(n^2) – the algorithm has nested loops, resulting in higher time complexity for larger arrays.

Conclusion

Both solutions provide a valid approach to solving the Two Sum problem, but the choice between them depends on the specific requirements of your use case. The hash table solution offers a more efficient O(n) time complexity, making it suitable for larger datasets, while the nested loop solution is simpler and may be sufficient for smaller arrays.

Remember to consider the trade-offs between time and space complexity when choosing an algorithm for your particular scenario.