Two Sum II - LeetCode 167 - Python

It can be really hard to know if an idea will really work or if you should dismiss it because it's wrong in subtle ways. The best programmers recognize this and take deliberate steps to get better at proving and disproving ideas, but this is super rare. Most people just throw stuff at the wall and hope that it works.

"Pray and hope" is okay at the beginner level, but will become a serious limiting factor if you want to go past that. This is why so much of my teaching is focused around helping students reason about correctness, and I try to model it as much as I can, like I did here in this video.

0:00 Two Sum II problem statement is silly
0:27 Example analysis
1:00 Exploit sorting? [Key Question]
1:33 Smallest & Largest? [Key Question]
3:57 Other Cases? [Key Question]
5:36 Time & Space Complexity
5:59 Implementation
7:40 The Rare (Killer) Skill

[nilesh]

Hey Gordon, I’ve never seen such clarity of thought when solving problems—thank you so much!

[mobiledeveloper_io]

Thanks for the video, Gordon!

I think the code becomes a bit more clear if we use a 'sum' variable for the addition of numbers[left] + numbers[right] (we'll need it in all the three conditions, so why keep the same repetitive code).

In other languages, such as Swift, the compiler would complain if we do not add return someArray at the end.
But since it doesn't make sense to add a line return [] or return [-1, -1] etc. that never gets executed, and it's generally recommended to return once (if possible), I prefer to use a break the moment I found the solution. In production code, we can also use an assert to make sure we found a valid result before returning it (won't matter much in this problem though, cause valid input is guaranteed).

Here is the Swift solution if anyone is interested:

class Solution {
func twoSum(_ numbers: [Int], _ target: Int) -> [Int] {
var left = 0
var right = numbers.count - 1
var result: [Int] = []

while left < right {
let sum = numbers[left] + numbers[right]

if sum == target {
result = [left + 1, right + 1]
break
}

sum < target ? (left += 1) : (right -= 1)
}

assert(result.count == 2)

return result
}
}