Two Sum

Easyarrayhash-table
Category: Array & Hashing
Companies that ask this question:
AmazonGoogleFacebookMicrosoftApple
LeetCode →NeetCode →

Approach

Problem Statement

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

You may assume that each input has exactly one solution, and you cannot use the same element twice.

Example:

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

Intuition

The brute force approach would check every pair of numbers, resulting in O(n²) time complexity. We can do better!

The key insight is to use a hash table to remember numbers we've seen and their indices. As we iterate through the array:

  1. For each number, calculate its complement (target - current number)
  2. Check if the complement exists in our hash table
  3. If yes, we found our pair!
  4. If no, store the current number and its index for future lookups

This transforms the problem from "find two numbers that sum to target" to "does the complement of this number exist?"

Pattern Recognition

This is a classic Array + Hash Table problem. The hash table trades space for time:

  • Space: O(n) to store elements
  • Time: O(1) lookups instead of O(n) nested loops

Edge Cases

  • Minimum array size: The array will have at least 2 elements (guaranteed solution)
  • Negative numbers: The algorithm works regardless of sign
  • Duplicate values: We can use the same value twice if they're at different indices

Complexity Analysis

  • Time Complexity: O(n) - Single pass through the array
  • Space Complexity: O(n) - Hash table stores up to n elements

Solution

java
1class Solution {
2    public int[] twoSum(int[] nums, int target) {
3        // Hash table to store value -> index mapping
4        Map<Integer, Integer> seen = new HashMap<>();
5
6        for (int i = 0; i < nums.length; i++) {
7            int complement = target - nums[i];
8
9            // Check if complement exists in our hash table
10            if (seen.containsKey(complement)) {
11                // Found the pair! Return both indices
12                return new int[] { seen.get(complement), i };
13            }
14
15            // Store current number and its index for future lookups
16            seen.put(nums[i], i);
17        }
18
19        // Should never reach here (problem guarantees a solution)
20        throw new IllegalArgumentException("No solution found");
21    }
22}
23
Loading visualizer...