Two Sum Algorithm Solution and Implementation

The Two Sum problem is a fundamental coding challenge that asks you to find two numbers in an array that add up to a target value. This solution explores the optimal hash map approach with detailed complexity analysis and implementation considerations for FAANG interviews.

1. Problem Restatement

Clarifying questions to ask the interviewer:

1. Can the input array be mutated, or should I preserve the original?
2. Are there any constraints on the size of the input array (e.g., max 10^5 elements)?
3. Do duplicate values in the input array affect the solution or are we looking for any valid pair?
4. What is the expected return format - indices, values, or something else?
5. Should I aim for O(n) time complexity or is O(n²) acceptable?

Restated problem: Given an array of integers and a target sum, find two distinct indices whose elements sum to the target value. Return the indices in any order.

Input/output specification:

• Input: int[] nums (array of integers) and int target
• Output: int[] containing two indices that sum to target
• Assumption: There exists exactly one valid solution and each element can only be used once

Key constraints:

• Array length between 2 and 10^4 elements
• Values can be negative, zero, or positive integers
• Target sum is within reasonable bounds for integer arithmetic

Hidden structure: The problem has a classic "complement" property where for any element nums[i], we're looking for target - nums[i] elsewhere in the array.

Assumptions made:

1. Input array is valid and contains at least 2 elements
2. There's always exactly one valid solution
3. The same element cannot be used twice (indices must be distinct)
4. Return format is 0-indexed array of indices
5. Array elements can be negative or zero

2. Pattern Recognition

The most likely pattern here is the Two Pointers or Hash Map approach for finding pairs that sum to a target value.

The wording "two numbers" and "sum to target" signals we're looking for a pair of elements that satisfy a specific relationship. The constraint that we need to return indices rather than just the values suggests we're dealing with a variation of the classic "Two Sum" problem.

This problem fits the pattern because:

1. We have a collection of numbers where we need to find a specific relationship between pairs
2. The requirement to return indices rather than values indicates we need to track element positions
3. The target sum creates a clear mathematical relationship that can be exploited

The core insight is that for any element in the array, we can calculate what the complement value should be (target - current_value), and then check if that complement has been seen before. This suggests either:

• Using a hash map to store previously seen values with their indices (O(n) time)
• Sorting the array and using two pointers (O(n log n) time)

The key insight is that we can solve this in linear time by using a hash map to store the complement relationship, avoiding the need for nested iteration.

This pattern is commonly seen in array problems where we're looking for pairs with specific sum or difference constraints, and the hash map approach is a standard optimization for such problems.

3. Approach Evolution

My first instinct is to use a brute force approach where I check every pair of elements to see if they sum to the target. This would be O(n²) time complexity because for each element, I'd need to scan the entire array again to find its complement. But that's inefficient and not optimal for a FAANG interview.

Let me think about how to optimize this. I notice that if I can somehow store already-seen elements and their indices, I can reduce the lookup time from O(n) to O(1). This suggests using a hash map to store elements as I traverse the array once.

I notice that if I maintain the invariant that my hash map only contains elements I've already processed, then for each current element, I can immediately check if its complement exists in the map. If it does, I've found my answer. This reduces the problem to a single pass through the array.

The key insight is that for any element at index i, if I've already seen (target - nums[i]), then I have found the two elements that sum to target. By storing each element and its index in a hash map as I process them, I can achieve O(n) time complexity.

This approach is optimal because we must at least look at each element once to determine if it's part of the solution, making O(n) time complexity unavoidable for this problem.

The algorithm works by:

1. Traversing the array once
2. For each element, checking if its complement exists in our hash map
3. If found, returning the indices immediately
4. If not found, storing the current element and its index in the hash map for future lookups

This maintains the crucial invariant that we never process an element twice and always have the correct indices to return.

4. Data Structure Choice

For the Two Sum problem, I'll use a HashMap as my primary data structure.

Primary Data Structures Used

1. HashMap<Integer, Integer> - stores previously seen values and their indices
2. int[] - to return the result indices

Why Each Data Structure Is Needed

The HashMap is essential because:

• It provides O(1) average time complexity for both lookups and insertions
• It allows me to store the relationship between values and their indices efficiently
• It enables the single-pass algorithm where I can check if the complement exists in constant time

The int[] array is needed to:

• Return the required indices in the expected format
• Store and return the final answer

Time and Space Impact

Time Complexity: O(n) for the single pass through the array Space Complexity: O(n) in worst case for storing all elements in the HashMap

Helper Structure

No additional helper structures are needed beyond the HashMap. The solution naturally builds on the fact that we only need to store values we've already processed, making the HashMap the most efficient choice for this specific problem pattern.

The HashMap approach is optimal here because:

