# Coding Notes

# Array

## Operations

### Shifts

```
A = [1,2,3,4,5,6,7]; x = 3
# right shift by x -> [5,6,7,1,2,3,4]
A[-x:] + A[:-x]
# left shift by x -> [4,5,6,7,1,2,3]
A[x:] + A[:x]
# convert right shift to left shift
amt = (- x) % len(A)
A[amt:] + A[:amt] == A[-x:] + A[:-x]
# convert left shift to right shift
amt = (- x) % len(A)
A[-amt:] + A[:-amt] == A[x:] + A[:x]
```

## Techniques

### Prefix Sum / Prod

Accumulating summation or production of elements in sequence.

- Variant value to first location mapping. Prefix_sum[val] = first index idx, where sum(arr[:idx]) = val

## Two Pointers

### Annotate with sign

### Floyd’s Tortoise and Hare (Cycle Detection)

# Line Sweap

## Set

## HashMap

## Greedy

Applicable when local optimal choice always leads to global optimal.

If the problem consists of a sequence of choices, and if there does not seem to be promises that local optimal choice guarantees global optimal, then DP or backtracking?