Two Sum Problem - LeetCode Solution

Problem Statement

The Two-Sum problem asks you to find two numbers in a list of integers that add up to a given target sum. You are tasked with returning the indices of these two numbers in the array.

This problem is widely used to test your understanding of arrays, hash maps, and optimization techniques. In this blog, we’ll explore how to efficiently solve this problem using C++, Python, and Java.

Explanation

The simplest way to solve this problem is by using a brute-force approach: we check all pairs of numbers to see if they add up to the target sum. However, this approach has a time complexity of O(n²), which is inefficient.

A more optimal approach uses a hash map. As we traverse through the array, we check if the complement of the current number (i.e., target - current number) exists in the map. If it does, we’ve found a pair of numbers that sum up to the target, and we return their indices.

Example

Given an array nums = [2, 7, 11, 15] and a target target = 9, the answer is index 0 and 1 because nums[0] + nums[1] = 9.

[2, 7, 11, 15]
        ↑
   target - 9 - find complement
        ↑
   solution found (index 0 and 1)
            

Time & Space Complexity

Time Complexity: O(n), where n is the number of elements in the input array. We only need to iterate through the array once.

Space Complexity: O(n), where n is the number of elements in the input array. We use a hash map to store the indices of the numbers as we iterate.

C++

Python

Java

C++ Solution

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

    for (int i = 0; i &lt; nums.size(); ++i) {
      if (const auto it = numToIndex.find(target - nums[i]);
          it != numToIndex.cend())
        return {it->second, i};
      numToIndex[nums[i]] = i;
    }

    throw;
  }
};

Python Solution

class Solution:
  def twoSum(self, nums: list[int], target: int) -> list[int]:
    numToIndex = {}

    for i, num in enumerate(nums):
      if target - num in numToIndex:
        return numToIndex[target - num], i
      numToIndex[num] = i

Java Solution

            class Solution {
  public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> numToIndex = new HashMap<>();

    for (int i = 0; i < nums.length; ++i) {
      if (numToIndex.containsKey(target - nums[i]))
        return new int[] {numToIndex.get(target - nums[i]), i};
      numToIndex.put(nums[i], i);
    }

    throw new IllegalArgumentException();
  }
}

If you found this helpful, feel free to leave a comment or share it with fellow learners!

Made by Sandeep Mhaske