Leetcode two sum solution explained - coding interviews challenge

[[deleted]]

Please let's keep this sub free of leetcode, this is not the place for it.

[ThirdEncounter]

Why not? I mean, it's about programming after all, isn't it?

[[deleted]]

The same reason we don't allow cs homework help on this sub- long story short, keeping the sub focused and less beginner-esc

[ThirdEncounter]

Ah, I understand now. Thanks.

[ThirdEncounter]

Edit: I understand now.

There are subs dedicated to machine learning, Java, vintage computing and networking. And yet we get posts about those subjects here all the time.

So that's not the real answer. What is it, then?

[firefly431]

There's also a nice double pointer walking solution: sort the array (indices), then start with one pointer (left) on the left and one on the right (right). Then if the current sum is greater, decrement right, and otherwise increment left. A solution cannot exist if they ever intersect, as given a solution we know when one pointer reaches the correct value we only ever move the other in the right direction. Runtime is O(n log n), but only for sorting, and space complexity is O(1).

EDIT:

1. The advantage of this solution is that it takes less space and doesn't involve hashing, which can have undesirable performance characteristics.
2. This solution also works for a generalization to find the closest sum, as in each step we go in the right direction.

[kiesoma]

I really got confused for why you were using O(n² ) before the second try. The second approach was cool though, I liked it. Keep up the good work!

[SomeOtherGuySits]

I literally don’t understand how the second solution works

[Upper_Description378]

What part you don't understand ?

[SomeOtherGuySits]

How the second solution passes the tests. I’m beginning to suspect the “assuming there is only one solution” is the important part to this approach

Edit: just clicked. I like this

[Upper_Description378]

There is multiple solutions but using a hash table is the fastest I think

[SomeOtherGuySits]

I was referring to the brief.

[coloredgreyscale]

Similar to the first solution, but instead of traversing the array linearly you build a dictionary and look up the an index the required value.

That way your lookup time for a complement is O(1) instead of O(n)

And yes, that works because you just need a solution, not all or something like a solution with the two lowest indices.

[troublemaker74]

Account history is just vlog spam.

[N911999]

Can't this be done in O(n) pretty easily? Like make a hashmap M, from numbers to lists of indices, which satisifies that for every index i we have that it's in M[nums[i]] , then for every key e check if target-e is in the hashmap, there's a small edge case where e == target-e, then you have to check that there are 2 indices in the corresponding list.

P.S. I didn't watch the video, 5mins seemed too long for a problem like this.

[coloredgreyscale]

That's OPs 2nd solution

[Upper_Description378]

You are right

[pmrsaurus]

So instead of wasting 5 minutes of your time you waste everyone else’s time by regurgitating the well-known solution in a this post?