LeetCode Two Sum Solution Explained - Java

[@basedecho2731]

So much respect for you. You documented your grind from start to finish!

[@behindthescene4406]

Hey can u plz help me out ...at 4:42 return new int [ ] {I, j} ...is this mean creating an array whose values are i n j is this right ?

[@unknownman1]

@@behindthescene4406 correct

[@AnshumanBiswas]

Thanks, Nick! I think the reason why the execution takes more time at the end of the video is that you are performing the subtraction operation twice, rather than perform it once and only retrieve the value in two places. The original approach you showed is more efficient and the Leetcode compiler seems to agree.

[@saumya1singh]

Yuss!

[@zeitgeist18]

I was going to comment the same thing :). I have a rule, where if I'm performing the same exact calculation twice, I usually just store it in a variable and reuse that variable. It makes things easier to understand and it's actually more efficient.

[@mustafakarakas1116]

@@zeitgeist18 u are golden bro

[@tahaansari5621]

I was going to comment the same thing

[@Chauhannitin]

I believe compiler would be lot smarter to handle this. One reason could be that code is not hot when it is run first time. After multiple executions, JVM becomes more efficient and more optimised.

[@cyrilpatton238]

One thing to note: given that nums[i] is the key, if the test array (nums) has duplicate values e.g: [1, 1, 1, 14, 3, 7, 2], you will get an error for adding a new value to the hashmap with a key that already exists. Better to do num_map.put(i, nums[i])

[@vigneshk3423]

If you use something like this, how will you get the key of that particular value? and tell me the Target value.

[@aishgadol]

doing this will make you search in o(n) since you can only search for key and not value in O(1)

[@Shiva-zy7jq]

Thanks. I am gonna watch all your leetcode videos and give thumbs up to all the videos :)

[@tarunmendon]

Put "int complement=0" out of the for loop. You would get the output in 1 ms

[@xXBamboostick3Xx]

Better yet dont use a variable at all

[@ashishshah9006]

@@xXBamboostick3Xx check 9:05, it will take more time

[@xXBamboostick3Xx]

@@ashishshah9006 but also the software clearly wasn't running consistently.

[@lucaspenz5550]

It is faster to keep the subtraction into a var because it only needs to calculate once

[@saileshramesh8113]

Thank-you so much I just started learning DSA, your videos are very helpful and your doing a great job.

[@prakashkrishna2566]