• We need to quickly find if a complement exists
• We're trading space for time efficiency
• The problem's constraints (one valid answer exists) make this approach deterministic and complete

5. Algorithm Walkthrough

Let me trace through the algorithm with a concrete example to demonstrate how it works step-by-step.

Example: nums = [2, 7, 11, 15], target = 9

Step 1: Initialize empty HashMap: map = {}

• Process nums[0] = 2
• Calculate complement: complement = 9 - 2 = 7
• Check if 7 exists in map: No
• Add current element to map: map = {2: 0}

Step 2:

• Process nums[1] = 7
• Calculate complement: complement = 9 - 7 = 2
• Check if 2 exists in map: Yes, at index 0
• Return result: [0, 1]

The algorithm terminates here because we found the solution. The key insight is that for any element, if its complement already exists in our map, we've found our answer.

Edge case handling:

• If input is empty or has only one element, we return null/empty array
• If duplicates exist (like nums = [3, 3], target = 6), we still correctly return indices [0, 1] because we only check for complement existence before adding current element to map
• The order matters: we must check for complement before adding to avoid false matches with the same element

Why it works: The algorithm maintains the invariant that for any position i, we've already processed all elements before index i. When we check if the complement exists in our map, we're guaranteed to find a valid previous element that sums with current element to reach the target. This ensures correctness while maintaining linear time complexity.

public int[] twoSum(int[] nums, int target) {
    // HashMap to store value -> index mapping
    Map<Integer, Integer> map = new HashMap<>();
    
    // Iterate through each element
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        
        // If complement exists in map, we found our answer
        if (map.containsKey(complement)) {
            return new int[] {map.get(complement), i};
        }
        
        // Add current element to map for future lookups
        map.put(nums[i], i);
    }
    
    // No solution found (should not happen per problem constraints)
    return new int[] {};
}

6. Java Solution

public class TwoSum {
    public int[] twoSum(int[] nums, int target) {
        // HashMap to store value -> index mapping
        Map<Integer, Integer> numToIndex = new HashMap<>();
        
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            
            // If complement exists in map, we found our answer
            if (numToIndex.containsKey(complement)) {
                return new int[] {numToIndex.get(complement), i};
            }
            
            // Store current number and its index
            numToIndex.put(nums[i], i);
        }
        
        // This should never be reached given problem constraints
        throw new IllegalArgumentException("No two sum solution exists");
    }
}

The solution uses a hash map to achieve O(n) time complexity. For each element, we calculate its complement (target - current number) and check if that complement has been seen before. If yes, we've found our pair. Otherwise, we store the current number and its index in the map for future lookups.

The key insight is that we only need to look backwards, not forwards - so storing elements as we traverse works perfectly for finding the pair that sums to target.

7. Complexity Analysis

Time Complexity: O(n)

The algorithm makes a single pass through the input array, performing constant-time operations (hash map lookups and insertions) for each element. Since we process each element exactly once, the overall time complexity is linear in the size of the input array.

Space Complexity: O(n)

In the worst case, we store all elements of the input array in the hash map before finding a valid pair. This occurs when no valid pair exists, or when the solution requires storing nearly all elements to find a match. Therefore, the space complexity is linear in the size of the input array.

Why these bounds are correct:

The time complexity analysis is straightforward because each hash map operation (put and get) has an average time complexity of O(1), and we perform a constant number of such operations per input element. The space complexity follows directly from the fact that we might need to store all elements in our hash map before finding a solution.

Optimality:

This is optimal for the two-sum problem when we're looking for a solution that returns indices rather than just checking if a pair exists. Any algorithm that needs to examine all possible pairs would require at least O(n²) time, and since we can solve it in O(n) time using a hash map, our solution is near-optimal. The O(n) time complexity matches the theoretical lower bound for this problem when we need to return specific indices rather than just a boolean result.

8. Edge Cases & Pitfalls

Empty and Minimal Inputs

• Empty array: Should return empty result or throw appropriate exception based on requirements
• Single element array: Cannot form a valid two-sum pair, so should handle gracefully
• Two elements: Should correctly identify the pair if it exists

Duplicate Values and Repeated States

• Duplicate numbers: The solution must handle cases where the same value appears multiple times in the array
• Target sum with duplicates: When nums = [2, 2, 4] and target = 4, we want indices [0, 1] not [0, 0]
• Zero values: Special handling needed for cases like nums = [0, 4, 3, 0] with target = 0

Boundary Conditions

• Integer overflow: When adding two large numbers, ensure we don't overflow the integer range
• Negative numbers: The algorithm must work correctly with arrays containing negative values
• Large input sizes: For very large arrays, memory usage becomes a concern

Common Implementation Mistakes

