This question has been asked by almost every company including big giants like Google, Amazon, etc.
Purpose: Practice of thinking of all possible solutions which help you in interviews.
Hi Readers! I am taking a question from the Top Interview Question list given by the Leetcode coding platform.
Leetcode 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]Example 3:
Input: nums = [3,3], target = 6
Output: [0,1]Constraints:
2 <= nums.length <= 10^4
-10^9 <= nums[i] <= 10^9
-10^9 <= target <= 10^9
Only one valid answer exists.
Before we start, please remember that we need to return the indices as an answer. Also, you can skip to the third solution if you are only looking for the best approach.
All possible solutions:
1. Two for loop: TC -> O(n²) and SC -> O(1) - simple. You need to use two for loops and take the sum of all possible combinations. If you find the sum equal to the target value then return the results. See code below:
2. Sorting and two pointer technique: TC -> O(nlogn) and SC -> O(n).
Sort the array and use two pointers. start=0, end=n-1.
if(nums[start]+nums[end]==target) then return answer,
else if(nums[start]+nums[end]<target) then start=start+1 as we need to increase the sum to reach the target value,
else if(nums[start]+nums[end]>target) then end=end-1 as we need decrease the sum to reach the target value.
This solution will not work for this question because here we have to return the indices of the numbers whose sum equals to target. Due to sorting, indices got changed for each element. However, this approach can be used when you need to “check for a pair in an array with sum as target value” like this question. Refer code below:
3. Using HashMap: TC -> O(n) and SC -> O(n) - best solution.
The below solution is based on the idea that a+b = target and if we know the value of a and target then b = target-a.
Here we store element of nums array as key and corresponding index as a value in a hashmap. Now, iterate through nums and check if (target - nums[i]) is present in the hashmap or not. If it is present that means nums[i] and (target - nums[i]) is our required pair. We update the hashmap with nums[i] in each iteration to keep the track of elements. See below solution:
Refer above code here.
That’s it… Hope you liked this article. Please do like and share it with your friends.” It motivates us.
Comments