Two Sum Problem | Two-Pointer Technique

Problem

Given an array of integers nums[] and a target value, determine if any two numbers in the array sum up to the target, and return their indices.

Constraints

• 2 <= nums.length <= 104
• -109 <= nums[i] <= 109
• -109 <= target <= 109

Example

Input: nums = [3, 8, 9, 10, 25], target = 19
Output: [2, 3]
Explanation: nums[2] + nums[3] = 9 + 10 = 19

Note: Only one valid pair is required, even if multiple pairs may exist. Duplicate values are not a concern for this problem.

Approach I (Brute Force)

This naive solution checks every possible pair of elements using two loops to see if they sum up to the target. If the target sum is not found, it returns an empty result to indicate that no solution exists.

Pseudocode

TWO-SUM(nums, target):
1. for i = 0 to n-1:
2.     for j = i+1 to n-1:
3.         if nums[i] + nums[j] == target:
4.             return (i, j)
5. return empty

Code Implementation

 // Brute-force approach for Two Sum
vector<int> twoSum(vector<int>& nums, int target) {
    int n = (int) nums.size();
    
    // Check all pairs (i, j)
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (nums[i] + nums[j] == target) {
                return {i, j}; // Return indices if sum matches target
            }
        }
    }
    
    return {}; // Return empty vector if no solution is found
}

Time Complexity: O(n²) — two nested loops
Space Complexity: O(1) — no extra space used

Two-Pointer Technique

This method involves sorting the array and then using two pointers to identify a pair of numbers whose sum equals the target. One pointer starts from the beginning of the array and the other from the end. Based on the current sum compared to the target, the pointers move inward — either increasing the left pointer or decreasing the right pointer.

Pseudocode

while left < right:
    sum = nums[left] + nums[right] 
    if sum == target:
        return true
    else if sum < target: // move left pointer to increase the sum
        left++
    else:
        right--  // move right pointer to decrease the sum
return false

Example

Consider the input: nums = [3, 8, 9, 10, 25], target = 19

Approach II (Two-pointer)

Sort the array while keeping track of original indices. Once sorted, place two pointers at the start and end of the array. Then, move pointers based on sum comparison with the target.

• If the sum of the values at these pointers equals the target, you’ve found a solution.
• If the sum is less than the target, move the left pointer forward to increase the sum.
• If it’s greater, move the right pointer backward to decrease the sum.

Since sorting changes the original positions, we first store each number along with its original index to ensure we return correct indices.

This approach relies on the sorted order to efficiently narrow down to a valid pair. If no such pair is found after checking all combinations, return an empty result to indicate that no solution exists.

Pseudocode

TWO-SUM(nums, target):
1. Store (value, index) pairs
2. Sort the array based on values
3. l = 0, r = n-1
4. while l < r:
5.     sum = nums[l].value + nums[r].value
6.     if sum == target: return (nums[l].index, nums[r].index)
7.     if sum < target: l++
8.     else: r--
9. return empty

Code Implementation

// Two-pointer approach for Two Sum
vector<int> twoSum(vector<int>& nums, int target) {
    vector<pair<int, int>> numIndex;  // Store {value, index}
    
    // Store values with their original indices
    for (int i = 0; i < nums.size(); i++) {
        numIndex.push_back({nums[i], i});
    }
    
    // Default behaviour: sorts based on the first element of each pair
    sort(numIndex.begin(), numIndex.end());

    int l = 0, r = (int) nums.size() - 1;
    
    while (l < r) {
        int sum = numIndex[l].first + numIndex[r].first;
        
        if (sum == target) {
            return {numIndex[l].second, numIndex[r].second}; // Return original indices
        } else if (sum < target) {
            l++;  // Increase sum by moving left pointer forward
        } else {
            r--;  // Decrease sum by moving right pointer backward
        }
    }

    return {}; // Return empty vector if no solution
}

Time Complexity: O(n logn) — for sorting
Space Complexity: O(n) — to store value-index pairs

Approach III (Hashmap)

This efficient method uses a hashmap to store previously seen numbers and their indices. As we iterate, we compute the complement (target - nums[i]) and check if it exists in the map. If it exists in the map, we have found a pair of indices that sum up to the target. If not, we store the current number and its index in the map for future reference.

This single-traversal technique ensures that we only loop through the array once, making it an efficient approach.

Note: The find() operation in a hashmap (implemented as an unordered_map in C++) has an average time complexity of O(1), due to the underlying hash table structure. This allows constant-time lookups of previously seen values during the traversal.

Pseudocode

TWO-SUM(nums, target):
1. Create empty hashmap
2. for i = 0 to n-1:
3.     complement = target - nums[i]
4.     if complement in map:
5.         return (map[complement], i)
6.     map[nums[i]] = i
7. return empty

Code Implementation

// Hashmap approach for Two Sum
vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int, int> numMap; // Stores {value, index}

    for (int i = 0; i < nums.size(); i++) {
        int complement = target - nums[i]; // Required value

        if (numMap.find(complement) != numMap.end()) {
            return {numMap[complement], i}; // Found solution
        }

        numMap[nums[i]] = i; // Store number and its index
    }

    return {}; // Return empty if no solution
}

Time Complexity: O(n) — single traversal
Space Complexity: O(n) — for storing hashmap

Comparison

Depending on input constraints and desired efficiency, each approach has its advantages.

Practice Problem
Two Sum