• Incorrect index tracking: Using wrong indices when updating hash map or returning result
• Not checking for same element twice: When nums[i] + nums[i] = target, we must ensure we don't return the same index twice
• HashMap key collision: Though unlikely with integers, improper handling of hash collisions could cause issues
• Return order inconsistency: Some implementations return indices in ascending or descending order inconsistently

Implementation-specific Pitfalls

// Common mistake - not handling same element twice
if (map.containsKey(target - nums[i]) && map.get(target - nums[i]) != i) {
    // This check prevents using the same element twice
}

// Another mistake - incorrect return order
return new int[]{map.get(target - nums[i]), i}; // Should be in ascending index order

The solution must ensure that when the same element is used twice (e.g., nums[i] = 2 and target = 4), we don't return the same index twice, and that we maintain consistent return ordering.

9. Alternative Approaches

There are several alternative approaches to solving the Two Sum problem, each with different trade-offs:

Brute Force Approach: The most straightforward alternative is to use nested loops to check every pair of elements. For each element at index i, iterate through all elements at indices j > i to see if their sum equals the target. This approach has O(n²) time complexity and O(1) space complexity. While simple to implement, it's inefficient for large inputs and doesn't leverage any structural properties of the problem.

Sorting + Two Pointers: Another approach involves sorting the array first (O(n log n) time) and then using two pointers technique - one starting from the beginning and one from the end. If the sum is too small, move the left pointer right; if too large, move the right pointer left. This approach works well when we don't need to preserve original indices but requires O(n log n) time due to sorting.

HashMap with Index Tracking: A variation of the hash map approach that stores both values and their indices in a HashMap. This allows us to return the actual indices rather than just checking for existence. The time complexity remains O(n) but with slightly higher constant factors due to storing additional index information.

Binary Search Approach: If the array is sorted, we can iterate through each element and use binary search to find if target - current_element exists in the remaining array. This approach has O(n log n) time complexity due to binary search operations and is less efficient than the hash map solution.

The hash map approach remains the preferred solution because it provides optimal O(n) time complexity with clean, readable implementation that handles all edge cases naturally. The alternatives either introduce unnecessary overhead or don't achieve the optimal complexity bound.

The chosen solution is optimal for this problem because:

1. It achieves O(n) time complexity, which is the theoretical lower bound for this problem since we must examine each element at least once
2. It uses O(n) space in the worst case, which is also optimal for maintaining a lookup structure
3. It handles all edge cases including duplicates, negative numbers, and empty arrays elegantly

10. Test Cases

public class TwoSumTestCases {
    public static void main(String[] args) {
        // Test case 1: Basic valid case
        int[] nums1 = {2, 7, 11, 15};
        int target1 = 9;
        // Expected: [0, 1] or [1, 0]
        
        // Test case 2: Negative numbers
        int[] nums2 = {-1, 0, 1, 2};
        int target2 = 1;
        // Expected: [0, 3] or [3, 0]
        
        // Test case 3: Duplicate values
        int[] nums3 = {3, 3};
        int target3 = 6;
        // Expected: [0, 1] or [1, 0]
        
        // Test case 4: Single element array (edge case)
        int[] nums4 = {5};
        int target4 = 10;
        // Expected: null (no solution)
        
        // Test case 5: Empty array (edge case)
        int[] nums5 = {};
        int target5 = 0;
        // Expected: null (no solution)
        
        // Test case 6: Target at boundary
        int[] nums6 = {1, 2, 3, 4, 5};
        int target6 = 10;
        // Expected: [1, 4] or [4, 1]
        
        // Test case 7: Large numbers
        int[] nums7 = {1000000000, 2000000000};
        int target7 = 3000000000L;
        // Expected: [0, 1] or [1, 0]
    }
}

Sample Test Cases:

Basic Valid Case: nums = [2, 7, 11, 15], target = 9 → Expected: [0, 1]

Negative Numbers: nums = [-1, 0, 1, 2], target = 1 → Expected: [0, 3]

Duplicate Values: nums = [3, 3], target = 6 → Expected: [0, 1]

Edge Cases:

• Empty array: nums = [], target = 0 → Expected: null
• Single element: nums = [5], target = 10 → Expected: null

Boundary Case: nums = [1, 2, 3, 4, 5], target = 10 → Expected: [1, 4]

Large Numbers: nums = [1000000000, 2000000000], target = 3000000000 → Expected: [0, 1]

The test cases cover all major scenarios including edge cases, duplicates, negative numbers, and boundary conditions that could break a naive implementation.

11. Final Summary

The core insight is to use a hash map to achieve O(n) time complexity by trading space for speed, eliminating the need for nested loops. This solution efficiently handles the two-sum problem by storing previously seen values and their indices, allowing us to find the complement in constant time. The approach is optimal for the given constraints and demonstrates a clean balance between time complexity, space usage, and code readability that would impress FAANG interviewers.