Brute Force Solution: class Solution { public int[] twoSum(int[] nums, int target) { int first,comp; for(int i=0;i

[@itheblackwolfofmyfamily]

Man you look like big head from Silicon Valley movie series. Good work! Thank you for the video

[@Hgh38]

Robel Ayelew Is he lazy as big head though?

[@ahmedal-maliki4232]

It is uncanny

[@anthropomorphicOrange]

He doesn't look anything like Big Head to me. (Big Head was my favorite character on the show). I do agree that with you that Nick does an excellent job explaining the steps to solving the algorithms.

[@theindecisivegamer5036]

i keep running into missing return statment for line 15. Thanks for this video too i understand the algorithm very well. I seem to run into same problem with return statments in all my code .

[@saumya1singh]

Thanks from India! You really explain very well :)

[@vrosofficial]

Mam You are Everywhere😂😂✌✌

[@Thephantom916]

Thank you so much. You taught me how to solve this and now I know how to use hashmaps.

[@ConwellConwell]

Nick helped code 911 and grinder

[@rohitsakalle]

There is a issue in this code now based on newly test added, that what if you have duplicate items in array for example 1, 1, 1, 1, 1, 4, 1, 1, 1, 1, 1, 7, 1, 1, 1, 1, 1 and target is 11

[@hasanvizrt]

First attempt in hash map approach had slower runtime because of target-num[i] was being evaluated in every if comparison. But last solution was faster because it uses already compute value.

[@aishsaras7105]

You mean the second attempt in hash map right? in which he ditched the complement variable

[@maxstanley1818]

putting num_map.put(nums[i], i) first in the loop will actually cause an error, because the return statement will start returning values from the same indexes like [0,0].

[@P-7]

Why would that be an error (I understand that it’s not correct but why doesn’t java like it?)

[@Mkm-xt6hx]

Hi I have a question on: return int[] {num_map.get(complement), i} How does it not return [1,0], since the complement is in index 1 (7) and i is still index 0 (2) Appreciate the video and help

[@P-7]

[1, 0] and [0, 1] would both technically be correct because sums can go either way, but the way the code is written, in the first run through there will be no data to check against yet, so the value 2 is put in the hashmap, then in the second run through complement will be set to 2 (9-7) and that will be found in the hashmap. Since 2 was the complement, it will return [0, 1]. Put simply: the solution is found in the second run of the loop, not the first, so the values are reversed from what you would expect

[@Mkm-xt6hx]

@@P-7 thank you

[@Bedivine777angelprayer]

Amazing thanks for sharing having some one guide in leet ode is so great

[@annieonee]

Why can't we put the num_map.put(nums[i], i) at the beginning of the for loop? I tried that and it gives runtime error for the input [3,3]. But if I put it at the end of the for loop like in the video, it's good

[@P-7]

I’m not sure why there’s a runtime error, but putting data in the hashmap at the start won’t work because in the example input [3, 3], the number will see itself as the match, but I believe the problem wants 2 different indexes

[@SaiyaraLBS]

That’s why in the official solution they put one more condition in the if statement that map.getComplement != i

[@Shad0wB0X3r]

could anyone explain to me how the section: compliment = target - nums[i] works?

[@thedoomsday8659]

Lets say x + y = z then you can write x = z - y too, now instead of searching for x and y you can judty search x in the given array , hope i answered your query

[@thedoomsday8659]

So in this section compliment = target - num[i] we are calculating x value for every y value in linear time

[@ProdHway]

Is compliment the same as saying answer? I'm confused on why we use that word

[@syeds4380]

when you subtract target by nums[i], the number you get is the number that you now have to look for in the array in order for nums[i] + the new number to equal target. Complement just refers to the number that you now have to find by searching through the array.

[@WalkWithM3]

You are always doing good job. A bit slowe would be nice but I am a big fan of you.

[@rupaldesai7098]

Reduce the speed in setting🙈

[@Priyanka-xh9gs]

in the nested for loop solution, if you remove the throw newIllegal line since it isnt needed, then you get an error that says 'missing return statement', how do you resolve that error in a manner that does not have redundant code. Thank you in advance!

[@judeochalifu]

Every non-void method needs to return something. If you remove that statement, you have to return an empty array or null. (return int[0]) or (return null)

[@samhitasegar2864]

All your solutions are so clear!! thanks alot!! Thumbs Up to all your Videos Nick!!

[@jacobe7713]

Great explanation! Thanks Nick :)

[@behindthescene4406]

Hey can u plz help me out ...at 4:42 return new int [ ] {I, j} ...is this mean creating an array whose values are i n j is this right ?

[@surajyerramilli9255]

do I Need to write IllegalArgumentException or can i just have a print statement that says "no match found"

[@shrirambalaji2915]

Thank you man it indeed helping a lot of people like me, Thank you.

[@nanditasahu2358]

Can we use 2 pointer approach if the array is sorted??

[@csninja1150]

Yes, if the array is sorted you can use the inward walking strategy. Where one pointer is at the beginning and the other one at the end, and you compare and move them inwards until they meet or you find a solution

[@kevinrodriguez7403]

when you " if(num_map.containsKey(complement)){ return new int[] {num_map.get(complement),i}; }" why does the "num_map.get(complement)" return its index value instead of the numerical value in the that specific index?

[@abhi_in_sydney]

just one doubt :Why can't we put num_map .put(nums[i],i) before the if loop?

[@shreycodes]

Well the reason of doing num_map.put(nums[i], i) is that if you want to come back to that value in another iteration of the for-loop. This means that you have to put it after the if statement as it is something you only want to do when the if statement is not executed for any given iteration of the for-loop.

[@abhi_in_sydney]

@@shreycodes thanks for the reply..I kind of understand it now.But what would have happened if we place it before the nos will be saved accordingly don't u think

[@shreycodes]

@@abhi_in_sydney Let's take the following inputs. The list is [5, 3, 7] and 10 is the number that we want any two numbers to add to. In the first iteration of the for-loop, we are going to be looking at the 5 in the list since it is the first item. The remainder would come out to be 10 - 5 = 5. In other words, we have to find another 5 in our list to add up to 10, but we already know that there is only a single 5. Now as you said, we add the current item (5) into the HashMap which we created earlier so our entry would be (5:0) where 0 is the index. Now the if statement would see whether the remainder is a value is present in the hashmap, which it indeed is because we just added it. So the algorithm will go okay so 5 + 5 gives 10 hence the output is (0,0). We just violated the rules of the algorithm because we had said that the same number cannot be used more than once and here we just did. Hope that made sense! :)

[@abhi_in_sydney]

@@shreycodes Thanks a lot dude! You made it crystal clear!! Cheers

[@shreycodes]

@@abhi_in_sydney No worries, glad to hear it helped you :)

