1. Two Sum

Description

Difficulty: Easy

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

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

You can return the answer in any order.

Example 1:

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

Output: [0,1]

Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

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.

Follow-up: Can you come up with an algorithm that is less than O(n²) time complexity?

Solution

The algorithm iterates through the input array nums once. For each element encountered, it calculates the "complement" needed to reach the target. It then checks if this complement has been seen before (and stored in the hash map).

1. Initialization:

   • An empty HashMap<Integer, Integer> named map is initialized. This map will store elements of nums as keys and their corresponding indices as values.

2. Iterative Search and Storage:

   • The algorithm iterates through the nums array using a for loop, with i representing the current index.

   • Calculate Complement: For each nums[i], the complement is calculated as target - nums[i]. This complement is the number that, when added to nums[i], would equal the target.

   • Check for Complement: The algorithm then checks if this complement already exists as a key in the map using map.containsKey(complement).

     • If Found: If the complement is found in the map, it means we have successfully found two numbers that sum up to the target. The indices are map.get(complement) (the index of the stored complement) and i (the index of the current number). An array containing these two indices is immediately returned.

     • If Not Found: If the complement is not found in the map, it means the current nums[i] is not the second part of a pair found so far. In this case, nums[i] and its current index i are stored in the map using map.put(nums[i], i). This prepares the map for future iterations, where nums[i] might be the complement for a later number.

3. No Solution:

   • If the loop completes without finding any pair that sums to the target, an empty integer array new int[0] is returned. This indicates that no such pair exists in the input array.

Code

import java.util.HashMap;

class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<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[0];
    }
}

Time Complexity: O(n)
The algorithm iterates through the nums array exactly once.
Inside the loop, HashMap operations (containsKey and put) have an average time complexity of O(1). In the worst-case scenario (due to hash collisions), these operations could degrade to O(n), but for typical hash functions and data, the average case dominates.
Therefore, the total time complexity is linear with respect to the number of elements in the input array.

Space Complexity: O(n)
In the worst-case scenario, if no pair is found until the very last element (or no pair exists), the HashMap could end up storing all n elements from the nums array.
Each entry in the HashMap stores an integer (the number) and another integer (its index). Thus, the space required grows linearly with the number of elements in the input array.