# Techniques

# Guessing complexity based off problem size

Size | Complexity |
---|---|

7 | \(O(N!)\) |

12 | \(O(2^N)\) |

16 | \(O(N^3)\) |

64 | \(O(N^2)\) |

462 | \(O(NlogN)\) |

4096 | \(O(N)\) |

\(2^4096\) | \(O(logN)\) |

Any | \(O(1)\) |

# 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

## Same sequence

### Opposite direction

- 11. Container With Most Water
- 1877. Minimize Maximum Pair Sum in Array
- 15. 3Sum solution 1
- 246. Strobogrammatic Number
### Same direction

- 15. 3Sum solution 3
- 31. Next Permutation
- 43. Multiply Strings
- 163. Missing Ranges
#### Sliding Window

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