[@iamironman5051]

Can we do this using another array that will store given array index, and then after sorting array we can apply two pointer approach from i=0,j=n-1 ??

[@theweird_0]

why did we go nums.length in the second loop wouldn't there be an error of index outof bounds

[@madhoshyagnik3679]

Greetings Nick, why did you use the complement? I did not get that. Would you please help me?

[@BrasilEmFatos]

Same thing here. Trying to figure it out what exactly is the complement.

[@BrasilEmFatos]

Hey, what about your studies? Have a nice level of DS and Algos?

[@jeffreyawuku-boateng4018]

if complement isn't in the array why do we still need to add it to the harshMap?

[@DreamerTrain]

what if you have to return every pair and you have say {1,1,1,2} for a target sum of 2

[@JavaDeveloper-v2w]

Nice work bro.. Divide the playlist like seperate concepts

[@TheGianaJinx]

Is there a name for the specific strategy you used for the indexing in the hashmap?

[@hkhan7235]

Hashmap's are quick and useful for thousands or millions of data.

[@tusharbhapkar7296]

but how can we check contains in map if we have not added array into map ?

[@saebalam2498]

why am i getting missing return statement ? 4.40

[@tariyekorogha4980]

I think this is the nerd in me talking but this dude's smooth.👌 Edit: I hadn't gotten to the last 3 mins before I made this comment 😂. Still, cool dude.

[@dozo4748]

Why can't we: for (int i = 0; i < nums.length; i++){ num_map.put(i, nums[i]); if (num_map.containsKey(target - nums[i])) return new int[] {i, num_map.get (target - nums[i])}; } return new int[] {};

[@RanbirSingh-dl9co]

Either he is Grim reaper or he saw death with his own eyes! Love your content! No hate.

[@nutpiro343]

i don't understand the use of compliment why can't we just check if sum is equal to target

[@billseaman3103]

Sorry I am a beginner and I am a confused about why there is no " main " after "public" here. I know this is a stupid question, if any help thanks a lot.

[@tylerzuraski5823]

holy cow 2:30 am and youre grinding leet, i hope you own Google one day !

[@luanagiorgia4464]

how num_map.get(complement) shows it's index instead of it's value?

[@elyorbekibrokhimov6754]

Every element in the array is mapped to it's index. In the second iteration complement = 2 and map contains complement and it is mapped to index 1 in the above example.

[@siobhanahbois]

Method "get" in HashMap: Object get(Object key): It is used to retrieve or fetch the value mapped by a particular key.

[@ravindra1607]

See the line num. 9 he is mapping the index as the value against the value as index to make things easier while retrieving.

[@dennisnderitutv]

Great Explanation!!

[@Emperorog79]

Can we use hashset instead?

[@behindthescene4406]

Hey @Nick_White can u plz help me out ...at 4:42 return new int [ ] {I, j} ...is this mean creating an array whose values are i n j is this right ?

[@jaydave2500]

y

[@daboos8]

Thanks 🙏 great explanation

[@behindthescene4406]

Hey can u plz help me out ...at 4:42 return new int [ ] {I, j} ...is this mean creating an array whose values are i n j is this right ?

[@daboos8]

behind the scene Yes! Exactly. It saves you lines of code in this case.

[@behindthescene4406]

Awesome I guess it right as I am new to cp n not that much idea about java ..I know cpp ..

[@fit_companion]

Bro sounds like motor

[@amanpareek8056]

is there any common way to solve all these sum problems?

[@ZhouHaibo]

Is this a single pass algo?

[@乌雅成璧-g7m]

Is the complexity of checking existence of a key in a map O(1)? I thought it was O(log(n)).

[@feng282]

I mean you should just google for quick questions like this.

[@Wladik0]

if you check if there are only 2 numbers in the array you will get 99%

[@shanthureddy4234]

Thanks for your explanation

[@bigcheeseontoast9829]

i am litterally so new to coding all i know is "hello world" so the explaining here was helpful but some of still made no sense to me

[@zorainkhan4785]

Austin reaves

[@crackribswithdante7807]

