2 Sum- Leetcode 1

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.

You may assume that:

• Exactly one valid answer exists.
• You cannot use the same element twice.
• Return the indices in any order.

Example 1

Input

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

Output

[0,1]

Explanation

nums[0] + nums[1]= 2 + 7= 9

Since the sum equals the target, we return the indices:

[0,1]

Example 2

Input

nums = [3,2,4]

target = 6

Output

[1,2]

Explanation

nums[1] + nums[2]= 2 + 4= 6

Return:

[1,2]

Constraints

2 <= nums.length <= 10^4
-10^9 <= nums[i] <= 10^9
-10^9 <= target <= 10^9

Brute Force Approach

Intuition

The most straightforward idea is:

For every element, check every other element and see whether their sum equals the target.

Since we need two numbers whose sum is target, we can try all possible pairs.

Example

nums = [2,7,11,15]

target = 9

Check:

2 + 7 = 9 ✅

We found the answer, so return:

[0,1]

Algorithm

1. Traverse the array using index i.
2. For each i, traverse the remaining array using index j.
3. Check if:

nums[i] + nums[j] == target

1. If true, return {i, j}.
2. If no pair is found, return an empty vector.

Dry Run

C++ Code

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

        int n = nums.size();

        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 {};
    }
};

Complexity Analysis

Time Complexity

O(n²)

Reason:

• Outer loop runs n times.
• Inner loop runs approximately n times for each element.

Total operations:

n × n = O(n²)

Space Complexity

O(1)

No extra data structure is used.

Why is this inefficient?

Suppose:

n = 10000

Then comparisons can be close to:

10000 × 10000= 100,000,000

That's huge.

Notice that for every number nums[i], we are repeatedly searching for:

target - nums[i]

If we could find this required value instantly instead of scanning the whole array, we could reduce the complexity from O(n²) to O(n).

This observation leads to the optimal Hash Map solution.

Optimal Approach (Hash Map)

Intuition

In the brute-force solution, for every number we searched the entire remaining array to find its partner.

Let's think differently.

Suppose:

nums = [2,7,11,15]

target = 9

We start with:

2

To make 9, we need:

9 - 2 = 7

So instead of searching the whole array later, what if we store numbers we've already seen in a hash map?

Key Observation

For every element nums[i], calculate:

required = target - nums[i]

If required already exists in the hash map, then we have found our answer.

Otherwise, store the current number and its index.

Dry Run:

Algorithm

1. Create an empty hash map.
2. Traverse the array.
3. Compute:

required = target - nums[i]

1. If required exists in the hash map:
   • Return {hashMap[required], i}

2. Otherwise, store:

hashMap[nums[i]] = i

4. Continue until the answer is found.

C++ code:

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

        unordered_map<int, int> mp;

        for (int i = 0; i < nums.size(); i++) {

            int required = target - nums[i];

            if (mp.find(required) != mp.end()) {
                return {mp[required], i};
            }

            mp[nums[i]] = i;
        }

        return {};
    }
};

Complexity Analysis

Time Complexity

O(n)

Reason:

• We traverse the array only once.
• Hash map lookup is approximately O(1).

Therefore:

n × O(1) = O(n)

Space Complexity

O(n)

In the worst case, all elements may be stored in the hash map.

Practice link:

Two Sum - LeetCode

Video reference:

https://youtu.be/KLlXCFG5TnA?si=ni5zs0oTBgmrSWQg