Two Sum

Author: Nikhitha Chatla
Date: May 30, 2025

🔍 Problem Statement

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

Constraints:

• Exactly one solution exists.

• Same element cannot be used twice.

• Return the result as indices — order doesn’t matter.

Input: nums = [2, 7, 11, 15], target = 9  
Output: [0, 1]
Explanation: 2 + 7 = 9 → nums[0] + nums[1] = 9

🧠 Brute Force Approach(2-pointer)

Iterate through the array and find the elements which sum up to give target.

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        for (int i = 0; i < nums.size(); i++) {
            for (int j = i + 1; j < nums.size(); j++) {
                if (nums[i] + nums[j] == target)
                    return {i, j};
            }
        }
        return {}; // if no solution found
    }
};

⏱️ Time & Space Complexity

• Time: O(n²) — Every pair is checked.

• Space: O(1)

✅ Pros:

• Simple to write.

❌ Cons:

• Very slow for large input.

🚀 Optimal Approach Using Hash Map

💡 Intuition:

We iterate through the array once and use a hash map to store each number's value and index. For every current number, we compute the complement (i.e., target - currentNumber) and check if it exists in the map.

If it does, we return the current index and the index of its complement.

This approach is very fast — we do only one pass through the array, and hash map lookups are O(1) on average.

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> map; // value -> index
        for (int i = 0; i < nums.size(); i++) {
            int complement = target - nums[i];
            if (map.find(complement) != map.end()) {
                return {map[complement], i};  // Found the answer
            }
            map[nums[i]] = i; // Store current value and index
        }
        return {}; // Not needed; problem guarantees a solution
    }
};

⏱️ Time & Space Complexity:

• Time: O(n)

• Space: O(n) (for the hash map)

✅ Pros:

• Very efficient.

• Easy to implement.

❌ Cons:

• Uses extra memory.

problem link: https://leetcode.com/problems/two-sum/