Two Sum Algorithm Solutions and Optimization Strategies

The Two Sum problem is a fundamental coding challenge that tests understanding of array traversal, hash table operations, and algorithm optimization. This write-up presents multiple solution approaches with detailed complexity analysis and practical implementation considerations for FAANG interviews.

1. Pattern Restatement

Clarifying questions to ask the interviewer:

1. What is the size constraint on the input array? (e.g., up to 10⁶ elements)
2. Are duplicates allowed in the input array?
3. What format should the return value take? (indices, values, or just a boolean?)
4. Can I modify the input array during processing?
5. What is the target time complexity for follow-ups? (e.g., O(n) preferred)

Restatement of the pattern: The Two Sum problem asks us to find two distinct elements in an array whose sum equals a given target value. It's a canonical pattern for identifying pairs that satisfy a specific arithmetic relationship, often requiring efficient lookup mechanisms to avoid brute-force nested iteration.

Signal words and constraint shape: Key signal words include "sum", "pair", "two elements", and "target". The constraint shape typically involves a fixed-size array with integer values where we must return indices or boolean confirmation of existence. The problem often appears in variants like "Two Sum II" (sorted array) or "Three Sum".

Assumptions made:

• Input array contains at least two elements (to form a valid pair)
• Target value is an integer
• We're looking for distinct indices (not the same element used twice)
• The problem usually assumes one valid answer exists, or all valid answers should be returned

Scenario suitability: This pattern is best suited for static input scenarios where all data is available upfront. It's less appropriate for streaming data where elements arrive continuously, though it can be adapted with sliding window techniques in some variants.

The core insight is that we can reduce the problem from O(n²) brute-force search to O(n) using hash maps for constant-time lookups, making it a fundamental pattern in algorithmic optimization.

2. When to Use This Pattern

Signal words and constraint shapes in a problem statement that indicate this pattern:

• "Two numbers that sum to target"
• "Find a pair with specific sum"
• "Return indices of two elements"
• "Array of integers" with "target sum"
• "Exactly one valid answer exists"

Why this pattern fits better than the most common alternatives: This pattern is distinct from general search problems because it requires finding a specific relationship (sum of exactly two elements) rather than just locating individual elements. Compared to brute force O(n²) nested loops, the two-sum pattern leverages sorting or hash maps to achieve O(n log n) or O(n) time respectively. Unlike sliding window problems, it doesn't require the array to be sorted or have specific ordering properties.

Conditions where a variation or related pattern applies instead:

• For 3-sum or K-sum problems, use sorting + two-pointer technique or hash map approaches
• For finding any subarray with sum K, use prefix sum with hash maps
• For unsorted arrays where we only need to detect existence of a pair, hash set approach is optimal
• For sorted arrays, two-pointer technique is more efficient than hash map

The core insight that makes this pattern work: The key insight is that if we're looking for elements a and b such that a + b = target, then for any element a in the array, we only need to check if target - a exists in the remaining elements. This can be efficiently implemented using hash maps to store previously seen elements, allowing us to find the complement in O(1) time rather than O(n) for linear search.

The pattern works particularly well when:

1. We need to return indices rather than just existence
2. The input array is not necessarily sorted
3. We want optimal time complexity over space trade-offs
4. The problem asks for exactly one valid solution

3. Approach Evolution

Interview communication script:

"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. But that's O(n²) because for each element, I'd have to look at all remaining elements. Let me think about how to optimize this...

I notice that if I sort the array first, I can use the two-pointer technique to find pairs in O(n) time. But that would require O(n log n) for sorting, and I'd lose the original indices which might be needed. Actually, let me think about this more carefully - I don't need to sort the array at all.

I notice that if I maintain a hash map of previously seen values and their indices, I can solve this in one pass. For each element, I check if the complement (target - current value) exists in my hash map. If it does, I've found my answer. Otherwise, I add the current element to the hash map and continue. This is O(n) time and O(n) space.

The key insight is that I can trade space for time by caching previously seen elements, which allows me to avoid the nested loop structure. This is much more efficient than checking every pair."

Brute-force approach and why it is not ideal:

The brute force approach involves checking every possible pair of elements in the array to see if their sum equals the target. For each element at index i, we iterate through all elements at indices j where j > i and check if nums[i] + nums[j] = target.

This approach has O(n²) time complexity because for each element, we potentially examine all remaining elements. It's not ideal because:

• It's inefficient for large inputs
• The nested loop structure makes it hard to scale
• There's no reuse of previously computed information

Improved approach and the key optimization:

The improved approach uses a hash map to store previously seen elements along with their indices. The key optimization is that we can look up the complement (target - current element) in O(1) time instead of having to search through remaining elements.

Instead of checking all pairs, we process elements one by one and for each element, we check if its complement has been seen before. If yes, we've found our answer. If no, we store the current element and continue.