Replying to this 3 years later 😎. Nick am sure by now you laugh at yourself when you watch 9:25, when you didn't know that when not using that variable, you ended up to perform the calculation twice.

[@HarshitSharma-cl6io]

I wrote the same solution but there is no return statement so its showing runtime error in leetcode. Please, help someone I want to use this solution only. public class twoSum { public int[] Solution(int [] nums , int target){ for(int i =0;i

[@coltsfancolts]

in the real world is the hashmap solution faster?

[@AdamantlyAdams]

Thank you Nick!

[@makineninaveen]

I didn't understand about 6,8,9lines

[@nagamadhu_07]

Someone teach me time complexity plz.. I can't write efficient code bcoz i m not good at time complexity!!

[@aniketdeshmane6569]

its simple, use proper data structure where required. and try to use less nested loops. :) hope this works for you!

[@rasheedolilakandy6399]

coolest explaination

[@hoata9112]

Could anyone explain the "return new int [ ] " line in the video? Thank you.

[@dman10345]

The problem ask that you return an integer array of the indices of the two elements which add up to target. So he is simply creating a new integer array and returning it. If you’re asking about how he came up with the values he placed in there then it works like this: he creates a HashMap which stores a Key-Value pair where each key has to be unique which is why looking up a key happens in constant time. First he checks to see if the complement is stored in the HashMap as a key (meaning we’ve seen it already) and if so then he creates an integer array where he accesses the HashMap key equal to the complement and the value paired with the complement key is its index in the array (e.g. [2, 7, 9, 12] the key 2 would have a value of 0, the key 7 would have a value of 1, etc) and the value of i which is the current index we are looking at in the array or the other part of the compliment. This turns out to be an array with the values { num_map.get(complement), i }. If the complement value is not found in the HashMap then that means we haven’t seen it and therefore he adds the value to the HashMap using the element value as the key and its index as the value to the pair.

[@justworkfine321]

Can you able to explain in white board?

[@QuantYogi]

with brute force, I got Time Limit Exceeded why didn't you?

[@vidzpk5144]

Leetcode probably added another test case with a bigger list. It might not have been their before

[@user-mw1qb5kd9l]

n1 + n2 = target n1 = target - n2

[@mohamedmahmoud-mv9dl]

why this is not working , private static int[] check(int[] arr , int number) { for(int i = 0; i < arr.Length; i++) { for(int k = 0; k< arr.Length; k++) { if(i!=k) { int sum = arr[i] + arr[k]; if(sum == number) { //int[] result = {}; //result.Append(i); //result.Append(k); //return result; return new int[] { i,k}; } } } } throw new IllegalArgumentException("No two sum solution"); }

[@noialbinoi3050]

Thanks man.

[@Candyroxnrulz]

Why didnt he need to import java.util?

[@BrajBliss]

LeetCode does not show the Main method and in there all the imports are done so we actually never need to import anything. All we need to do is write the code. Hope that clarifies.

[@a.yashwanth]

This is a simple problem and can be done in 2 nested for loops. for i in range(len(nums)): for j in range((I+1),len(nums)): if nums[i] == target: return [i,j] Just add element in ith index with the remaining elements on its right side one by one and check if it is equal to target.

[@gio8139]

O(n^2)

[@csninja1150]

That is definitely a valid solution just not an ideal approach. When you're solving leetcode problems you want to think about how your algorithm functions when you scale the given data set. In your case, you could be solving the exact same problem in a lot less time. And your goal should always be to solve a given problem in the least time and space complexity.

[@mohammedghabyen721]

Thank you a lot

[@sanjushekhawat6446]

Thanks

[@itheblackwolfofmyfamily]

in my leet code it said 1ms

[@sparrowkayuni5267]

mine said 36ms 💀💀

[@chiragsingla.]

@@sparrowkayuni5267 I think they increased test cases 👁️👄👁️

[@MdRizwanRabbani]

Nick rocks

[@Kakerate2]

5:30

[@mr.carthick6134]

Bro I’m watching this😞

[@rishiraj2548]

👍

[@bonle3771]

cool

[@therahul5304]

hmm no

[@peaconpramanik]

so white code bro keep up raise up the voice a little bit

[@dcyadgaroff]

Explanation from this video is terrible. Skip and watch a different video

[@delightful730]

your voice is too high.

[@Ash-td4sx]

Please give on the that darth vedor voice bro.. so annoying

[@shanthureddy4234]

Thanks for your explanation

[@inspiredsamat]

Thanks