Two Sum easy

Problem Statement

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]

Steps and Explanation

The brute-force approach would involve checking every possible pair of numbers in the array. This has a time complexity of O(n²). However, we can optimize this significantly using a hash map (or object in JavaScript/TypeScript).

1. Create a hash map: We'll use a hash map (an object in this case) to store each number in nums as a key, and its index as the value.

2. Iterate through the array: For each number num in nums:

   • Calculate the complement: complement = target - num.
   • Check if the complement exists as a key in the hash map.
   • If it does, we've found the pair! Return the index of the current number and the index stored in the hash map for the complement.
   • If it doesn't, add the current number and its index to the hash map.

3. No solution found: If the loop completes without finding a pair, it means there's no solution. (The problem statement guarantees a solution, so this shouldn't happen in valid inputs).

Code (TypeScript)

function twoSum(nums: number[], target: number): number[] {
    const numMap: { [num: number]: number } = {}; // Hash map to store numbers and their indices

    for (let i = 0; i < nums.length; i++) {
        const num = nums[i];
        const complement = target - num;

        if (complement in numMap) {
            return [numMap[complement], i]; // Found the pair!
        }

        numMap[num] = i; // Add the current number and its index to the map
    }

    return []; // Should not reach here given the problem statement
};

Complexity

• Time Complexity: O(n), where n is the length of the input array. We iterate through the array once. The hash map lookups are on average O(1).

• Space Complexity: O(n) in the worst case, as the hash map could store all the numbers from the input array.