DSA - Revision

This covers standard DSA questions and concepts for revision purposes - Topic wise

~ Tools and Intuition

Fundamentals

• Ascii of 0 → 48 , A-Z [65 - 90], a - z [97-122] ,

• char in c++ is 1 byte or 8 bits so it can take value 0-255 (2^8-1). Now signed char takes values [-128,127], Unsigned char : [0-255]

• using for type aliases.

char c = 200;
unsigned char d = 200;
cout << (int)c; // -56
cout << (int)d; // 200

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
int main() {
    ll x;
    cin >> x;
    cout << x;
}

C++ Memory Information (Pointers / references and addresses….)

int a = 5, b = 10;
int *p = &a; // Pointer to 'a' ( p points to memory of a)
// p holds address of where `a` is stored
p = &b; // Now points to 'b'

int &r = a; // Reference to 'a' , no new memory is allocated
// r is alias to a , any operation on r affects a
// r = &b; // ❌ Error: A reference cannot be changed to refer to another variable

r = b; // ✅ Changes the value of 'a' to 10 (not reassigning reference)

Questions

⇒ Step1 → Solve this sheet for revision purposes

⇒ Step2 → Striver SDE sheet , Striver A-Z sheet , Leetcode 150

⇒ Step3 → Leetcode company wise and random problems…

⇒ Step4 → Revisit the Additional DSA problems from this sheet → Additional DSA

→ For syntax refer Codes , for solutions and concepts refer Notes…

Math and Geometry

Formulas

1. Euclidean GCD O(log(N)) , Ques

2. Prime or Not - $O(\sqrt{N})$

3. Sieve of Eratosthenes [Ques] → Number of prime numbers up to $N$ in $O(N \log \log N)$

4. x^n % M in Log(N) → [Concept]

5. Factors of N → $O(\sqrt{N})$

   1. [Better] Factors of N → $O(N^{1/3})$

6. Find all prime factors of N smallest prime factor → $O(\log N)$, $O(1)$

   1. Initially my idea was to calculate factors of $N$ in $O(\sqrt{N})$, then loop over every factor and check if prime or not using a precomputed sieve.

   2. GFG has a better solution by dividing by spf[i] → $O(\log N)$ per query

7. nCr, [Ques]

8. Trailing Zero in factorial of a number

Questions

9. Factor Combinations

10. Bulb switcher → Mind Fuck

11. Min number of operations required to reduce n -> 0 → Beautiful….

12. Triangular sum of array O(N) solution

Arrays and String

1. Find 2nd String in 1st String

2. Unique Length-3 Palindromic Subsequences

3. All pairs with Given Sum

4. Given array of non negative integers, find number of subarrays with sum b/w B-C O(N)

5. Merge sorted arrays without extra space O(N) , O(1)

6. Two Sum 2 - Input Array Sorted - O(N) , O(1)

7. Subarray with 0 Sum - O(N), O(N)

8. Triplets with 0 sum - O(N2) , O(1)

9. Celebrity Problem

10. Find all anagrams in given string - O(N) , O(1)

11. Dictionary matching problem - O(N) , O(N)

12. Find the majority element in the array O(N) O(1)

13. Subarrays with B-odd numbers

14. Count Subarrays with sum = k O(N) O(N)

15. Subarray with Given XOR O(N) O(N)

16. Next Permutation O(N) , O(1)

17. Longest Substring with K distinct characters O(N) O(k)

18. Maximum ones after modification O(N) O(1)

19. Subarrays with K distinct Integers O(N) O(k)

20. Longest substring without repeating characters O(N), O(1)

21. Count Inversion Problem O(NlogN) , O(N)

22. Maximum Size Subarray Sum Equals k O(N) , O(N)

23. Sort Colors O(N), O(1)

24. Longest subarray with 0 sum O(N), O(N)

25. Longest consecutive sequence O(N) O(N)

26. Maximum subarray sum O(N) , O(1)

27. Maximum subarray size having all subarrays sums less than k O(N) O(1)

28. Check if 2 strings are rotation of each other O(N)

29. Lexicographic rank of a String O(N)

30. Closest pair from 2 sorted arrays - O(N+M)

Pattern Matching

31. KMP search for pattern matching O(n+M)

32. Rabin Karp

33. Z algorithm pattern matching

Stack and Queues

1. NSL - Nearest smallest left - O(N), O(N)

2. NSR - Nearest smallest right - O(N), O(N)

3. Infix to Postfix - O(N), O(N)

4. Stock Span Problem - O(N), O(N)

5. Reverse Polish / Prefix Evaluation - O(N) , O(N)

6. Maximum Rectangle area in Histogram - O(N) , O(N)

7. Trapping rainwater problem O(N) , O(N)

8. Sliding window maximum O(N) , O(k)

9. Max rectangle area in a matrix O(R.C) , O(R.C)

10. Longest valid parentheses O(N) , O(1)

11. Reverse stack without using extra space in O(N)

12. Sort Stack using recursion O(N2) , O(N)

13. Max stack in O(1) time (see the solution i have explained the intuition)

