Problem Overview

  • We are given an array of integers nums and an integer target.

  • Our Goal is to find two distinct integers from the array, such that their sum is equal to the target and return their indices.

  • Constraints:

    • The array contains at least 2 elements.
    • Exactly one valid solution exists.

  • The goal is to design a solution with O(n) time complexity.

Lets Fund out how i approached this problem and what were my thoughts while solving this.

The first goal is to solve the problem and then optimizes it.

Brute Force

  • The most straightforward way to solve the problem is to try all possible pairs.
  • We iterate over the array using two nested loops and check if any pair sums to the target.
  • This approach will give us the desired result but is is not the best.
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        
        int n = nums.size();
        vector<int> result;

        for(int i=0;i <n;i++){
            for(int j=i+1;j<n;j++){
                if(nums[i] + nums[j] == target){
                    result.push_back(i);
                    result.push_back(j);
                    break;
                }

            }
        }

        return result;
    }
};
  • Time Complexity: O(n²)
  • Space Complexity: O(1)

Why it fails:

  • The nested loop becomes too slow as input size grows.

Loop + Two Pointer Attempt (Rejected)

  • After the brute-force solution, on observing the code an idea was struck to optimize the inner loop using a two-pointer technique.
  • The approach fixes one element and tries to find the second using two pointers.
  • one pointer search for the remaining from the start and another from the end.

Why this does not work:

  • Time complexity remains O(n²) in the worst case.
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        
        int n = nums.size();
        vector<int> result;
        int flag = 0;
        for(int i=0;i <n;i++){
        
            int x = target - nums[i];
            int y=i+1, z=n-1;

            while(y<=z){

                if(x == nums[y]){
                    result.push_back(i);
                    result.push_back(y);
                    flag = 1;
                    break;
                }

                if(x == nums[z]){
                    result.push_back(i);
                    result.push_back(z);
                    flag = 1;
                    break;
                }

                y++;
                z--;

                if(flag == 1) return result; 
            }
          
        }

        return result;
    }
};

Conclusion: This approach does not provide real optimization and is discarded. But its the above solution that lead me to the final solution so this was not in vein.

Using HashMap (Optimal Solution)

  • Instead of searching for both elements, we fix one element and search for its complement.

  • While iterating through the array:

    • For the current element nums[i], compute target - nums[i].
    • Check if this value already exists in a hash map.
    • If found, we have our answer.
    • If not, store the current value and its index in the map.

This removes the inner loop entirely.

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {

        int n = nums.size();
        vector<int> result;
        unordered_map<int, int> map;


        for (int i = 0; i < n; i++) {

            int x = target - nums[i];

            if (map.find(x) == map.end()) {
                map.insert({nums[i], i});
                continue;
            }

            result.push_back(i);
            result.push_back(map[x]);
            break;
        }

        return result;
    }
};
  • Time Complexity: O(n)
  • Space Complexity: O(n)

Conclusion

  • This problem demonstrates how hashing can convert a pair-search problem into a single-pass lookup.