Leetcode Problem 1 - Two Sum

Two Sum

Difficulty: Easy

Given an array of integers nums and an integer target, return the indices of two numbers that add up to target.

Constraints:

• Each input has exactly one solution.
• 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: nums[0] + nums[1] == 9, so 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 <= 10^4
• -10^9 <= nums[i] <= 10^9
• -10^9 <= target <= 10^9
• Only one valid answer exists.

Follow-up:

Can you solve this problem with a time complexity better than O(n²)?

---

Solution Approaches

1. Brute Force Approach (O(n²) Time Complexity)

This approach checks every possible pair in the array.

Algorithm:

1. Use two nested loops to check all pairs.
2. If a pair sums up to target, return their indices.

Code (C#)

using System;

public class Solution {
    public int[] TwoSumBruteForce(int[] nums, int target) {
        int n = nums.Length;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (nums[i] + nums[j] == target) {
                    return new int[] { i, j };
                }
            }
        }
        return new int[] {}; // This should never be reached per problem constraints
    }
}

// Example Usage
class Program {
    static void Main() {
        Solution solution = new Solution();
        int[] nums = {2, 7, 11, 15};
        int target = 9;
        int[] result = solution.TwoSumBruteForce(nums, target);
        Console.WriteLine($"[{result[0]}, {result[1]}]");
    }
}

---

2. Optimized Approach (O(n) Time Complexity using HashMap)

Using a hash table (Dictionary) to store numbers and their indices allows O(1) lookup time, reducing time complexity.

Algorithm:

1. Iterate through the array.
2. For each number, compute its complement: complement = target - num.
3. Check if the complement exists in the dictionary.
4. If found, return the indices; otherwise, store the number in the dictionary.

Code (C#)

using System;
using System.Collections.Generic;

public class Solution {
    public int[] TwoSumOptimized(int[] nums, int target) {
        Dictionary<int, int> numIndexMap = new Dictionary<int, int>();

        for (int i = 0; i < nums.Length; i++) {
            int complement = target - nums[i];

            if (numIndexMap.ContainsKey(complement)) {
                return new int[] { numIndexMap[complement], i };
            }
            numIndexMap[nums[i]] = i;
        }
        
        return new int[] {}; // This should never be reached per problem constraints
    }
}

// Example Usage
class Program {
    static void Main() {
        Solution solution = new Solution();
        int[] nums = {2, 7, 11, 15};
        int target = 9;
        int[] result = solution.TwoSumOptimized(nums, target);
        Console.WriteLine($"[{result[0]}, {result[1]}]");
    }
}

---

Complexity Comparison

Approach	Time Complexity	Space Complexity
Brute Force	O(n²)	O(1)
Optimized (HashMap)	O(n)	O(n)

Why the Optimized Approach is Better (O(n)) 🚀

• The brute force approach checks all pairs, leading to O(n²) time complexity.
• Using a hash table (Dictionary) allows O(1) lookup time, making the solution O(n).
• The optimized approach traverses the array only once, making it efficient.

This optimized approach is the best solution for the Two Sum problem! 🚀