Puzzling Adventures - Episode 1: 2SUM

Welcome back to the second installment of this exciting series where I look at programming puzzles and go into far too extensive detail about how to solve them.

This time, we are looking at the classic 2SUM and 3SUM problems on binarysearch.com and if you watch closely - or at all - you might notice some glaring issues revealing I am still a novice at this recording and talking to an unresponsive camera thing. For instance, I got confused in the beginning and claimed binarysearch tells you about your memory usage compared to other submissions - which it does not - and later on I mixed up some words in a famous saying and completely ruining its meaning in the process. The screen section I decided to record is somewhat suboptimal and both lighting and - thanks to it - the quality of my greenscreen vary widely throughout the runtime.

Buuut, just because I suck at it doesn't mean I shouldn't try and improve myself and in the process publish something that might be of use to someone out there! So I hope you can enjoy the video and learn something from it regardless of its flaws. If so, please let me know and suggest other problems you might be interested in seeing in future videos.

Thank you very much for reading ;-)

Links to stuff mentioned in the video:

The (first) problem we solved today: https://binarysearch.com/problems/Sum-of-Two-Numbers

Blogpost with my Advent of Code solutions: https://codemetas.de/2021/04/19/Advent-of-Code-2020.html

Variations we looked at(in order of appearance): https://binarysearch.com/problems/Sum-of-Two-Numbers-with-Sorted-List https://binarysearch.com/problems/Lowest-Sum-of-Pair-Larger-than-Target https://binarysearch.com/problems/Sum-of-Three-Numbers https://binarysearch.com/problems/Pythagorean-Triplets

Stackexchange post about generalized k-sum: https://cs.stackexchange.com/questions/2973/generalised-3sum-k-sum-problem

Timestamps:

0:00 Introducing binarysearch.com 2:45 Problem Statement 5:10 Brute Force Solution 7:25 Better Brute Force Solution 8:52 Wasted Effort 10:55 Binary Search Explanation 20:57 Binary Seach Based Solution 27:17 Inward Walk Explanation 35:22 Inward Walk Solution 39:14 Hashset Besed Solution 44:14 Wasting Memory 51:35 Variation 0: Pre-sorted Values 53:40 Variation 1: Largest sum smaller than target 56:48 3SUM 1:00:48 3SUM Variation: Pythagorean Triplets 1:05:27 The End 1:06:35 Begging