# Techniques

## 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)
```

## 2D Array

### Location in a square matrix:

```
+ Main diagnoal is r == c
+ Off diagnoal is r + c == n - 1
```

## 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 sequence Same direction

### 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.