Two Sum - Leetcode

Introduction

Two sum is a classic problem, and one of the most liked problems on leetcode. It seems to be an easy problem yet it is asked frequently in many interviews of big companies like Facebook(meta), Google, Amazon, Microsoft, Adobe, Apple, Netflix.

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: nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]
Explanation: nums[1] + nums[2] = 6

Try Yourself Before Seeing the Code

Explanation

Approach 1 -

Let's consider the given array is [2, 5, 12, 7, 15, 1] and target = 6.

We need two numbers from array that's sum will be equal to target, the first thought that'll cross your mind is using two nested loops, and that's correct as well.

We will use two nested loops, to find the two numbers that's equal to the target and return an array of indices of both the numbers. If the sum is not present in the array return an empty array of size 2.

Code

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(target - nums[i] == nums[j]){
                return new int[]{i, j};
            }
        }
    }
    return new int[2];
}

Time complexity - O(N^2), as we're using nested loop that will both run for linear time in worst case.

Space complexity - O(1), we're not using any extra space.

Approach 2-

Sort the array and use two pointer approach, left and right.

Increase left pointer if the sum is less than target, decrease the right pointer if sum is more than target.

Modifying the input data may be discouraged by some interviewers, so you can provide a different solution.

public int[] twoSum(int[] nums, int target) {
    Arrays.sort(nums);
    int left = 0, right = nums.length-1;
    while (left < right) {
        if (nums[left] + nums[right] == target)
            return new int[]{left, right};
        else if (nums[left] + nums[right] < target)
            left++;
        else
            right--;
    }
    return new int[2];
}

Time complexity - O(n logn), Sorting takes O(n logn) time and traversing through the array takes O(n), so overall it'll take O(n logn) time.

Space complexity - O(1), depends upon the internal implementation of sort function, if it uses merge sort it'll take O(n) space, in case of heap and quick sort it'll take o(1) space.

Approach 3-

Using HashMap we can get an optimal solution without sorting the array, we'll map the element of array and index of element, here we will find if the map contains targetNumber - currentNumber if it present in Map then return an array of targetNumber - currentNumber's index and currentIndex.

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

Time complexity - O(n), we're traversing through array only once.

Space complexity - O(n), HashMap will store n elements in worst case.