Two Sum

10 May 2026 0 Likes

Problem Description

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

You may assume that each input has exactly one valid solution, and the same element cannot be used twice. The returned indices can be in any order.
Example 1:
Input: nums = [2, 7, 11, 15], target = 9

Output: [0, 1]
Explanation: Because nums[0] + nums[1] = 2 + 7 = 9, we return [0, 1].
Example 2:
Input: nums = [3, 2, 4], target = 6

Output: [1, 2]
Explanation: Because nums[1] + nums[2] = 2 + 4 = 6, we return [1, 2].
Example 3:
Input: nums = [3, 3], target = 6

Output: [0, 1]
Explanation: Both elements together form the required target sum.

Constraints

The array contains at least 2 elements and can contain up to large input sizes depending on platform limits.

The value of each integer inside nums may be positive, negative, or zero. The target value can also be negative or positive.

There will always be exactly one valid answer, and the same array element cannot be used twice while forming the target sum.

An optimal solution is expected to run in linear time complexity using additional space for hashing.

Understanding the Problem

The problem is asking us to find two numbers in the array whose sum becomes equal to the given target.

A simple way to understand the problem is by using a brute-force approach. We can pick one element and compare it with every other element in the array to check whether their sum equals the target.

For example, if the array is [2, 7, 11, 15] and the target is 9, we first choose 2 and check:

2 + 7 = 9

Since the sum matches the target, we have found the required pair.

In general, for every element nums[i], we try pairing it with elements appearing after it and check whether:

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

This approach helps in understanding the problem clearly because it directly follows the statement of checking all possible pairs until the correct answer is found.

Hints

The first hint is to think about what information is needed to quickly determine whether a matching number already exists. Instead of searching the array repeatedly, try storing previously visited elements for constant-time lookup.

Another important observation is that for every number nums[i], the required matching value is target - nums[i]. If this complement has already been processed earlier, then the solution is found immediately.

Using a HashMap is the key optimization because it allows efficient searching without using nested loops.

Solutions

BETTER

Sorting + Two Pointer

In this approach, we first store both the number and its original index together because sorting changes the positions of elements inside the array.

After storing the values with their indices, we sort the array based on the numbers. Then we use the two-pointer technique.

One pointer starts from the beginning of the sorted array, while the other starts from the end. We calculate their sum:

1. If the sum is smaller than the target, we move the left pointer forward to increase the sum.
2. If the sum is greater than the target, we move the right pointer backward to decrease the sum.

Once the sum becomes equal to the target, we return the original indices stored earlier.

This approach is more efficient than brute force and demonstrates the practical use of sorting and two pointers together.
public class B_Sorting {

    public int[] twoSum(int[] nums, int target) {

        int[][] numsIndex = new int[nums.length][2];

        for (int i = 0; i < nums.length; i++) {
            numsIndex[i] = new int[]{nums[i], i};
        }

        Arrays.sort(numsIndex, (a, b) -> Integer.compare(a[0], b[0]));

        int i = 0;
        int j = numsIndex.length - 1;

        while (i < j) {

            int total = numsIndex[i][0] + numsIndex[j][0];

            if (total < target)
                i++;

            else if (total > target)
                j--;

            else
                return new int[]{numsIndex[i][1], numsIndex[j][1]};
        }

        return new int[]{};
    }
}
class Solution:

    def twoSum(self, nums, target):

        nums_index = []

        for i in range(len(nums)):
            nums_index.append([nums[i], i])

        nums_index.sort(key=lambda x: x[0])

        left = 0
        right = len(nums_index) - 1

        while left < right:

            total = nums_index[left][0] + nums_index[right][0]

            if total < target:
                left += 1

            elif total > target:
                right -= 1

            else:
                return [nums_index[left][1], nums_index[right][1]]

        return []
Time Complexity
O(n log n)
Space Complexity
O(n)
BRUTE FORCE

Nested Loop Brute Force Solution

This approach uses a simple nested loop technique to check every possible pair present in the array.

We start from the first element and compare it with all remaining elements one by one. For every pair, we calculate the sum and check whether it becomes equal to the given target.

If the sum matches the target, we immediately return the indices of those two elements.

Although this solution is easy to understand and implement, it becomes inefficient for large input sizes because every element is compared with multiple other elements.
public class A_BruteForce {

    public int[] twoSum(int[] nums, int target) {

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

            for (int j = i + 1; j < nums.length; j++) {

                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j};
                }

            }

        }

        return new int[]{};
    }

}
class Solution:

    def twoSum(self, nums, target):

        for i in range(len(nums)):

            for j in range(i + 1, len(nums)):

                if nums[i] + nums[j] == target:
                    return [i, j]

        return []
Time Complexity
O(nĀ²)
Space Complexity
O(1)
OPTIMAL

Optimal HashMap Solution

This approach uses a HashMap to efficiently track previously visited numbers while traversing the array only once.

For every element nums[i], we calculate the required complement using: target - nums[i]

If this complement already exists inside the map, it means we have found the two numbers whose sum equals the target.

The map stores the number as the key and its index as the value, allowing constant-time lookup operations.

This solution avoids nested loops completely and achieves optimal performance with linear time complexity.
public class C_Map {

    public int[] twoSum(int[] nums, int target) {

        Map<Integer, Integer> map = new HashMap<>();

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

            if (map.containsKey(target - nums[i])
                    && map.get(target - nums[i]) != i) {

                return new int[]{i, map.get(target - nums[i])};
            }

            map.put(nums[i], i);
        }

        return new int[]{};
    }
}
class Solution:

    def twoSum(self, nums, target):

        mp = {}

        for i in range(len(nums)):

            complement = target - nums[i]

            if complement in mp:
                return [i, mp[complement]]

            mp[nums[i]] = i

        return []
Time Complexity
O(n)
Space Complexity
O(n)

Conclusion

The Two Sum problem is one of the most important beginner-level coding interview problems because it introduces the concept of efficient searching using hashing.

Although the brute-force solution is simple to understand, the optimized HashMap-based approach demonstrates how appropriate data structures can drastically improve performance.

Mastering this problem helps build a strong foundation for solving advanced problems involving arrays, hashing, and lookup optimization in technical interviews.

šŸ’¬ Comments