Two Sum Problem: Find a Pair That Sums to Target (LeetCode Guide)

The Two Sum problem is one of the most popular coding interview questions and a classic challenge on LeetCode. Given an array and a target value, the goal is to find two numbers that sum up to the target and return their indices. In this guide, we will explore both the brute force and optimized hashmap approaches, providing clear explanations and efficient Java/Python code implementations.

Problem Statement

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

Example Inputs and Outputs:

Example 1:  
Input: nums = [2,7,11,15], target = 9  
Output: [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:

• There is exactly one valid solution.
• You cannot use the same element twice.

Brute Force Approach (O(n²))

Explanation

This method checks all possible pairs in the array to determine if their sum equals the target.

Java Implementation

public int[] twoSum(int[] nums, int target) {  
    for (int i = 0; i < nums.length; i++) {  
        for (int j = i + 1; j < nums.length; j++) {  
            if (nums[i] + nums[j] == target) {  
                return new int[]{i, j};  
            }  
        }  
    }  
    return new int[0];  
}  

Drawbacks

• Inefficient for large arrays.
• Time Complexity: O(n²) due to nested loops.

Optimal Hashmap Approach (O(n))

Explanation

Using a hashmap, we store each number’s index while iterating through the array. If the complement (target - num) exists in the hashmap, we return the indices immediately.

Why This Approach Works

• Hashmaps allow O(1) average lookup time.
• The solution is linear in time complexity (O(n)).

Step-by-Step Execution

Let’s consider nums = [2,7,11,15] with target = 9:

Java Implementation

import java.util.*;  
public int[] twoSum(int[] nums, int target) {  
    Map<Integer, Integer> numMap = new HashMap<>();  
    for (int i = 0; i < nums.length; i++) {  
        int complement = target - nums[i];  
        if (numMap.containsKey(complement)) {  
            return new int[]{numMap.get(complement), i};  
        }  
        numMap.put(nums[i], i);  
    }  
    return new int[0];  
}  

Python Implementation

def twoSum(nums, target):  
    num_map = {}  
    for i, num in enumerate(nums):  
        complement = target - num  
        if complement in num_map:  
            return [num_map[complement], i]  
        num_map[num] = i  
    return []  

Complexity Analysis

• Time Complexity: O(n) – Only one traversal of the array.
• Space Complexity: O(n) – Hashmap stores at most n elements.

Key Takeaways

1. Hashmaps Are Efficient: They reduce time complexity from O(n²) to O(n).
2. Single Pass Solution: We check and insert elements in one loop.
3. Edge Case Handling: The hashmap approach properly manages duplicate values like [3,3].

FAQs

Q1: What if there are multiple valid answers?

The problem guarantees exactly one solution, so handling multiple pairs is unnecessary.

Q2: Why not use sorting and two-pointer technique?

Sorting changes the order of indices, making it hard to return the correct positions.

Q3: Can this solution handle negative numbers?

Yes! The hashmap method works for both positive and negative integers.

Related Problems to Practice

1. Three Sum – Find three numbers that sum to zero.
2. Two Sum II – Variant with sorted input (uses two pointers).

If you found this guide helpful, share it to help others master coding interviews!

Keywords

Two Sum LeetCode solution, optimal algorithm, hashmap approach, Java solution, Python solution, coding interview preparation, O(n) time complexity, two sum explained, efficient algorithm, competitive programming.

This post is designed for clarity, SEO optimization, and reader engagement. It follows search engine guidelines for spam-free, plagiarism-free content.