# 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

# Line Sweap

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