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

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.

  1. Use some variables to summarize the window for simple questions like sum, avg.
  2. Use a hashmap/hashset/orderedhashmap/deque to keep track of counts of elements in the window for more complex problems.
  3. Think about what is the core information needed from the window that is needed to solve the problem.

Two sequences

Linked List

Example Questions