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]

• 1427. Perform String Shifts

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

• 268. Missing Number
• 448. Find All Numbers Disappeared in an Array

Floyd’s Tortoise and Hare (Cycle Detection)

• 287. Find the Duplicate Number

Line Sweap

• 1229. Meeting Scheduler

Set

• 128. Longest Consecutive Sequence

HashMap

• 454. 4Sum II

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?

• 409. Longest Palindrome