Patterns for Coding Questions: Two Pointers (Dutch National Flag) in Python

*** I TOTALLY FORGOT ABOUT RUN AND SPACE TIME What makes the two pointers pattern so great is that it is extremely efficient! For the first problem pairWithTargetSum the time complexity is O(n) because in the worst case we will need to iterate through every element in the array. The space complexity is O(1) because we don't store anything and we work on the array we are given. For the Dutch National Flag problem it is the same, O(n), because we only go through the array once. And the space complexity is also the same at O(1) because we don't take any extra space but we change the input array in place. *** In this video I explain the two pointers pattern for coding questions. I think this is probably the most practical pattern because I see it the most just in general not just in deliberate coding problems but in day to day programming. It is one of the easiest to wrap your head around. By the way I got most of these patterns from the great course on educative.io which sort of reads like a book but it also has an interactive coding pad to try out the problems yourself. I couldn't recommend it enough. Link to code: https://github.com/davearch/coding-patterns/blob/master/twoPointers.py