Is this how you're supposed to solve coding tests?... Solving timeouts with 'Two Pointers'
I had a coding test problem that kept failing due to timeouts, so I checked other people's solutions and almost all of them used a technique called 'Two Pointers'. It's a way to reduce a double for loop from O(n^2) to O(n).
I get the part about sorting the array and adjusting the left and right indices to search... but I don't intuitively understand why this guarantees an optimal solution. Anyone able to recommend search keywords or YouTube videos on this concept?
3 answers
Yeah, two pointer is the most basic of basics lol
I didn't get it at first either, but if you actually draw it out, you'll see why it's O(n). The left/right pointers each move up to n times, so that's 2n total, which is O(n). And since the array is sorted, moving only one side based on the condition still guarantees the answer. Instead of watching videos, search for 'Two Pointer Two Sum' and walk through an example by hand. It shows up a lot in coding tests, so it's worth getting comfortable with it.
Well... isn't that only true for sorted arrays? If you need to preserve the original order or can't sort, you can't use two pointers. It depends on the problem—double for loops aren't necessarily slow. Feeling that it's not guaranteed might actually be the right intuition.