14. Valid Parentheses 2 O(N) , O(N)

15. Josephus Problem O(N) , O(1)

Linked List

1. Concepts Link list

2. Remove loop in link list O(N) O(1)

3. Length of cycle in link list O(N) O(1)

4. Reverse a Link list

5. Reverse Nodes in K group O(N)/

6. Sort a K sorted Linked list O(nlogk) , O(k)

7. Find starting point of the loop O(N), O(1)

8. Intersection of 2 Linked List O(N) , O(1)

9. Reverse Alternate K nodes O(N) , O(1)

10. Clone a Linked list with random pointer O(N), O(N)

Binary Search

1. Median in row-wise sorted matrix

2. WoodCutting Problem

3. K closes elements to given value

4. Search in rotated array

5. Find peak element

6. Median of 2 sorted array

7. Sqrt of x

8. Woodcutting problem

9. Search in row-wise and co-wise sorted matrix

10. Position of element in infinite sorted array

11. Painter partition problem

Greedy and Sorting

Sorting

• Algo that takes minimum number of writes → Selection sort

• Quick sort for array and merge sort for link list → O(N) swaps

• Inplace(doesn’t need extra space) → Bubble , Insertion, Quick sort , Selection

• Stable(2 elements equal value appears in same order as in normal array)

  • Bubble sort , Insertion , Merge sort

