Leetcode Two Sum Problem Explained: A Simple Guide

Imagine you have an array of numbers called nums and a number called target. Your job is to find the indices of the two numbers that add up totarget.

You can assume there's always one solution, and you can't use the same number twice.

Feel free to 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<sup>4</sup>

• -10<sup>9</sup> <= nums[i] <= 10<sup>9</sup>

• -10<sup>9</sup> <= target <= 10<sup>9</sup>

• Only one valid answer exists.

Follow-up: Can you devise an algorithm with a time complexity less than O(n^2)?

Approach 1: Simple solution to the problem

function twoSum(nums: number[], target: number): number[] {
    for(let i=0;i<nums.length;i++){
        for(let j=i+1;j<nums.length;j++){
            if(nums[i]+nums[j] == target){
                return [i,j]
            }
        }
    }
};

This function, twoSum, finds two numbers in an array (nums) that add up to a specified target value (target). It returns their indices.

Step-by-Step Explanation:

1. Function Signature:

   • function twoSum(nums: number[], target: number): number[] declares the function with two parameters:

     • nums: an array of numbers.

     • target: the target sum.

   • The function returns an array of two indices.

2. Outer Loop:

   • for(let i=0; i<nums.length; i++) { iterates through each element in nums using i as the index.

3. Inner Loop:

   • for(let j=i+1; j<nums.length; j++) { starts from the element after i (j=i+1) and iterates to the end of nums.

4. Checking for Target Sum:

   • if(nums[i] + nums[j] == target) { checks if the sum of elements at i and j equals the target.

   • If true, the function returns [i, j].

5. Return Statement:

   • return [i, j] exits the function and returns the indices of the two elements whose sum equals the target.

6. Function End:

   • If no pair adds up to the target, the function returns nothing. You might want to handle this by returning an empty array or throwing an error.

Approach 2: Using Map function

 function twoSum(nums: number[], target: number): number[] {

    let map = new Map()
    for(let i=0; i<nums.length;i++){
        if(map.has(nums[i])){
            return ([map.get(nums[i]),i])
        }else{
            let diff = target-nums[i];
            map.set(diff, i)
        }
    }

};

Explanation

1. Map Initialization:

   • let map = new Map(); initializes an empty Map to track the differences (complement values) and their indices.

2. Loop Through the Array:

   • for (let i = 0; i < nums.length; i++) { iterates through each element in the nums array using the index i.

3. Check if Current Number is in the Map:

   • if (map.has(nums[i])) { checks if the current number nums[i] is already present in the Map.

   • If it is, it indicates that a previous number, when added to the current number, equals the target.

4. Return the Indices:

   • return [map.get(nums[i]), i]; retrieves the stored index of the complement (the number that, when added to the current number, equals the target) and the current index i. These are the indices of the two numbers that sum up to the target.

5. Calculate and Store the Difference:

   • let diff = target - nums[i]; calculates the difference (complement) needed to reach the target sum for the current element nums[i].

   • map.set(diff, i); stores this difference along with the current index i in the Map.

Time and Space Complexity

• Time Complexity: O(n) because the function iterates through the nums array only once.

• Space Complexity: O(n) due to the additional space used by the Map to store up to n elements.

This article discusses two approaches to solve the problem of finding indices of two numbers in an array that add up to a given target. The first approach uses a simple nested loop with a time complexity of O(n^2), while the second approach employs a Map to achieve a more efficient solution with a time complexity of O(n). Detailed explanations and code examples are provided for each approach.