Final approach with step-by-step reasoning:

1. Initialize an empty hash map to store {value → index} mappings
2. Iterate through the array from left to right
3. For each element, calculate its complement (target - current_value)
4. Check if the complement exists in our hash map:
   • If yes, return the stored index and current index
   • If no, store the current element as {value → index} in hash map
5. Continue until we find a pair or exhaust the array

Important invariants that must hold:

• The hash map always contains elements that we've processed but haven't found a complement for yet
• For any element at index i, all elements at indices < i are either in the hash map or have already been paired
• When we find a match, we return indices in ascending order (smaller index first)
• The solution handles negative numbers correctly since we're looking for complement values, not just larger elements

4. Data Structure Choice

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

Primary Data Structures:

• HashMap<Integer, Integer> - stores previously seen values and their indices
  • Key: array value
  • Value: index of that value in the input array
  • Why needed: Enables O(1) lookup to find if complement exists in prior elements
  • Time impact: Reduces lookup from O(n) to O(1)
  • Space impact: O(n) additional space for storing up to n elements

Helper Structures:

• int[] - input array (read-only, no mutation needed)
  • Used for accessing original values and indices
  • No additional space cost beyond input

The HashMap is essential because it allows us to maintain a "memory" of previously processed elements while iterating once through the array. This is crucial for achieving linear time complexity.

Alternative approaches like using a HashSet would only store values, not indices, which wouldn't work for this problem since we need to return actual indices rather than just whether a pair exists.

The key insight is that we're trading space for time - using O(n) extra space to achieve O(n) time complexity instead of the brute force O(n²) approach.

5. Algorithm Walkthrough

Let me trace through the Two Sum problem with the optimal approach using hash map.

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

Step-by-step execution:

1. Initialization: Create empty HashMap numToIndex to store {value → index} mappings

2. Iteration 1 (i=0, num=2):

   • Calculate complement: complement = 9 - 2 = 7
   • Check if 7 exists in HashMap → No
   • Add current element: numToIndex[2] = 0

3. Iteration 2 (i=1, num=7):

   • Calculate complement: complement = 9 - 7 = 2
   • Check if 2 exists in HashMap → Yes, at index 0
   • Found solution: return [0, 1]

Edge case handling:

• If array has fewer than 2 elements → handled by problem constraints
• If no valid pair exists → return null/empty array (not requested in this problem)
• Duplicate values handled correctly since we only need one valid pair

Algorithm termination: The algorithm terminates when either:

1. A valid pair is found (early return)
2. All elements are processed without finding a match

Why it works: At each step, we check if the complement of current number has been seen before. If yes, we've found our pair. Since we process elements sequentially and only store what we've seen, we never miss a valid combination.

The key insight is that for any pair (a,b) where a+b=target, we'll encounter one element first and the other second. By storing previously seen elements in a hash map, we can instantly look up if the complement exists.

// Example trace:
// i=0: num=2, comp=7, not found, store {2:0}
// i=1: num=7, comp=2, found at index 0, return [0,1]

6. Java Solution

public class TwoSum {
    /**
     * Finds two indices in the array that sum to the target value.
     * Uses hash map for O(n) time complexity.
     * 
     * @param nums Array of integers
     * @param target Target sum value
     * @return Array containing the two indices, or empty array if no solution exists
     */
    public int[] twoSum(int[] nums, int target) {
        // Map to store value -> index mapping
        java.util.Map<Integer, Integer> numToIndex = new java.util.HashMap<>();
        
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            
            // If complement exists in map, we found our pair
            if (numToIndex.containsKey(complement)) {
                return new int[]{numToIndex.get(complement), i};
            }
            
            // Store current number and its index
            numToIndex.put(nums[i], i);
        }
        
        // No solution found
        return new int[0];
    }
}

The solution uses a hash map to achieve O(n) time complexity by storing previously seen numbers along with their indices. 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 answer; otherwise, we store the current number and continue. This approach avoids the O(n²) brute force nested loop solution while maintaining clean, readable code that handles all valid inputs correctly.

7. Complexity Analysis

Time Complexity: O(n log n)

The time complexity breaks down as follows:

• Sorting the array takes O(n log n) time
• The two-pointer traversal runs in O(n) time
• Since O(n log n) dominates O(n), the overall time complexity is O(n log n)

Space Complexity: O(1)

The space complexity is constant because:

• We only use a fixed number of integer variables (left, right, sum)
• No additional data structures are created that scale with input size
• The sorting is done in-place (assuming the built-in sort is in-place)

Why these bounds are correct:

The O(n log n) time bound is tight because:

