Leetcode Question 1. Two Sum [ Intuition, Approach, Solution, Complexities ]

• Difficulty - Easy
• Language used to solve - C++

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

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

Constraints:

• 2 <= nums.length <= 104
• -109 <= nums[i] <= 109
• -109 <= target <= 109
• Only one valid answer exists.

Follow-up: Can you come up with an algorithm that is less than O(n2) time complexity?

Intuition :- The main intuition to this question is to solve it to less than O(n^2) time complexity. rest we need to follow our most naive solution that is obviously Brute-force.

The question clearly stated that, It has some target number, we can calculate by adding just two numbers from the given array

Example :- target = 9, array = [ 2, 5, 1, 7, 6], Answer = [2+7] which is coming from 0th and 3rd index so it'll return [0,3];

The Brute-force approach or naive approach is to go through the two times loop and check inside second loop if the index of 1st loop and 2nd loop is really equal to target then store the order and return outside the loop.

Giving Example code below:-

vector<int> twoSum(vector<int>& nums, int target) {
    vector<int> result;
    for (int i = 0; i < nums.size()-1; i++) {
        for(int j=i+1;j<nums.size();j++){ 
           if(nums[i]+nums[j] == target){
              result.push_back(i);
              result.push_back(j);
           }
        }
    }
    return result;
}

Since the question / problem returns the Vector<int> array so we need to take a auxiliary space to return it otherwise, it'll throw error if we only return interger kind of datatype.

🔹 Outer loop: for (int i = 0; i < n-1; i++)

• i is the first index in the pair.
• If i reaches n-1, there’s no j > i left to pair with (because the last index is already taken).
• So we stop at n-2 (that’s why the condition is < n-1).

👉 Example: if n = 5

• i = 0 → j = 1..4
• i = 1 → j = 2..4
• i = 2 → j = 3..4
• i = 3 → j = 4
• i = 4 → ❌ no j left (so we don’t need this case).

---

🔹 Inner loop: for (int j = i+1; j < n; j++)

Goes until the last index n-1 → so condition is < n.

j always starts one step ahead of i (to avoid repeating pairs like (i,j) and (j,i)).

If we come to the complexities of this naive solution then

Time Complexity:
- The code uses two nested loops: the outer loop runs from 0 to n-2, and the inner loop runs from i+1 to n-1.
- In the worst case, this results in approximately n*(n-1)/2 comparisons.
- Therefore, the time complexity is O(n^2).

Space Complexity:
- The auxiliary space used is for the result vector, which can hold at most two indices.
- Apart from the input and output, the space used is constant.
- Hence, the space complexity is O(1).

In summary:
- Time complexity: O(n^2)
- Space complexity: O(1)

Now coming to the question to code this problem in O(n) time complexity

vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int, int> numMap;
    vector<int> result;
    for (int i = 0; i < nums.size(); i++) {
        int complement = target - nums[i];
        if (numMap.find(complement) != numMap.end()) {
            result.push_back(numMap[complement]);
            result.push_back(i);
            return result;
        }
        numMap[nums[i]] = i;
    }
   return result;
}

🔹 1. Each pair is found only once

• In brute force, you check all pairs (i, j) → duplicates are possible if you’re not careful.
• In hashmap:
  • At index i, you only check if the complement has already appeared before.
  • If yes → return {index_of_complement, i} immediately.
  • If no → you store the current number with its index for future use.

👉 This guarantees each valid pair is discovered only once, because you only “look back”, never “look forward”.

---

🔹 2. Handling repeated numbers

Suppose nums = [3, 3], target = 6.

• i = 0 → nums[0] = 3, complement = 3 → not found → store {3: 0}.
• i = 1 → nums[1] = 3, complement = 3 → found at index 0 ✅
  → return [0, 1].

So it works fine with duplicates.

---

🔹 3. Why it avoids using the same element twice

• You first check the hashmap for the complement, before inserting the current element.
• That means i will never match with itself (e.g., you won’t pair nums[i] with itself unless another identical number exists at a different index).

---

✅ Example with more repeats

nums = [2, 7, 11, 15, 7], target = 14

• i = 0 → 2 → complement 12 → not found → store {2:0}
• i = 1 → 7 → complement 7 → not found → store {7:1}
• i = 2 → 11 → complement 3 → not found → store {11:2}
• i = 3 → 15 → complement -1 → not found → store {15:3}
• i = 4 → 7 → complement 7 → found at index 1 ✅ → return [1,4]

If we come to complexities to this optimal solution is then

Complexity:

• Time → O(n) (each element looked at once)
• Space → O(n) (hashmap storage)

Verdict :- Cheers! We solved the TwoSum.