Two Sum Unsorted

Problem Link

Two Sum – LeetCode

Problem: Two Sum

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 the target.

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

Return the answer in any order.

Examples

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

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 <= 10⁴

• -10⁹ <= nums[i] <= 10⁹

• -10⁹ <= target <= 10⁹

• Only one valid answer exists.

Intuition

We want to find two numbers in the array that sum to a given target. A brute-force approach would take O(n²) time, but we can solve this in O(n) by using a HashMap to store the numbers we've seen so far and their indices.

Approach

1. Initialize an empty HashMap<Integer, Integer> to store each number and its index.

2. Iterate over the array:

   • For each element nums[i], compute its complement: target - nums[i].

   • If the complement is present in the map, return the current index and the index of the complement.

   • Otherwise, add nums[i] and its index to the map.

3. If no such pair is found, return [-1, -1] (theoretically unreachable due to problem constraints).

Code (Java)

import java.util.*;

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < nums.length; i++) {
            int rem = target - nums[i];
            if(map.containsKey(rem)) {
                return new int[]{map.get(rem), i};
            }
            map.put(nums[i], i);
        }
        return new int[]{-1, -1};
    }
}

Time and Space Complexity

• Time Complexity: O(n)
  Each element is visited once, and each map operation is constant time on average.

• Space Complexity: O(n)
  We store up to n elements in the map.

Dry Run

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

• Initialize map: {}

• i = 0: nums[0] = 2, complement = 9 - 2 = 7 → not in map → put 2 → 0 → map = {2: 0}

• i = 1: nums[1] = 7, complement = 9 - 7 = 2 → found in map → return [0, 1]

Conclusion

This is a classic hash map-based problem to efficiently find a pair of numbers that sum to a given target. It demonstrates how hashing can reduce time complexity from quadratic to linear for search problems.