Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.
A thread 🧵👇
Approach - 1 : Brute Force
- Use 2 for loops and check for all possible pairs of numbers that makes the target sum.
Time Complexity - O(n^2)
Space Complexity - O(1)
Approach - 2 : Sorting + Two Pointers
- Consider nums = [2,15,11,7] and target = 9
- After Sorting, nums = [2,7,11,15]
- Take 2 pointers, "start" and "end" pointing to the first and last element of the array.
- Let, sum = nums[start] + nuts[end]
- If, sum>target : decrement "end"
sum<target : increment "start"
sum=target : You got the answer!
Time Complexity - O(nlog(n))
Space Complexity - O(1)
Approach - 3 : Using HashMap
- Go to every element of the array and search if (target - currentElement) is present in the Hashmat.
- If its present then you have got the pair.
- Otherwise, insert that element into the HashMap and continue the above steps.
HashMap provides constant lookups and hence the overall time complexity of this solution will be linear.
Time Complexity - O(n)
Space Complexity - O(n)
I would highly recommend you to watch this video to understand how you should approach any problem statement in interviews. There they have discussed the same problem!
I hope you guys understood all the approaches to solve this problem! Consider retweeting if it helped.
I will be sharing much more problems in the upcoming days so make sure you follow along @_MohitBalwani !
• • •
Missing some Tweet in this thread? You can try to
force a refresh