@take U forward : Hi Striver Bhaiya , I love your video , I am learning alot from you , just want to highlight in SDE sheet for this problem it's redirecting to some other question (i.e Find all pairs with a given sum) ,but it's similiar to 2sum approach only :)
Striver, I cracked my coding interview by providing your optimal solution. Can’t thank you enough. You have changed lives of many. Keep doing great work ❤
I can’t thank enough because you teach so well about the concepts of DSA compared to others. None of the paid resources out there have good content. All I can say is May God bless you with long life and happiness. You are making all of us to land in our dream job.
bhaiya you're so much doing for us, even you live alone in Poland, you sacrifice your time for you and I understand every thing you teach as you are so good in explaining and making people understand. once again thanks a lot for this
00:06 The video covers the 'two sum problem' and its two varieties. 02:04 Two sum problem can be solved using brute force method 04:05 Optimizing 2 Sum problem using a better solution 06:08 Using hashing to easily retrieve elements from a data structure. 08:13 Find the indexes of two elements in an array 10:30 Two pointer approach is a slightly better solution to solve the problem without using a map data structure. 12:38 Using the two-sum problem to find pairs that add up to a given target 14:51 The time complexity of the algorithm is O(n) 16:49 Space complexity and array manipulation explanation
Man after watching the first 5 videos and solving the problems on my own , I was also able to solve almost all medium and some hard problems. Watching these videos really built my logic , these lectures are a gold mine.
Yes even i can solve any problem using brute force approach for better & optimal i have to think....i m sure till the course end i will able to improve my solving skills..i belive ❤
🎯 Key Takeaways for quick navigation: 00:45 📚 *The video is part of the Striver's A to Z DSA course, covering comprehensive content with a guarantee of deep understanding in DS algo for interviews worldwide.* 01:12 🎯 *The Two Sum problem has two varieties: one asks for a yes or no if a pair with the given sum exists, and the other requires returning the indices of the pair.* 02:50 🧠 *The initial Brute Force solution involves nested loops to check every pair's sum.* 05:24 ⏩ *The improved solution uses hashing, mapping array elements to their indices, reducing time complexity to O(n).* 09:17 🚀 *The optimal approach, sorting the array and using two pointers, achieves O(n log n) time complexity without extra space.* 15:16 🔄 *The space complexity for the two-pointer approach is O(1), considering no additional space is used.* 17:50 📂 *Code for all three approaches (Brute Force, Hashing, Two-Pointer) is available in C++, Java, and Python in the video description.* Made with HARPA AI
Bhaiya thanks for understanding from the student perspective. You are doing a really great job. Looking forward to the other problem solving videos from you. Good luck!
I am actually preparing for my placements,now im btech 3 rd yr and i wanted someone who says from the scratch with the bestttttttt explanation.........thankyou soo muchh bro...i will follow each and every video of urs and i hope i can crack it....!!!
00:06 The video covers the 'two sum problem' and its two varieties. 02:04 Two sum problem can be solved using brute force method 04:05 Optimizing 2 Sum problem using a better solution 06:08 Using hashing to easily retrieve elements from a data structure. 08:13 Find the indexes of two elements in an array 10:30 Two pointer approach is a slightly better solution to solve the problem without using a map data structure. 12:38 Using the two-sum problem to find pairs that add up to a given target 14:51 The time complexity of the algorithm is O(n) 16:49 Space complexity and array manipulation explanation Crafted by Merlin AI.
The question is to find the indices of the elements which on adding give us the target value. In the last part of video, where we need to find the solution in O(1) space, we sort the array and hence lose the indices of input array. So how can we return the indices of elements then ?
Variant 2 solution here: class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: list = [] for i in range(0, len(nums)): list.append([nums[i], i]) list.sort() print(list) i = 0 j = len(nums)-1 while i < j: sum = list[i][0] + list[j][0] if sum == target: return(list[i][1], list[j][1]) elif sum > target: j = j-1 else: i = i+1
@@vinothkannaramsingh8224 i now python more than java......but in interveiws they ask to code in java or c++.....python sucks in dsa....that's the truth....
Using unordered_map we can do it in O(n) and even if we use ordered map we can do it in O(n*logn) and for two pointer approach we are sorting first so it is taking O(n*logn) so how is that optimal approach?
Thanks to you for the video Sir . Had a query : In Type 2 of the problem , why do we need the extra Data structure for the indices ? Because I think "left" and "right" these should be giving us the indices of the 2 numbers whose sum equals to the target .
12:36 sorting the array itself will take O(n*n) then another O(n) for the 2 pointer traverssal whick adds up to O(n*n) ruining the whole point of optimisation !
No bro when we sort using bubble sort or selection sort or insertion sort we will get O(n*2) but if we use MERGE SORT or QUICK SORT we will end up with O(N*log(N)) that’s what he is saying to do
bhaiya Third approach will not be apply if we return index of both element because if we do sort the element then automatically element indexes will be changed...
As usual you rock as you explain 🔥 Hey Raj, what if the array has duplicate elements for example, arr = [2,3,5,1,2] and target = 4 Will hashing work for this case too?.................Because hashmap has unique keys
Yes it will work beacuse we will check if the target - curr is present in the hashmap before putting the curr in map , So if the curr elem is duplicate of some element that is previiously present, we wont have to worry coz we are checking before inserting .
@takeuforward you said that in the variety 2 problem in the optimal solution we would end up taking O(2*N) space but I was thinking, can't we just return the left and right indices as integers when the sum is equal to the target?
Average and worst csse TC of unordered Hashmap is O(1) and O(N), so total TC can be O(N) or O(N^2). So how did you arrive at total TC of O(NlogN) for the better approach?
Sir has suggested to take ordered_map which has TC = O(logN) for search and insertion instead of unordered_map in case we are given with critical inputs or when problem might end up to worst case.
i got an small logic striver not so optimal for(int i = 0; i < nums.length; i++) { for(int j = i + 1; j < nums.length; j++) { if(target-(nums[i]+nums[j])==0){ return new int[]{i,j}; array:[8,4,6,12[ } ex: target =14 14-(8+4)=!0x 14-(8+6)=0 true so we wil return the indexes
def two(): nums = [3, 3] target = 6 dic = {} for i, v in enumerate(nums): dic[v] = i nums.sort() left = 0 right = len(nums) - 1 iteration = len(nums) - 1 for _ in range(iteration): if nums[left] + nums[right] == target: if dic[nums[left]] == dic[nums[right]]: a = dic[nums[left]] dic.pop(nums[left]) b = dic[nums[right]] return a, b else: return left, right elif nums[left] + nums[right] > target: right -= 1 elif nums[left] + nums[right] < target: left += 1 print(two()) Hello! Bro I am getting problem in line 22 while popping the key[3] with value (0, 1), Because its a test case of num = [3, 3] and target = 6. So, while in a dictionary when we remove a key it removes all the matching keys. Try to give us the solution with this test case --> nums = [3, 3] and Target = 6 👈🏻👈🏻 👆🏻👆🏻👆🏻👆🏻 This is my only request, Don't get frustate with my code just plz resolve this test case with your Opinion and Logic.🙏🏻🙏🏻 Please..
solve in python $$$ x=list(map(int,input().split())) x.sort() y=int(input()) for i in range(y): a=(y-x[i]) if (a in x): p=x.index(a) print(i,p) break else: continue time complexity 0(n)
Let's march ahead, and create an unmatchable DSA course! ❤
Timestamps pleaseeee
Use the problem links in the description.
0.45 - BRUTE SOL
5.13 - BETTER APPROACH (USING HASHING)
11.55 - OPTIMAL APPROACH (USING 2 POINTER)
0.45
BRUTE
5.13
BETTER
11.55
OPTIMAL
@take U forward : Hi Striver Bhaiya , I love your video , I am learning alot from you , just want to highlight in SDE sheet for this problem it's redirecting to some other question (i.e Find all pairs with a given sum) ,but it's similiar to 2sum approach only :)
it does not work on tc=-3,-2,2,3,3 any please help me out in this
@@RamanKumar-er8ie what is the target?
Striver, I cracked my coding interview by providing your optimal solution. Can’t thank you enough. You have changed lives of many. Keep doing great work ❤
Bro, can you say about your complete interview experience
Don't lie 😅
where, which company, how much lpa?
dont play games with us man
Bro, I am a guy from Africa you are the first person in this tech community that inspires me that I can do it..
Hats off for you bro 🔥🔥🔥
Bro ,I need some tips to increase my 🍆?
That's a complement to whole country..!!
no@@kulkarnisoham
yes my boy, you can do it lets gooooo !!!!
Thank you from India on behalf of Striver 😂
I can’t thank enough because you teach so well about the concepts of DSA compared to others. None of the paid resources out there have good content. All I can say is May God bless you with long life and happiness. You are making all of us to land in our dream job.
bhaiya you're so much doing for us, even you live alone in Poland, you sacrifice your time for you and I understand every thing you teach as you are so good in explaining and making people understand. once again thanks a lot for this
We need more problem solving videos. Explanation is super. I have gone through a few channels but this is the best! Thank you so much.❤️
Man you have changed a lot, this new version feels like a super saiyan mode.
Haha, experience :)
00:06 The video covers the 'two sum problem' and its two varieties.
02:04 Two sum problem can be solved using brute force method
04:05 Optimizing 2 Sum problem using a better solution
06:08 Using hashing to easily retrieve elements from a data structure.
08:13 Find the indexes of two elements in an array
10:30 Two pointer approach is a slightly better solution to solve the problem without using a map data structure.
12:38 Using the two-sum problem to find pairs that add up to a given target
14:51 The time complexity of the algorithm is O(n)
16:49 Space complexity and array manipulation explanation
@takeUforward
@takeUforward
This is the consistency we need from you bhai! 🔥
He is just insane🔥
Man after watching the first 5 videos and solving the problems on my own , I was also able to solve almost all medium and some hard problems. Watching these videos really built my logic , these lectures are a gold mine.
I didn't think about hashing but you mentioned it, I quickly coded it and got the answer. Now I just have to think of these approaches quickly
Yes even i can solve any problem using brute force approach for better & optimal i have to think....i m sure till the course end i will able to improve my solving skills..i belive ❤
@@Josuke217 same
Understood! Thanks a billion for your top-notch explaination brother!
GREAT BHAIYA I buy multiple dsa courses but i only understand with ur lectures
🤗🤗
Done this video. Amazing explanation. Learning amazing. Growing amazingly.
this 5-star add is just crazy!!
goddamn, maybe it was the first time, I understood the approach from the video and coded it on my own and got it accepted. God complex bruhh
🎯 Key Takeaways for quick navigation:
00:45 📚 *The video is part of the Striver's A to Z DSA course, covering comprehensive content with a guarantee of deep understanding in DS algo for interviews worldwide.*
01:12 🎯 *The Two Sum problem has two varieties: one asks for a yes or no if a pair with the given sum exists, and the other requires returning the indices of the pair.*
02:50 🧠 *The initial Brute Force solution involves nested loops to check every pair's sum.*
05:24 ⏩ *The improved solution uses hashing, mapping array elements to their indices, reducing time complexity to O(n).*
09:17 🚀 *The optimal approach, sorting the array and using two pointers, achieves O(n log n) time complexity without extra space.*
15:16 🔄 *The space complexity for the two-pointer approach is O(1), considering no additional space is used.*
17:50 📂 *Code for all three approaches (Brute Force, Hashing, Two-Pointer) is available in C++, Java, and Python in the video description.*
Made with HARPA AI
When he introduced two pointer method my mind was like 🤯💥 Thank you striver!!!
Bhaiya thanks for understanding from the student perspective. You are doing a really great job. Looking forward to the other problem solving videos from you. Good luck!
Raj, Thanks a lot for This Amazing Video about C++ Arrays
Video - 5 Completed ✅
I am actually preparing for my placements,now im btech 3 rd yr and i wanted someone who says from the scratch with the bestttttttt explanation.........thankyou soo muchh bro...i will follow each and every video of urs and i hope i can crack it....!!!
if you submit this two pointer approach in leet code is it accepted??
2 pointer approach was very beautiful
00:06 The video covers the 'two sum problem' and its two varieties.
02:04 Two sum problem can be solved using brute force method
04:05 Optimizing 2 Sum problem using a better solution
06:08 Using hashing to easily retrieve elements from a data structure.
08:13 Find the indexes of two elements in an array
10:30 Two pointer approach is a slightly better solution to solve the problem without using a map data structure.
12:38 Using the two-sum problem to find pairs that add up to a given target
14:51 The time complexity of the algorithm is O(n)
16:49 Space complexity and array manipulation explanation
Crafted by Merlin AI.
Understood ! This is the first ques of my challenge 😃
Thankss bhaiya for this consistency ❤️🙌
My placement is coming soon I'm in 6th semester!!🙂
me too, can we connect on linkedin?
Hello bhaiya how was it?
I'm here at 3rd sem 🤔
Hey!
Do you get the placements or how was your experience?
Understood! Super awesome explanation as always, thank you very very much for your effort!!
You are Great Sir! I love your explanation !!
Understood, Thank you strivers for this amazing video.
int main() {int n=3;
int array[3]={3,2,4}; int target=6;
for(int i=0; i
When I was asked before. I first sorted the array and done the binary search instead of hashmap to find the target. Wish i saw ur video then.
The question is to find the indices of the elements which on adding give us the target value. In the last part of video, where we need to find the solution in O(1) space, we sort the array and hence lose the indices of input array. So how can we return the indices of elements then ?
Great content it takes a lot of effort to make such hard topics enjoyable ❤
love you striver😍 you are the best teacher and mentor
understood ! very clear explanation!!
Understood!!!...Great as always. :)
let's go 28 december 🔥🔥
Top notch 🤩. Understood
Understood 🎉
40 lakh
Thanks a lot, very clear explanation
Variant 2 solution here:
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
list = []
for i in range(0, len(nums)):
list.append([nums[i], i])
list.sort()
print(list)
i = 0
j = len(nums)-1
while i < j:
sum = list[i][0] + list[j][0]
if sum == target:
return(list[i][1], list[j][1])
elif sum > target:
j = j-1
else:
i = i+1
dont do it in python
@@JK-de2gh Why ??. Python is my ♥
@@vinothkannaramsingh8224 i now python more than java......but in interveiws they ask to code in java or c++.....python sucks in dsa....that's the truth....
@@JK-de2gh Language doesn't matter bro
@ yeah unless u use any other inbuilt libraries in python that iso not present in any other languages.....
Using unordered_map we can do it in O(n) and even if we use ordered map we can do it in O(n*logn) and for two pointer approach we are sorting first so it is taking O(n*logn) so how is that optimal approach?
Two pointer approach is not that much optimal approach, but it is used when we want to find the answer without "map" data structure.
in the brute force approach you should have initialized j=i+1;
Awesome explanation, thanks a lot
Thanks to you for the video Sir .
Had a query : In Type 2 of the problem , why do we need the extra Data structure for the indices ? Because I think "left" and "right" these should be giving us the indices of the 2 numbers whose sum equals to the target .
Aftet sorting indices are changed
@@aashishomre1624 bhai return hum curly braces ma kyu nahi kar sakta hai
Bcoz return type function ka vector hai {-1,-1} indicating no pair found
vector vect{ 10, 20, 30 }; this syntax is used
Thank you so much for posting this!
Thanks sir for provide us this type of content ❤❤❤
Brute -> Better > Optimal = BEST👌
Understood. Very clear explanation
12:36
sorting the array itself will take O(n*n)
then another O(n) for the 2 pointer traverssal whick adds up to O(n*n) ruining the whole point of optimisation !
No bro when we sort using bubble sort or selection sort or insertion sort we will get O(n*2) but if we use MERGE SORT or QUICK SORT we will end up with O(N*log(N)) that’s what he is saying to do
But in this question we need to use only QUICK SORT but not MERGE SORT becoz MERGE SORT space complexity is O(N) but for Quick Sort it is O(1)
And you can see him saying it at 16:51
Got the same doubt
@@venkatesh_kensyou cleared it thanks❤
10:36
mpp.insert({nums[i], i}); is more optimised than
mpp[num] = i; (used in video)
Explain why
3:33 here you can keep j=i+1 instead of 0 so you don' need to write i==j
UNDERSTOOD!! ❤❤
HE just killed it as it says🤗
Thank u soo much Dada, u r the real inspiration. Respect++;
bhaiya Third approach will not be apply if we return index of both element because if we do sort the element then automatically element indexes will be changed...
Hats off to you striver bro
Hey Striver I am from Jupiter... I love your DSA playlist
understood. Thank youuuu
understood bhaiya! really well explained..
As usual you rock as you explain 🔥
Hey Raj, what if the array has duplicate elements
for example,
arr = [2,3,5,1,2] and target = 4
Will hashing work for this case too?.................Because hashmap has unique keys
Yes it will work beacuse we will check if the target - curr is present in the hashmap before putting the curr in map , So if the curr elem is duplicate of some element that is previiously present, we wont have to worry coz we are checking before inserting .
@@ayushmittal9666 Understood thanks
understood everything Thanks a lot sir!
Understood! great explanation
Pls make videos on sliding windows types questions and the types
Yes
Understood. Thanks a lot. Make More videos please......
Understood bhaiya 🙏 ❤️
understood everything .... thanks striver
how would you return the index of the of elements in the two-pointer case as the array is now sorted and the indices are changed?
Top notch . Understood
amazing video striver!
@takeuforward you said that in the variety 2 problem in the optimal solution we would end up taking O(2*N) space but I was thinking, can't we just return the left and right indices as integers when the sum is equal to the target?
In which lecture, do you explain the greedy approach for the first time?
understood bhaiya. u r best
you jus make things easier..
Understood! Thanks
Understood
Thank You :-)
Average and worst csse TC of unordered Hashmap is O(1) and O(N), so total TC can be O(N) or O(N^2). So how did you arrive at total TC of O(NlogN) for the better approach?
Sir has suggested to take ordered_map which has TC = O(logN) for search and insertion instead of unordered_map in case we are given with critical inputs or when problem might end up to worst case.
understand fully...😄
As usual lovely.
Job ke saath saath Padhana koi inse sikhe..🙌🙌
Understood 🔥
i got an small logic striver not so optimal
for(int i = 0; i < nums.length; i++) {
for(int j = i + 1; j < nums.length; j++) {
if(target-(nums[i]+nums[j])==0){
return new int[]{i,j};
array:[8,4,6,12[ }
ex: target =14
14-(8+4)=!0x
14-(8+6)=0 true so we wil return the indexes
striver bhaiya, thank you so much!!
Understood✅🔥🔥
I did not understand why you did mpp[a]=i at the last in the type-1 problem
How does finding take O(n^2) in the worst case for unordered_map? Isn't it O(n) due to collisions?
def two():
nums = [3, 3]
target = 6
dic = {}
for i, v in enumerate(nums):
dic[v] = i
nums.sort()
left = 0
right = len(nums) - 1
iteration = len(nums) - 1
for _ in range(iteration):
if nums[left] + nums[right] == target:
if dic[nums[left]] == dic[nums[right]]:
a = dic[nums[left]]
dic.pop(nums[left])
b = dic[nums[right]]
return a, b
else:
return left, right
elif nums[left] + nums[right] > target:
right -= 1
elif nums[left] + nums[right] < target:
left += 1
print(two())
Hello! Bro I am getting problem in line 22 while popping the key[3] with value (0, 1), Because its a test case of num = [3, 3] and target = 6.
So, while in a dictionary when we remove a key it removes all the matching keys.
Try to give us the solution with this test case --> nums = [3, 3] and Target = 6 👈🏻👈🏻
👆🏻👆🏻👆🏻👆🏻 This is my only request, Don't get frustate with my code just plz resolve this test case with your Opinion and Logic.🙏🏻🙏🏻 Please..
Great job. Thanks.
Understood 💯💯💯
Can we do this using recursion like picking up the index and not picking....please share the code for it.
even im looking for that solution
video mai jo code likha hai usme map initialize kese ho rha hai 10:36 p?
i am having trouble in understanding that when we declare a map how can we immediately start finding elements in it without filling in the values
Only after filling the map as we iterate on the array, we can find elements.
what should we do if there is more than one pair of elements adding to 14.like 8,6 in index 1 and 3.and 10,4 in 2 and 4 index
I have a doubt at 10:12 at line number 10. Why that mpp[a] = i is used there.... If any one knows please explain
same doubt
To store that key value in map...
Understood Sir!
Understood. Thank you.
solve in python
$$$
x=list(map(int,input().split()))
x.sort()
y=int(input())
for i in range(y):
a=(y-x[i])
if (a in x):
p=x.index(a)
print(i,p)
break
else:
continue
time complexity 0(n)
Understood bro.. thank you
for optimal solution why cant we return the pointer values as indexs ?? for variety 2
because after sorting the array indexes are changed
code for the better soln 16:25
Best explanation
In the better solution how can you find in the map that array element is present or not untill you put those all the elements in the hash map