Skip to main content

Two Sum

LeetCode 1 | Difficulty: Easy​

Easy

Problem Description​

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.

Constraints​

  • 2 <= nums.length <= 10^4
  • -10^9 <= nums[i] <= 10^9
  • -10^9 <= target <= 10^9
  • Only one valid answer exists.

Examples​

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: nums[0] + nums[1] = 2 + 7 = 9

Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

Approach​

Approach 1: Brute Force​

Check every pair of elements:

  • For each element, scan all remaining elements
  • Time: $O(n^2)$, Space: $O(1)$

Approach 2: Hash Map (Optimal)​

Use a hash map to store seen values → their indices. For each nums[i], check if target - nums[i] exists in the map.

Key Insight: Instead of looking for two numbers that sum to target, look for the complement of the current number.

Solution: Hash Map (Optimal)​

O(n) Solution using Dictionary
public class Solution {
    public int[] TwoSum(int[] nums, int target) {
        Dictionary<int, int> map = new Dictionary<int, int>();
        
        for (int i = 0; i < nums.Length; i++) {
            int complement = target - nums[i];
            
            if (map.ContainsKey(complement)) {
                return new int[] { map[complement], i };
            }
            
            map[nums[i]] = i;
        }
        
        return new int[] {}; // No solution found
    }
}

Solution: List-based Lookup​

This was my original accepted submission:

Accepted Submission
public class Solution {
    public int[] TwoSum(int[] nums, int target) {
        List<int> vals = new List<int>();
        int[] result = new int[2];
        for (int i = 0; i < nums.Length; i++) {
            int index = vals.IndexOf(target - nums[i]);
            if (index >= 0) {
                result[0] = index;
                result[1] = i;
            }
            else vals.Add(nums[i]);
        }
        return result;
    }
}
Performance Note

List.IndexOf() is $O(n)$, making this approach $O(n^2)$ overall. Using a Dictionary reduces lookup to $O(1)$.

Complexity Analysis​

ApproachTimeSpaceNotes
Brute Force$O(n^2)$$O(1)$Two nested loops
List Lookup$O(n^2)$$O(n)$IndexOf is $O(n)$
Hash Map$O(n)$$O(n)$Single pass, $O(1)$ lookup

Interview Tips​

Key Points
  • Always start with brute force and then optimize — this shows your problem-solving process
  • The hash map approach is a fundamental pattern that appears in many problems (3Sum, 4Sum, subarray sum, etc.)
  • Ask: "Can there be duplicate values?" — Yes, but only one valid pair exists
  • Ask: "Can I modify the input?" — If yes, sorting + two pointers is another $O(n \log n)$ approach

Follow-up Questions​

  • What if the array is sorted? → Use two pointers: $O(n)$ time, $O(1)$ space
  • What if you need to return all pairs? → Continue iterating instead of returning early
  • What about 3Sum? → Sort + fix one element + two pointers