GoogleAlgorithmsEasy

Two Sum Problem

AlgorithmsArrayHashMapTwo Pointers

Question

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

Answer

Problem: Find two numbers in an array that sum to a target value.

Brute Force Approach (O(n²)):

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

Optimal Approach using HashMap (O(n)):

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

Explanation

The HashMap approach is optimal because: - Time Complexity: O(n) - single pass through array - Space Complexity: O(n) - HashMap storage We store each number and its index, then check if the complement (target - current number) exists in the map.