Arrays in Python: Two Sum Problem

In this video, we are going to be solving the so-called "Two-Sum Problem":

Correction: Note that the while condition should be altered to "!=". This change is made in the code hosted on my GitHub. Apologies for the mistake.

Problem: Given an array of integers, return indices of the two numbers such that they add up to a specific target. You may assume that each input would have exactly one solution, and you may not use the same element twice.

We investigate three different approaches to solving this problem.

Method 1: A brute-force approach that takes O(n^2) time to solve with O(1) space. We loop through the array and create all possible pairings of elements.

Method 2: A slightly better approach time-wise, taking O(n) time, but worse from a space standpoint, with a space complexity of O(n). In this approach, we make use of an auxiliary hash table to keep track of whether it's possible to construct the target based on the elements we've processed thus far in the array.

Method 3: This approach has a time complexity of O(n) and a constant space complexity, O(1). Here, we have two indices that we keep track of, one at the front and one at the back. We move either the left or right indices based on whether the sum of the elements at these indices is either greater or lesser than the target element.

The software written in this video is available at:

Do you like the development environment I'm using in this video? It's a customized version of vim that's enhanced for Python development. If you want to see how I set up my vim, I have a series on this here:

If you've found this video helpful and want to stay up-to-date with the latest videos posted on this channel, please subscribe:

[sriramradhakrishnan]

Sir, I'm going to attend coding round in a company, I don't where to study for python. Finally found yours channel. Thank you for everything, sir

[joyceguo]

The hash table explanation was so clear, thank you so much

[nackyding]

Damn. That really nice, clear and clean. Thank you.

[michaelworkspace]

You really deserved more views and subscribers. You're content are excellent and your explanations are on point. Thank you sir and keep up the amazing work!

[shubhamjaiswal]

Hello, I am very thankful for your such wonderful and detailed videos. They are helping me a lot to learn Data structure and you are such wonderful tutor.
The comment you have made at 12:48 should be
# A[i] + A[j] > target

[mateuszsmendowski]

Again I am so satisfied cause everything is clearly explained. Videos, where more than two approaches are presented, are very meaningful. We can compare which method is the most efficient. I have a lot of motivation when every day I face with your videos.
Thank you for your work, you give us a chance to develop and create our future. So helpful during studies. All the best Mr. Lucid!

[TXfoxie]

Damn. Your explanations are the most thorough ones out there. Details matter. Thank you. I will follow all your Leetcode series. You deserve way more views. The only question I have for you is:

[cnsc]

This is the only video I saw with the second and much better solution, thank you

[robn]

These videos have been very helpful. I started watching them about two to three weeks ago. When I started, I was never going to learn whiteboard code, algorithms were too hard and there was no point and it was hopeless and I was never going to get it. Now I can do most of the ones that would be considered "easy" on websites like leetcode. I'm now working on ones that are more in the "medium / intermediate" category on websites like leetcode. I want to blow my brains outs.

[msugal]

For the 3rd solution. Let us say that the arrays aren't sorted. Then that algorithm won't work unless we sort the array. So, if we resort to sorting it won't the time complexity becomes O(n log n) which is worse than O(n) in the 2nd solution.

[ThourCS]

Awesome, thank you so much for showing 3 methods.
I really like each one of your video.

[Imstupid-niwe]

finally understand that hash table explanation. Thank you so much

[joyoptimal]

Thank you. This was very helpful in understanding and easy answers. All the solutions in stackoverflow were so complex to understand and debug.

[alurma]

amazing video. explanation is very clear. thx

[prapulkrishna]

Excellent teaching and presentation. Thank you for video. This is a quality material to study.

[timothyelliott]

New subscriber. So well explained. Great teaching.

[gauravganguly]

In the third method, i think the code should be
A = [-2, 1, 2, 4, 7, 11]
target= 13
def two_sum(A, target):

i=0
j=len(A)-1
arr.sort()

while i<j:
if A[i] + A[j] == target:
print(A[i], A[j])
i += 1
continue
return True
elif A[i] + A[j] < target:
i += 1
else:
j -= 1
return False


if the array is not sorted and there are more than one pair of sum,
otherwise i will print only the first pair.


And in method 3, if you give A = [1, 2, 3, 1] and target = 5
it will give output as
Output:
1, 2
1, 2


means 1 will appear two times as A[i]
For this array should have non-repetitive values


Otherwise i prefer the second method is more accurate.

[Eva-scoe]

Dayummm... very concise and clear.. you made it easy to understand. Thanks for making this video! :)

[NaNa-ltpo]

thank you for this video. finally an explanation that i understand.

[clearwavepro]

Thank you for sharing this! Going to put on slightly slower playback next time, but perfect still :)