• Best case time complexity

  • Quick Sort → Best (O(Nlogn) , Worst → O(n2)

  • Bubble sort → Best (O(N)) , Worst → O(n^2)

• Radix Sort ( for fixed numbers in very large datasets )

  • len(d) < log2(N) → Radix sort makes sense

  • Sorting in O(N) time → O(n.d) , d is number of digits

1. Task Scheduler

2. Find time where max guests are in party

3. Merge intervals problem

4. Arrange to get largest number in the array

5. JobSequencing problem

6. Fractional Knapsack problem

7. Intersection of all intervals

8. Insert interval in non-overlapping interval

9. Activity selection problem

10. Candy Problem

11. Jump Game 1 , Jump Game 2 - O(N^2) and O(N) solution

12. Minimum number of platforms

Heap

1. Concepts

2. Sort K sorted array

3. Find kth largest element in the array

4. Median in a Stream

5. Merge K sorted arrays

6. Connect ropes to minimize the cost

7. Kth smallest element in row wise and column wise sorted matrix (O(N) - Best)

8. K closest elements to a given value in unsorted array

BIT Manipulation

1. Count Set bits

2. Two odd occurring elements

3. All elements occur twice except for one (Sorted)

4. Minimum Bit Flips to convert A to B

5. Every element occurs thrice except for one

6. Check if binary representation is pallindrome

7. Reverse bits of a number

Recursion / BackTracking

1. Reverse stack using recursion

2. Kth symbol in grammar

3. Sort array using recursion

4. All Permutation of a number

5. Tower of Hanoi - Recursion

6. Generate All subsets

7. All permutations of a string with spaces

8. Permutation of a string by changing case

9. Generate All balanced parentheses

10. Generate all unique permutation of a string

11. N Queen Problem

12. Rat in a Maze problem

13. Sudoku solver

14. Find all subsets with given Sum

15. Combination Sum

16. Print all subsequences of a string

17. Knight Walk

———————————————————————————————————————

All the above topics cover basic problems now you come down to topics where most of the companies ask interview questions. So the best way is to solve as many questions as possible

Binary Tree

1. Concepts

2. Zig-Zag order traversal

3. Max-width of Binary tree

4. Left view , Right view , Vertical order traversal , Top view binary tree, Bottom view

5. Height of BT , Balanced B.T (AVL Red-Black Tree)

6. Print Root to Node path in BT If exists (check notes)

7. Invert a binary tree

8. Check if tree is symmetric

9. Deepest node in binary tree

10. Check for children sum prop in BT

11. LCA binary tree

12. Binary tree from inorder and preorder

13. Max edge removal to make even forest

14. Nodes at K distance binary tree

15. Diameter of a Binary tree

16. Diameter of N-ary tree

17. Print Longest path from Root to Leaf

18. Max path sum (Leaf - Leaf)

19. Max path sum from any node to any node

20. Max Path sum from Root to Leaf

21. Distance b/w 2 nodes of a BT

22. Flatten BT to Linked List

Binary Search Tree

1. Insert in BST , Search in BST , Delete a Node in BST

2. Ceil BST

3. Floor BST

4. Check if BT is a BST

5. LCA in BST

6. Sorted Array to BST

7. BST from preorder array

8. Check if array is valid PreOrder for BST

9. Kth Smallest element in BST

10. BST with N keys (Nth catalan number) → see notes…

11. Inorder successor and predecessor in BST

12. Correct BST with 2 nodes swapped

13. Pair with given sum - BST

14. Largest BST in BT

Graphs

1. Concepts codes → BFS , DFS

2. BFS , DFS recursive , Iterative DFS , BFS on 2D matrix , DFS on 2D matrix

3. Cycle Detection | Undirected graph | (BFS and DFS)

4. Cycle Detection | Directed Graph | (BFS and DFS)

5. Topo Sort BFS , Topo Sort DFS [DAG]

6. Bipartite Graph (BFS and DFS)

7. Dijaktras - Single source shortest path (Directed | Undirected) [ No negative edges ]

8. Bellman Ford - Single source shortest path (Negative edges)

9. Single source shortest path | DAG

10. Single source shortest path in Undirected graph with unit distance

11. Floyd Warshall - Single source shortest path for all pairs O(V^3)

12. MST { N nodes N-1 Edges } [ Intuition ]

    1. Kruskal MST

    2. Prims Algo MST

Other Algos

13. Strongly Connected Components - O(V+E) / O(V) [ Intuition ] [ Ques ]

14. Bridges in a graph - Tarjan Algo (O(V+E) / O(V)) [ Intuition ] [ Ques ]

15. Articulation Point - O(V + E) / O(V) [ Intuition ] [ Ques ]

Questions

16. Rotten Oranges

17. Number of islands in a graph

18. Word Search (Very basic problem but you always forget to do one step…)

19. Word Search 2 [ nice application ]

20. Snakes and Ladders (Very IMP question → BFS vs DFS)

21. Number of Connected components in a graph

22. Evaluate Division [ Gaand phat jyga but medium]

23. Word Ladder

24. Word Ladder 2 [ all possible paths ]

25. Swimming in a rising water

26. Minimize Malware spread - 2

DP

1-D / 2-D DP

1. Weighted Job Scheduling

2. Climbing stairs

3. Ugly number , Ugly number 2

4. Min cost to reach end if Max K jumps are allowed

5. House Robber

6. House Robber 2

7. Cherry pickup

8. Min cost path

9. Unique paths , Unique paths 2

10. Maximal Square

11. Queen Attack

12. Min Falling path sum in matrix

13. Number of ways to decode

14. Max sum rectangle in 2-D matrix

15. Longest AP sequence

16. Word Break

17. Longest Increasing Pairs

18. Box Stacking Problem

19. Count N digit number having no pair of consecutive digits

20. Predict the winner - Optimal strategy

21. Dungeon Game

22. Number of dice rolls with target sum

KnapSack and String

1. 0/1 Knapsack problem

2. Subset Sum

3. Target Sum

4. Count Subsets with Given sum

5. Partition into K equal subsets - This looks like the above problem but isn’t

6. Rod cutting

7. LCS

8. Print LCS

9. Min Subset sum difference

10. Coin change 2

11. Maximum length of repeated subarray

12. Maximum ribbon cut

13. Count number of subsets with given difference

14. Longest pallindromic subsequence , Pallindromic substrings

The only thing the above problems have taught me is that there is always an easier way to solve a problem and if you don’t know any other way of solving than your own… you’ve probably memorized the solution (even without knowing it 🙂)

15. LIS

16. LIS (NLogN)

17. Print LIS

18. Coin change

19. String interleaving

20. Shortest common supersequence

21. Print Shortest common supersequence

22. Longest pallindromic substring

23. Minimum deletion to make string pallindrome

24. Longest Bitonic Sequence

25. Min Deletions to make sorted sequence

26. Minimum number of insertion / deletion to convert a-->b

27. Minimum insertion to make string pallindrome

28. Longest Alternating subsequence

29. Edit distance

30. Longest Repeating Subsequence

31. Max Product cutting

32. Count all pallindromic substrings

Partition DP

33. Most Efficient way to multiply matrix

34. Boolean Parenthesis

35. Pallindrome partitioning

36. Egg dropping problem

37. Number of Ways to Write N as Sum of 1,3,4

38. Scramble String

39. Min/Max value of an expression

Advanced Data Structures and Algorithms

For these refer to Notes / Striver sheet

DSU

• Concepts

• Minimum Operations to make network connected

• Most Stones Removed with Same Row or Column

• Most stones removed with same row or col

• Number of Island - 2 [ Nice ]

• Minimum Time for K connected Components [Nice]

• Making a Large Island

• Account Merge

Tries

• Concept

• Word Break (Trie)

• Implement Trie Implement Trie 2

• Longest String with All prefixes

• Number of unique substrings in a string

• Maximum XOR of 2 numbers in array

• Word Search 2

• Pallindromic Pairs

• Stream of Characters

Segment Trees

Concept , More Practice

Fenwick Trees

Solutions / Concepts

MATH

Formulas

Modular Arithmetic

$$(a + b) \bmod m = ((a \bmod m) + (b \bmod m)) \bmod m$$

$$(a \cdot b) \bmod m = ((a \bmod m) \cdot (b \bmod m)) \bmod m$$

$$x^n \bmod m = ((x \bmod m)^n) \bmod m$$

• The number of digits of an integer $x$ in base $b$ is $\lfloor \log_b x \rfloor + 1$

• GP sum

  • Nth term ⇒ $T_n = ar^{n-1}$

  • Sum up to $N$ ⇒ $S_n = \frac{a(r^n-1)}{r-1}$

  • Infinite sum ⇒ $S_\infty = \frac{a}{1-r}$

Euclidean GCD Sol

If we subtract a smaller number from a larger one (we reduce a larger number), GCD doesn't change. So if we keep subtracting repeatedly the larger of two, we end up with GCD.

int findGCD(int a, int b) {
    if (a == 0)
        return b;
    return findGCD(b % a, a);
}

Modular Arithmetic

Recursive

int power(int x, int n, int M) {
    if (n == 0)
        return 1;
    if (n == 1)
        return x;

    long long res = power(x, n / 2, M);

    res = (res * res) % M;

    if (n % 2 == 0)
        return res % M;
    else
        return (res * x) % M;
}

Iterative

int power(x, n) {
    long long res = 1;
    while (n > 0) {
        if (n % 2 == 0) {
            res = res * x;
        } else
            x = x * x;
        n = n / 2;
    }
    return res;
}

Sieve Of Erantosheneus

→ Find all prime numbers upto N

int checkIfPrime(int n) {
    vector<int> sieve(n + 1, 1); // initially all are prime
    sieve[0] = sieve[1] = 0;     // obviously
    for (int i = 2; i <= sqrt(n); i++) {
        // if number is prime
        if (sieve[i] == 1) {
            // mark all factors of i as non-prime
            // start with i*i as (5,2) will be covered in (2,5)
            for (int j = i; i * j <= n; j++) {
                sieve[i * j] = 0;
            }
        }
    }
    return sieve[n];
}

nCr in O(r)

int nCr(int n, int r) {
    long long sum = 1;
    for (int i = 1; i <= r; i++) {
        sum = (sum * (n - i + 1)) / i;
    }
    return sum;
}

LINKED LIST

struct Node {
    int data;
    Node *next;

    Node(int val) {
        data = val;
        next = nullptr;
    }
};

void printLinkList(Node *a) {
    Node *head = a;
    while (head != nullptr) {
        cout << head->data << " ";
        head = head->next;
    }
}

// main
Node *a = new Node(5);
Node *b = new Node(10);
a->next = b;
print(a);

Trees

class Node {
  public:
    int data;
    Node *left;
    Node *right;
    Node(int val) {
        data = val;
        left = NULL;
        right = NULL;
    }
};
// main
Node *root = new Node(10);
Node *leftNode = new Node(11);
Node *rightNode = new Node(9);
root->left = leftNode;
root->right = rightNode;

Theory

1. Inorder traversal , Preorder traversal , Postorder traversal

2. Level order Traversal

3. Inorder (Without recursion) , Iterative Preorder , Iterative Postorder

4. Max nodes in a binary tree of height $h$ ⇒ $2^{h+1}-1$ (complete/perfect binary tree)

5. Binary tree with $n$ nodes and minimum possible height ⇒ $\lceil \log_2(n+1) \rceil - 1$

6. Complete B.T → All levels are filled except the last level. The last level filled left to right.

7. Perfect B.T → All leaf nodes are at the same level, every internal node has two children, and height = $\lfloor \log_2 N \rfloor$

Concepts in Heap

A Heap is a complete binary tree that satisfies the heap property.

Types

• Max Heap → Parent ≥ children

• Min Heap → Parent ≤ children

$$\operatorname{Root} = A[0], \quad \operatorname{Parent}(i) = A[\lfloor(i-1)/2\rfloor]$$

$$\operatorname{Left}(i) = A[2i+1], \quad \operatorname{Right}(i) = A[2i+2]$$

1. Insertion and deletion in Heap - O(log(K)) , K = number of elements in Heap.

   1. Insert : Just insert at the end → Heapify upwards

   2. Delete : delete the top element → copy last element to top → Heapify downwards

2. Heapify (how does it work) MaxHeap

   1. HeapifyUp - Compare with parent element and swap if parent is smaller.

   2. HeapifyDown - Compare with both children and find the biggest and swap parent with that.

Graphs

1. Adjacency List , Adjacency Matrix

• Adjacency list is generally represented as :

  • vector<int> g[N+1] for (N nodes 1 index) { Array of vectors }

• Adjacency matrix

  • vector<vector<int>> g(N+1, vector<int>(N+1,0)) { 2-D matrix fixed size }

• As you can see for memory usage adjacency list is far better as it only covers nodes with edges and adjacency matrix will take (NxN) space even for sparse graphs

• But if you have frequent operations to check if 2 nodes are connected, then adjacency matrix is better O(1) than adjacency list O(N).

  • Now you’ll say if we represent unordered_set<int> g[N] then we can query if 2 nodes are connected in O(1) right ?

  • YES but this uses Hashing and hash functions so the overhead is that of hash function and how strong your load factor is to avoid hash collision, this works very well for sparse graphs.

  • But for dense graphs or or when adjacency queries dominate and you don’t need neighbor iteration, adjacency matrix still beats your hash based adjacency list.

  • Also iteration in unordered_set<int> has worse cache locality than a flat vector<int>.The vector<int> stores elements sequentially whereas unordered_set use hash tables for storing elements and usually stores 0 or more elements that hash to the same index.

BFS vs DFS

Snakes and Ladders

• I tried this problem using DFS and wasted 2 hrs. The thing is DFS explores all the paths to reach the end. I was thinking of kind of DP way exploring all paths and using memoization which will give the answer but will waste a lot of time. Here every cell is a node which is connected to each other if it’s reachable the cost of moving from one cell to another is same. So it’s kind of like a unweighted graph where you have to find min cost to reach at the end and BFS does in O(N) or O(n*n)

• DP and recursion usually works when The graph has varying edge weights (so you can’t just rely on first-come-first-serve like BFS).

• Or when order matters, like sequences (LCS, LIS, knapsack).

  • In this board, every move costs the same (1 dice throw). So BFS explores all nodes in increasing number of moves, layer by layer. That’s why BFS gives the correct minimum steps without any need for recursion or DP.

Could BFS work for other “min cost” DP problems?

• All moves have the same cost (or we can model cost by level).

• Transitions form a directed acyclic or unweighted graph

Example for BFS

• Minimum jumps to reach end , Minimum number of operations to reach X from 1 ,

• Minimum path sum in a grid ❌BFS

  • costs vary per cell BFS fails because edges have weights; we need Dijkstra or DP.

In BFS the first time you reach a node is always the shortest path. You never need to update it.

Minimum Spanning Tree

A spanning Tree consists of N nodes , N-1 edges. Minimum spanning tree is a spanning tree with the sum of weights of all edges is minimal.

• The whole Spanning tree concept is defined for Un-directed graphs. And basically Spanning tree is a tree so it is acyclic and has N-1 edges

• Also yeah in MST or any spanning tree every node by definition is mutually reachable.

🌈 Imagine there are 4 cities and you have to connect them with Fibre Optics Cable, in such a way that overall cost is minimum. Cost of Connecting A→B is given as edge in the graph

→ Here your main idea is to find an MST.

Algorithms

Kruskal

Kruskal's idea was that we will always select the minimum edge and include it. But if adding an edge forms a cycle we’ll skip that.

How to know if adding an edge forms a cycle ? → If both the nodes are in the same component.

• So we’ll start by sorting the edges in ascending order of weight.

• Process edges one by one

  • If both nodes belong to the same super parent (DSU) → skip it [cycle]

  • Else Include them in MST Union(u,v)

Prim’s Algorithm

Prim’s idea works on Greedy by maintaining a min-heap of { wt, v, u } for edge u – v

• Pick any start vertex s → Add it to min-heap

• Continue until heap is empty

  • Pop the element and check if that node(v) is already visited if yes → skip

  • Else mark it as visited and include it in MST.

    • Push all the un-visited neighbors of this node(v) into Min-heap

Strongly Connected Components

Strongly connected components only exist for Directed Graphs.

• { A, B, C} is a SCC if all nodes are mutually reachable so (A→ B → C→ A) is a SCC as we can reach from any node to any other node.

• Before you think this is just cycle detection. Consider this graph { A→B , B→C , C→A , C→D , D→B }. You can easily detect a cycle of 3 nodes. But… This whole graph is an SCC meaning every node in this graph is mutually reachable via every other node. So cycle detection is just one small part of SCC.

Why do we need SCC ?

• SCCs are purely about mutual reachability, not shortest paths or distances. Think of it like finding clusters of mutually reachable people within a large set of people. So it can be used in grouping mutually reachable subsets in a large set.

• The idea is forming a Condensation Graph.

  • Take all the SCC components in a graph and reduce it to a single node.

  • The resulting graph is a DAG. And we all know how useful DAGs are, Used in Topo sorting and network analysis.

  • Even in Build tools like gradle uses SCC algorithms to first find the SCC in dependency of modules and then reduce it to a condensation graph for performing Topo Sort to decide a valid Build order.

Algorithm

• Consider this graph {1,2,3,4} , {5,6,7} forms a SCC. Connected by an Unidirected edge

• SCCa → SCCb

1. Perform DFS and record finish times. Put them in the stack. Here the first to finish would be 7. Stack(top) → [ 1, 2 , 3 ,4, 5 , 6 ,7]

2. Reverse the edges and and perform dfs again from decreasing order of finish time.

3. Each DFS traversal will give one SCC.

The whole idea of processing in decreasing order of finish time is because see this

SSCa → SCCb. If we reverse edges and start dfs from any node on SCCb then SCCa is still reachable. The idea was if we reverse edges the DFS traversal should give us SCC.

• So when we decompose a SCC graph into a node. We should always start processing from the SCC which finished last here. That would be SCCa so that after reversing the edges we cannot reach the other SCC.

• Why we didn’t take insertion time is because that can be different based on where you started your DFS. But the first node to finish will always be in SCCb irrespective of whichever node you start your DFS from.

Bridges in a Graph [ Critical Connection ] [ Single edge of failure ]

A bridge is an edge whose removal splits a connected graph into two disconnected parts.

Generally a concept of un-directed graph, but can be applied to directed graphs as well where connectivity in directed graphs would then refer to SCC

Algorithm

Tarjan Good Explanation - Jenny

The intuition is simple: when doing a DFS, you check if there’s any alternative path back from a subtree to an ancestor. If there isn’t, the edge leading into that subtree is a bridge.

• So suppose we think u – v is a bridge then we have to check if there is an alternate path to v which doesn’t go through u. For this we check low(v) > disc(u) ⇒ u – v is a bridge

• The whole point of low(v) is that can this node v be reached from any other node apart from parent u so if low(v) < disc(u) then yes then u–v is not a bridge, u is parent.

low[u] = x means that starting from u or anywhere in u’s DFS subtree, you can reach the node with discovery time x without using the tree edge that led you into u.

Tarjan

• We assign each node a discovery time disc [] , and low[] value

• Here insertion time is the time when the node was first discovered in DFS

• While doing DFS if you encountered a visited node (which is not parent) update your low for edge u–v low[u] = min(low[u],disc[v]).

• Now when the DFS of a node is completed and we backtrack then the parent node will check if u–v is a bridge and if low(v) > disc(u) ⇒ u – v is a bridge.

  • Also we will update low(u) = min ( low(u) , low(v) )

Articulation Point [ Single node of failure ]

💅 Imagine Riya being a common link to separate groups A and B. Group A talks to Group B only through riya. A marketing firm wants to advertise their product to masses. They have come up with a strategy targeting riya to advertise their product as riya here is the articulation point connecting the masses. Riya is the Articulation point and she is HOT

• Articulation point is any node in graph whose removal breaks the graph into multiple components

Algorithm

• Very much similar to Tarjan in bridges just that the entire node is removed.

• Here in u – v , u is an articulation point if from v you cannot reach to any edge above u, so simply in u –v , low(v) >= disc(u) ⇒ u is an articulation point

There is a catch u should not be root or u should have a parent so..

• For u – v ⇒ If ( parent != -1 && low[v] >= disc[u] ) ⇒ u is articulation point

But if u is root node and has multiple children than again u is articulation point so update condition

• In the end of DFS of u check if u is root and has > 1 children

  • If ( parent == -1 && children > 1) → u is articulation point

DSU

• DSU means Disjoint Set Union, also known as Union-Find.

• Basically it keeps track of non-overlapping sets (disjoint)

• Operation

  • Union(u,v) → Merge (or unite) two sets into one. O(1)

  • Find(x) → Find super parent of x, check if 2 elements belong to the same set.

• This is efficient as the Time complexity of both these operations is almost constant O(1)

• Path compression is used in find(x) gives, super parent of x, it’s like we make every node on the path point directly to the root.

• We are storing parent[] , size[] array , parent[x] gives super parent of x and size array is required during union operation to merge smaller size sets to larger sets

• Don’t access the parent[] , size[] array , access only from find(x) , union(u,v)

Application ?

• It’s a simple way to group elements and to check which group an element belongs to.

• Used for finding MST in Kruskal Algorithm

class DSU {
    vector<int> parent, rank, size;

  public:
    DSU(int n) {
        parent.resize(n);
        rank.resize(n, 0);
        size.resize(n, 1);
        for (int i = 0; i < n; i++)
            parent[i] = i; // 0 indexed
    }

    // find super parent of x or GODFather of x
    // O(4α) ~ O(1) operation
    int find(int x) {
        if (parent[x] == x) {
            return x;
        }
        // path compression (DP)
        return parent[x] = find(parent[x]);
    }

    // union of 2 nodes by Size
    // O(4α) ~ O(1) operation
    void unionBySize(int u, int v) {
        int superU = find(u);
        int superV = find(v);
        // if both super parents are equal (belong to same set)
        if (superU == superV) {
            return;
        }
        // if size of super parent of u > v then increase size of superParentU by size[superV]
        if (size[superU] > size[superV]) {
            parent[superV] = superU;
            size[superU] += size[superV];
        } else {
            parent[superU] = superV;
            size[superV] += size[superU];
        }
    }
};

// 6 nodes 0-5
DSU dsu(6);
dsu.unionByRank(1, 2);
dsu.unionByRank(3, 4);
dsu.unionByRank(2, 3);
dsu.unionByRank(0, 5);
// 0 and 3 belong to the same set ?
if (dsu.find(0) == dsu.find(3))
    cout << "SAME" << endl;
else
    cout << "NOT SAME" << endl;

• Most of the time DSU questions can be solved directly by using DFS. The whole point of DSU is to solve dynamic graph queries, where we leverage the already connected components..

• So mostly the questions revolve around finding components in a graph or to check if 2 nodes belong to the same set.

📝 Finding Components in a Graph with nodes defined ~ O(1)

• The idea is to keep a component counter in DSU. It is the max number of components possible in the graph. Usually it’s n where n is the number of nodes.

• On each successful Union of 2 nodes (if 2 nodes doesn’t belong to same set decrease component–

• If you only need size of a component of a node x → size[find(x)]

• If we are told to print distinct components or sizes of them ? →

  • Loop through all nodes again and group them by find(i)

unordered_map<int, vector<int>> comp;
for (int i = 1; i <= n; i++) {
    comp[find(i)].push_back(i);
}

📝 Finding Components in a Graph represented as Matrix ~ O(1)

• In a graph representation we can represent each cell as a node by :

  • getNode(i,j) → i*C + j Here C is total col.

• In order to find components you can use the same previous approach but n = 1’s in the matrix

Tries [ Prefix Tree ]

• Tries are essentially great if we are given a dictionary of words and have to do some prefix operations in each of them. Like for example if you are given dictionary of words and you have to find out how many words starts with pre

• Each node represents a character and path from root→node represents a prefix.

• Trie stores unique prefixes for each dictionary of words so

  • Total nodes of Trie == count of unique prefixes

• Each operation is O(len(word))

• The best way to represent trie is via edges so

“CANAL” is represented as (C–A–N–A–L) from root

• * means End of Word

• Trie contains {CANAL,CANDY,THE,THERE}

struct TrieNode {
    TrieNode *children[26];
    bool isEndOfWord; // marks end of a valid word
    int wordCount;    // how many words end at this node
    int prefixCount;  // how many words pass through this node

    TrieNode() {
        for (int i = 0; i < 26; i++)
            children[i] = nullptr;
        isEndOfWord = false;
        wordCount = 0;
        prefixCount = 0;
    }
};

class Trie {
  public:
    TrieNode *root;
    Trie() { root = new TrieNode(); }

    // Insert a word → O(len(word))
    void insert(const string &word) {
        TrieNode *node = root;
        for (char c : word) {
            int idx = c - 'a';
            if (!node->children[idx])
                node->children[idx] = new TrieNode();
            node = node->children[idx];
            node->prefixCount++; // increment for every node in the path
        }
        node->wordCount++; // mark end of word
    }

    // Search for a word O(len(word))
    bool search(const string &word) {
        TrieNode *node = root;
        for (char c : word) {
            int idx = c - 'a';
            if (!node->children[idx])
                return false;
            node = node->children[idx];
        }
        return node->isEndOfWord;
    }

    // Check if any word starts with a given prefix O(len(word))
    bool startsWith(const string &prefix) {
        TrieNode *node = root;
        for (char c : prefix) {
            int idx = c - 'a';
            if (!node->children[idx])
                return false;
            node = node->children[idx];
        }
        return true;
    }
    // Count words equal to the given word O(len(word))
    int countWordsEqualTo(const string &word) {
        TrieNode *node = root;
        for (char c : word) {
            int idx = c - 'a';
            if (!node->children[idx])
                return 0;
            node = node->children[idx];
        }
        return node->wordCount;
    }
    // Count words starting with a given prefix —> O(len(word))
    int countWordsStartingWith(const string &prefix) {
        TrieNode *node = root;
        for (char c : prefix) {
            int idx = c - 'a';
            if (!node->children[idx])
                return 0;
            node = node->children[idx];
        }
        return node->prefixCount;
    }
    // Erase a word (decrement counts along the path) → O(len(word))
    void erase(const string &word) {
        if (countWordsEqualTo(word) == 0)
            return; // word not present
        TrieNode *node = root;
        for (char c : word) {
            int idx = c - 'a';
            TrieNode *next = node->children[idx];
            next->prefixCount--;
            node = next;
        }
        node->wordCount--;
    }
};

For Dynamic Alphabets

When characters can include digits, uppercase, or even Unicode, or when memory is tight

struct TrieNode {
    unordered_map<char, TrieNode *> children;
    bool isEndOfWord = false;
};

Segment Trees

Basic Idea : Suppose you are given an array [ 4 , 5 , 6 , 8 , 2 ], and you have to find sum b/w index → {2,3} ⇒ (6+8 → 14) , you can do it in O(N) , now if i want you to optimize it you can probably think of using prefix array ⇒ [4, 9 , 15, 23, 25] and do pref(3) - pref(1) ⇒ 14

Great this is O(1) but what if i told you i want to update array values and perform the same operation again and again. For each update you will have to calculate prefix sum again so that would be worst case O(N) for updating the prefix array and O(1) for finding sum range.

Is there a better way to do this ?

• Turns out yes → Here comes the idea of Segment Trees / Fenwick Trees

• If you have lots of

  • Range queries (find max / min / sum) of given range

  • Update queries (updating the array)

Then Segment tree solves both problems in O(logN) time where N is the number of elements in the array.

How does it work ?

• First step is to build a segment tree.

• We take a tree array of size 4*N

• We divide the entire array into 2 halves and when size of each half is 1 we simply put tree[node] = arr[left]

• Each segment / node stores its operation result, here it’s sum so sum(0,2) = 15

• So if someone asks you to find sum(1,4) = sum(1,1) + sum(2,2) + sum(3,4) ⇒ 21

• So if I am sitting at root I will say to the left branch give me sum(1,2) and on my right give me sum(3,4) and I will simply add it and output.

We Will store this segment tree in a 4*N array where 0th node is empty so we will start from 1st node. The final Tree Array 4*5 = 20 size → [ 0, 25, 15, 10, 9, 6, 8, 2, 4, 5, 0, 0, 0, ……]

• Time complexity to build the tree is O(N)

• Remember if you are at ith index

  • Parent : floor ( i / 2) , Left child : 2*i , Right child : 2*i + 1

• Once you have constructed the tree than it’s easy for Range queries(a,b) you just have to divide the array into 2 equal halves recursively and check for range(a,m) and range(m+1,b). If the given node range is within [a,b] then return node value.

• Similarly for Update : We just have to find the index to update , this can be done again recursively to look check if index <= middle → check left subtree else right subtree

  • Once found update tree[node] = value, In the end re-build tree simultaneously

    • tree[node] = tree[2 * node] + tree[2 * node + 1]

Segment tree always starts with node = 1.

In C++ default parameters always comes at the end... remember

class SegmentTree {
    int nodes;
    vector<int> tree;

  public:
    SegmentTree(int n) {
        nodes = n;
        tree.resize(4 * n, 0);
    }

    void build(vector<int> &arr, int node = 1, int l = 0, int r = -1) {
        if (r == -1)
            r = nodes - 1;
        if (l == r) {
            tree[node] = arr[l];
            return;
        }
        int m = (l + r) / 2;
        build(arr, 2 * node, l, m);
        build(arr, 2 * node + 1, m + 1, r);
        // This is the operation = for Range Sum queries addition
        // For Range min/max query we can create segment tree with
        min / max of both children tree[node] = tree[2 * node] + tree[2 * node + 1];
    }

    void update(int idx, int val, int node = 1, int l = 0, int r = -1) {
        if (r == -1)
            r = nodes - 1;
        if (l == r) {
            tree[node] = val;
            return;
        }
        int m = (l + r) / 2;
        if (idx <= m)
            update(idx, val, 2 * node, l, m);
        else
            update(idx, val, 2 * node + 1, m + 1, r);
        tree[node] = tree[2 * node] + tree[2 * node + 1];
    }

    int query(int ql, int qr, int node = 1, int l = 0, int r = -1) {
        if (r == -1)
            r = nodes - 1;
        if (qr < l || ql > r)
            return 0;
        if (ql <= l && r <= qr)
            return tree[node];
        int m = (l + r) / 2;
        return query(ql, qr, 2 * node, l, m) + query(ql, qr, 2 * node + 1, m + 1, r);
    }
};

int main() {
    vector<int> arr = {4, 5, 6, 8, 2};
    SegmentTree st(arr.size());
    st.build(arr);

    cout << st.query(1, 3) << "\n"; // 5 + 6 + 8 = 19
    st.update(2, 10);
    cout << st.query(1, 3) << "\n"; // 5 + 10 + 8 = 23
}

But why 4*N size is taken ??

• If you look closely the size we require is the number of elements present in the tree

• For a complete binary tree with height h number of nodes ⇒ 2^(h+1)-1

• Here height is ceil (log2N) so number of nodes ⇒ 2^ (ceil(log2N + 1) -1

  • We can round off to 4N

Each Range and update operation is O(Log2(N)) as you are accessing exactly LogN elements in each operation

JAVA - Revise

static final int MOD = 1000000007;
static final int INF = Integer.MAX_VALUE;
static final long LINF = Long.MAX_VALUE;

static final int[] dx = {-1, 1, 0, 0}; // 4-directional
static final int[] dy = {0, 0, -1, 1};
static final int[] dx8 = {-1, -1, -1, 0, 0, 1, 1, 1}; // 8-directional
static final int[] dy8 = {-1, 0, 1, -1, 1, -1, 0, 1};

Scan Input / Output

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long x = sc.nextLong();
        String s = sc.next();
        System.out.println(n + " " + x + " " + s);
    }
}

• For Fast Input/Output scanning → Use BufferedReader + StringTokenizer

Leetcode Patterns - TBD

This section contains Leetcode Patterns and the general questions in that section. So if you have completed the above problems comfortably you can feel free to skip this.

Leetcode-101 Patterns

1. Sliding Window Template

2. Binary Search Problem

3. 2 Pointers

4. 10 Line Substring Template

5. String Pattern

6. BackTracking , BackTracking JAVA

7. Bit Manipulation

8. Monotonic Stack

—----------------------------------------

1. DP Pattern

   1. More DP

2. Graph for beginners

   1. BFS-DFS Part-1

   2. BFS-DFS Part-2

   3. More Graph

[Extras]

• Counting / radix

Patterns

• If input array is sorted then → Binary search , Two pointers

• If asked for all permutations/subsets then → Backtracking

• If given a tree / graph then → DFS , BFS

• If given a linked list then → Two pointers

• If recursion is banned then → Stack

• If must solve in-place then → Swap corresponding values

• Store one or more different values in the same → Two pointer

• If asked for maximum/minimum subarray/subset/options then → DP, Sliding window

• If asked for top/least K items → Heap , QuickSelect

• If asked for common strings then → Map , Trie

  • Else

Map/Set for O(1) time & O(n) space

Sort input for O(nlogn) time and O(1) space