Algorithms Notes

Last Updated: 22 Sept 2025

Terms to remember

Boustrophedon style : iteration like snake and ladder board

Range update in O(1) :

a[], get diff[],
range_update(l, r, val) -> diff[l] += val; diff[r+1] -=val
get a[] -> a[0] = diff[0]; a[i] = a[i-1] + diff[i]; ignore last number
📌 NOTE : Do precomputation if TLE.

DSU :

use chaining to define set, defined by parent-child relationship.
AR(x) : find topmost parent of x
Find(x, y) : check if x and y in same set
Union (x, y) : connect AR(x) to AR(y)
Cannot be used to detect cycle in directed graph, but possible in undirected

for(auto p:edgeList){  
    int fromP = find(p.first);  
    int toP = find(p.second);  
    if(fromP == toP)    //do cyclic condition work  
    union_op(fromP, toP);  
}

Brute force O(N) :

int find(int v):  
    if(dsuf[v] == -1): # can also have root point to same no and check to see if v equal to dsuf[v]  
        return v;  
    return find(dsuf[v]);  

void union_op(int a, int b):  
    int aa = find(a);  
    int bb = find(b);  
    dsuf[aa] = bb;

Optimized O(log N) :

do path compression, dsuf arr stores end parent only
rank and height are initially same but, after path compression, height is reduced but rank will be same
union by rank is done to make height less in union operation

int find_path_compression(int v):  
    if(dsuf[v] == -1):  
        return v  
    dsuf[v].parent = find(dsuf[v].parent)  
    return dsuf[v].parent  

void union_by_rank(int a, int b):    // height/rank not changed  
    if(dsuf[a].rank > dsuf[b].rank):  
        dsuf[a].parent = b  
    else if(dsuf[a].rank < dsuf[b].rank):  
        dsuf[a].parent = b  
    else:  
        dsuf[a].parent = b  
        dsuf[b].rank +=1

Digits DP

Below is implemention of check in range of numbers, how many digits are 3

int dp[20][2][20]; // index, tight, count  
int solve(string s, int idx, int tight, int cnt):  
    if(idx == s.size():   
        return cnt  
    if(dp[idx][tight][cnt] != -1):   
        return dp[idx][tight][cnt]  
    int limit = (tight==1) ? (s[idx)-'0' : 9)  
    for(int i=0; i<=limit; i++):  
         int updateCnt = cnt + (i==3 ? 1:0); // as per question  
         int nxtTight = tight & (i == s[idx]-'0')  
         ans += solve(s,idx+1, nxtTight, updateCnt)  
    return dp[idx][tight][cnt] = ans  

int main():  
    int lLimit, rLimit;  
    string ri = to_str(rLimit), le = to_str(lLimit)  
    dp = {-1}  
    int rAns = solve(ri, 0, 1, 0)  
    dp = {-1}  
    int lAns  = solv(li, 0, 1, 0)  
    return (rAns - lAns)

Segment Tree

Good for range query when no of update operations is high.

Update : O(U logN); U is no of update operations
Query : O(q logN) ; q is no of queries
No of nodes in ST : (2*N-1)

int constructST(St, si, arr, l, r):  
    if l==r: # leaf node  
        st[si] = arr[l]  
        return arr[l]  
    mid = (l+r)/2  
    st[si] = constructST(st, 2*si+1, arr, l, mid) +   
             constructST(st, 2*si+2, arr, mid+1, r) # for sum question  
    return st[si]  

int getSum(int si, int sl, int sr, int l, int r):  
    if(l <= sl && r >= sr):        # Total Overlap  
        return st[si]  
    if(sr < l || sl > r):          # No Overlap  
        return 0  
    mid = (sl + sr)/2;             # Partial Overlap  
    return getsum(2*si+1, sl, mid, l, r) +   
           getsum(2*si+2, mid+1, sr, l, r)  

void update( si, sl, sr, pos, diff): # update over range  
    if( sl > ps || sr < pos):  
        return  
    s[si] += diff  
    if(sl !- sr):  
        mid = (sl+sr)/2  
        update(2*si+1, sl, mid, pos, diff)  
        update(2*si+2, mid+1, sr, pos, diff)

Fenwick / Binary Indexed Tree

Updates and prefix sum Queries in O(log n), just like segment tree, only easier to remember code
memory is little less than seg tree
Seg tree advantage is that it Supports arbitrary range queries: Not limited to prefix sums.
Also Seg tree can handle custom operation like min, max, gcd, xor, etc.

int[] constructFT(int arr[], int n):  
    int fTree[n+1]  
    for i in range(1,n+1):  
        fTree[i] = 0  
    for i in range(n):  
        updateFT(fTree, n, i, arr[i])  
    return fTree  

def updateFT(int fTree[], int n, int index, int diff):  
    index += 1  
    while(index <= n):  
        fTree[index] += diff  
        index += index & (-index)  

int getSum(int fTree[], int index):  
    int sum = 0  
    index +=  1  
    while(index > 0):  
        sum += fTree[index]  
        index -= index & (-index)  
    return sum

Get number in diff base

def to_base(n, k):  
    digit=0  
    while (x):  
        digit = digit*10 + x%k  
        x /= k  
    return digit

Sum of 1st n palindromes

def first_n_palindromes(n):  
    int left=1, count=0;  
    long long ans=0  
    while (count < n):  
        int right = left * 10  
        # op = 0 indicates enumerating odd-length palindromes  
        # op = 1 indicates enumerating even-length palindromes  
        for (int op=0; op 2; ++op) :  
            # enumerate i' . i will be all numbers in   
            for (int i=left; i<right && count<n; ++i) :  
                long long combined = i  
                int x = (op==0 ? i/10 : i)  
                while (x) :  
                    combined = combined*10 + x%10  
                    x /= 10  
                ++count  
                ans += combined  
        left = right  
    return count

Topological Sort

Topological sort is a way to linearly order the nodes of a Directed Acyclic Graph (DAG) such that for every edge u → v, node u comes before v.

Below is code for bfs with cycle detection for topo sort. Especially useful for Course Schedule problems.

# given adj and n vertices  
def topo_sort():  
    int inDegree[n] = {0}  
    for x in adj:  
        for y in x:  
              inDegree[y]++  
    queue<int> q;        
    for i in range(n):  
        if inDegree[i] == 0 :  
            q.push(i)  
    topo = []  
    while !q.empty():  
        int node = q.front(); q.pop()  
        topo.append(node)  
        for x in adj[node]:  
            inDegree[x]--  
            if(inDegree[x]==0)  
                q.push(x)  

    if len(topo) == n:  
        return topo  
    # if all elements arent present, its cyclic so return empty  
    return {}