Guessing complexity based off problem size
Greatest Common Deviders
def gcd(a, b): while b: a, b = b, a % b return a
Longest Increasing Subsequence
def lis(nums): tails =  for num in nums: i = bisect_left(tails, num) if i == len(tails): tails.append(num) else: tails[i] = num return len(tails)
Two Pointers Technique
- 11. Container With Most Water
- 1877. Minimize Maximum Pair Sum in Array
- 15. 3Sum solution 1
- 246. Strobogrammatic Number
- 15. 3Sum solution 3
- 31. Next Permutation
- 43. Multiply Strings
- 163. Missing Ranges
For problems on Array, Strings or Linked List, where the task is to find a subarray/ a section of the linked list satisify certain criterion. General approach is to use two pointers to indicate the left and right of the window, move, expand and contract the window along the line.
- Use some variables to summarize the window for simple questions like sum, avg.
- Use a hashmap/hashset/orderedhashmap/deque to keep track of counts of elements in the window for more complex problems.
- Think about what is the core information needed from the window that is needed to solve the problem.
- 3. Longest Substring Without Repeating Characters
- 76. Minimum Window Substring
- 159. Longest Substring with At Most Two Distinct Characters
- 340. Longest Substring with At Most K Distinct Characters