Time Complexity

get sublist/substring
- continuous substring: O(N^2)
- any substring/sublist without changing order O(2^N) ?

#Tips:

Bug-free

consider start and end index
for list, the last index is not included in the actual list, carefully when calculating the length of subarray/sublist
- array[a:b] is array[a], array[a+1], …, array[b-1], with length of (b-1) - a + 1 = b - a
- items between index a and b are array[a], array[a+1], …, array[b] , with length of b - a + 1
think about duplications
check upper/lower cases
check the variables names especially when handling curr_item and next_item in recursive calls

Optimization

DP
DFS + memorization
bit manipulation

Tricks

array

The first typical way to solve circular array problems is to extend the original array to twice length, 2nd half has the same element as first half. Then everything become simple.
The second way is to use a stack to facilitate the look up
two pass: forward and backward
two points: start and end
sort + points / dict for n-sum problems

Intervals:

Evidently, two events [s1, e1) and [s2, e2) do not conflict if and only if one of them starts after the other one ends: either e1 <= s2 OR e2 <= s1. By De Morgan’s laws, this means the events conflict when s1 < e2 AND s2 < e1.

graph/matrix

use index i,j instead of x,y whenever you can in matrix to avoid mistakes on handling boundaries
matrix diagonal indexes meet one of the following requirements:
- i + j = Constant
- i - j = Constant
Take advantage of Counter/dict to record states while doing one pass scan for matrix/graph

String

regex/matching: consider dp (bottom up)
calculator: use stack, sign, num, or op_stack + num_stack
pre calculate the values if there are limited possibilities (e.g. Roman number)

Tokenize the input array/string

tokens = filter(bool, re.split('([A-Z]{1}[a-z]?|\)|\(|\d+)', formula))

DP

use when next step is relied on prev step / prev state and nothing else
rolling array/Counter to save space (2D DP -> 1D DP)

Recursive

order of eval and tmp vairables matters
make sure to use local variable for recursive comparision instead of global variable if necessary

Bit Manuiplition

<<= 1 to speed things up (e.g. divide, 1, 2, 4, 8, … * factor)
random number:

https://leetcode.com/problems/linked-list-random-node/discuss/85659/Brief-explanation-for-Reservoir-Sampling
O(1) Space reservoir-sampling

# Assume that you have the memory to store k elements
import random
def random_subset( iterator, K ):
    result = []
    N = 0
    for item in iterator:
        N += 1
        if len(result) < K:
            result.append( item )
        else:
            s = random.randint(0, N-1)
            if s < K:
                result[s] = item
    return result