1. The sorting step cannot be avoided - we need the array sorted to apply the two-pointer technique
2. The two-pointer approach is optimal for finding pairs in a sorted array - each element is visited at most once
3. No comparison-based sorting algorithm can achieve better than O(n log n) time complexity

The O(1) space bound holds because:

1. We only maintain a constant number of variables regardless of input size
2. The algorithm does not create any data structures that grow with input

Optimality:

This solution is near-optimal for the given constraints. If we were to solve this without sorting (using hash maps), we could achieve O(n) time complexity, but that would require O(n) extra space. The current approach trades space for time efficiency by leveraging the sorted property to avoid hash map overhead.

The solution is optimal in the comparison-based model where sorting is required to achieve O(n) time complexity for the two-pointer approach.

8. Edge Cases & Pitfalls

Empty and Minimal Inputs

• Empty array: Should return empty result or handle gracefully with appropriate error handling
• Single element array: Cannot form any valid pair, so should return empty result or throw appropriate exception
• Two element array: May be the only valid case for a solution, but must verify that the pair sums to target

Duplicate Values and Repeated States

• Duplicate elements: The algorithm must correctly handle cases where multiple elements have the same value, ensuring that we don't accidentally use the same element twice in a pair
• Multiple valid pairs: When multiple pairs sum to target, the solution should return all valid pairs or handle according to problem requirements (e.g., first pair only, all pairs)
• Same element used twice: If array contains duplicate elements and one element appears twice, we must ensure that we don't use the same index twice

Boundary Conditions

• Integer overflow: When adding two large integers, result might exceed integer range; consider using long or checking for overflow conditions
• Negative numbers: Solution must work correctly with negative numbers, including cases where one number is positive and another is negative
• Zero values: Special handling needed for zero, since 0 + 0 = 0 and 0 + x = x

Common Implementation Mistakes

• Index reuse: Using same index twice in a pair (e.g., i and j where i == j)
• Incorrect result format: Returning indices in wrong order or not matching expected output format
• Missing edge case handling: Not checking for null inputs or empty arrays before processing
• Inefficient iteration: Using nested loops instead of hash map approach, leading to O(n²) time complexity
• Not handling multiple solutions: Assuming only one valid pair exists when problem allows for multiple valid pairs
• Integer overflow in sum calculation: Not considering that int values might overflow when summed

Specific Pitfalls in Two Sum Implementation

• HashMap key collision: While unlikely with integers, could be an issue if using custom objects as keys
• HashMap null handling: If array contains null elements, HashMap operations might throw NullPointerException
• Return value consistency: Some problems require indices in ascending order, others don't; must be consistent with problem requirements
• Mutating input: If problem requires preserving original array, ensure no in-place modifications occur

9. Alternative Approaches

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

Brute Force Approach: Use nested loops to check every pair of elements. Time complexity is O(n²) with O(1) space. This is inefficient but works for small inputs or when no extra space is allowed.

Sorting + Two Pointers: Sort the array first, then use two pointers from both ends to find pairs. Time complexity becomes O(n log n) due to sorting, but space is O(1) if we don't count the sorting overhead. This approach requires modifying the input array.

Hash Map with Index Tracking: Store indices in the hash map to handle duplicate values properly. This maintains O(n) time but uses O(n) space for the hash map.

Binary Search: For each element, perform binary search for (target - current_element). This requires the array to be sorted first, making it O(n log n) time and O(1) space if sorting is done in-place.

The chosen hash map approach is preferred because it provides optimal O(n) time complexity with clean handling of duplicates, and the space overhead is acceptable for most practical applications. The sorting approach may be preferred when memory is extremely constrained and the input array can be modified, but it introduces additional time complexity due to sorting.

10. Test Cases

// 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: No solution
int[] nums4 = {1, 2, 3};
int target4 = 10;
// Expected: null or empty array

// Test case 5: Single element
int[] nums5 = {5};
int target5 = 10;
// Expected: null or empty array

// Test case 6: Empty array
int[] nums6 = {};
int target6 = 0;
// Expected: null or empty array

// Test case 7: Large numbers
int[] nums7 = {1000000000, 2000000000};
int target7 = 3000000000L;
// Expected: [0, 1] or [1, 0]

The test cases cover the essential scenarios:

• Basic valid pairs
• Negative numbers and mixed signs
• Duplicate values that form the target sum
• Cases with no valid solution
• Edge cases with minimal input sizes (empty array, single element)
• Large integer values to test for overflow considerations

Each case tests a different aspect of the two-sum problem and ensures robustness of the solution across various input conditions.

11. Final Summary

The core idea is to leverage a hash map to achieve O(n) time complexity for finding two integers that sum to a target value, trading space for speed. This solution works by storing visited elements and their indices in a hash map, allowing us to find the complement in constant time during a single pass through the array. The approach is optimal for the static two-sum problem where we need to return indices rather than just a boolean existence check.