How to use this guide

This is a deep, interview-ready DSA handbook. Each topic: quick definition, intuition, naive example, optimized approach, complexity, pitfalls, interview notes and problems.

  • Read intuition first — code second.
  • Learn templates — they map directly to interview patterns.
  • Practice the problems in Practice Problems section.

Complexity Guide (Big-O quick reference)

Common operation costs — memorize these.

  • Array access: O(1)
  • Array insert/delete (mid): O(n)
  • Linked list insert/delete at head: O(1)
  • HashMap lookup/insert (avg): O(1), worst O(n)
  • BST balanced operations: O(log n), skewed O(n)
  • Heap push/pop: O(log n)
  • DFS/BFS: O(V + E)
  • Sorting (comparison): O(n log n) average (merge/quick), O(n^2) naive

Arrays — concept & usage

Intuition: contiguous memory, fast indexing, used when size mostly known or random access is needed.

Naive — Find Maximum

int max(int[] arr) {
    if (arr == null || arr.length==0) return Integer.MIN_VALUE;
    int m = arr[0];
    for (int i=1; i m) m = arr[i];
    return m;
}

Optimize? — When to optimize

If scanning repeatedly, build prefix/suffix arrays, segment tree, or maintain running aggregates.

In-place rotate (common pattern)

void rotateRight(int[] a, int k) {
    k = k % a.length;
    reverse(a, 0, a.length-1);
    reverse(a, 0, k-1);
    reverse(a, k, a.length-1);
}
void reverse(int[] a, int l, int r) {
    while (l < r) { int t = a[l]; a[l++] = a[r]; a[r--] = t; }
}

Pitfalls

  • Off-by-one on indices
  • Null and empty checks
  • Beware integer overflow in loops? use l + (r-l)/2 in binary search

Linked Lists

Intuition: nodes with pointers — flexible size, cheap insert/delete at ends.

Naive — Reverse (iterative)

class Node { int v; Node next; Node(int x){v=x;} }
Node reverse(Node head) {
    Node prev=null, cur=head;
    while(cur!=null){
        Node tmp=cur.next; cur.next=prev; prev=cur; cur=tmp;
    }
    return prev;
}

Find middle (two-pointer)

Node middle(Node head) {
    Node slow=head, fast=head;
    while(fast!=null && fast.next!=null){ slow=slow.next; fast=fast.next.next; }
    return slow;
}

Use cases

  • Implement stacks/queues, adjacency lists

Stack (LIFO)

Use for recursion emulation, backtracking, expression parsing.

Naive — Balanced parentheses

boolean isBalanced(String s){
    java.util.Stack<Character> st = new java.util.Stack<>();
    for(char c : s.toCharArray()){
        if(c=='(') st.push(c);
        else if(c==')'){ if(st.isEmpty()) return false; st.pop(); }
    }
    return st.isEmpty();
}

Template: iterative DFS

void dfsIter(int src, List<Integer>[] adj) {
    boolean[] vis = new boolean[adj.length];
    java.util.Stack<Integer> st = new java.util.Stack<>();
    st.push(src);
    while(!st.isEmpty()){
        int u = st.pop();
        if(vis[u]) continue;
        vis[u]=true;
        // process u
        for(int v : adj[u]) if(!vis[v]) st.push(v);
    }
}

Queue (FIFO)

Great for BFS, producer-consumer. Use circular buffer or LinkedList.

BFS template

void bfs(int s, List<Integer>[] adj) {
    boolean[] vis = new boolean[adj.length];
    java.util.Queue<Integer> q = new java.util.LinkedList<>();
    q.add(s); vis[s]=true;
    while(!q.isEmpty()){
        int u=q.remove();
        // process u
        for(int v: adj[u]) if(!vis[v]) { vis[v]=true; q.add(v); }
    }
}

Hashing / HashMap

Average O(1) mapping. Good for frequency, dedup, caching.

Counting frequencies

Map<Integer,Integer> freq(int[] a){
    Map<Integer,Integer> m = new java.util.HashMap<>();
    for(int x: a) m.put(x, m.getOrDefault(x,0)+1);
    return m;
}

Collision & worst-case

Use good hash function; Java's built-in handles most primitives/strings well. For adversarial data, consider tree bins (Java 8+) or alternative maps.

Strings — patterns & common tasks

String problems often reduce to sliding-window, hashing (rolling hash), KMP, or two pointers.

Naive — substring search

int indexOf(String s, String p) {
    for(int i=0;i+ p.length()<=s.length(); i++){
        if(s.substring(i, i+p.length()).equals(p)) return i;
    }
    return -1;
}

KMP outline (use for guaranteed O(n))

Precompute lps table, then single pass.

Sorting — naive → efficient

Remember: comparison sorts cannot beat O(n log n) average using comparisons.

Bubble Sort (naive)

void bubbleSort(int[] a){
  int n=a.length;
  for(int i=0;ia[j+1]){ int t=a[j]; a[j]=a[j+1]; a[j+1]=t; }
    }
  }
}

Merge Sort (stable, O(n log n))

void mergeSort(int[] a, int l, int r){
  if(l>=r) return;
  int m=(l+r)/2;
  mergeSort(a, l, m);
  mergeSort(a, m+1, r);
  merge(a, l, m, r);
}
// merge uses temp array

QuickSort (average O(n log n), worst O(n^2))

Randomized pivot avoids worst-case on sorted inputs.

Searching

Binary search template (iterative)

int binarySearch(int[] a, int target){
  int l=0, r=a.length-1;
  while(l<=r){
    int m = l + (r-l)/2;
    if(a[m]==target) return m;
    if(a[m] < target) l = m+1; else r = m-1;
  }
  return -1;
}

Trees

Hierarchical structures. Use recursion for traversals.

DFS traversals — recursive templates

void inorder(Node root){
  if(root==null) return;
  inorder(root.left);
  visit(root);
  inorder(root.right);
}

Tree problems: lowest common ancestor (LCA)

Use parent+depth lifting (binary lifting) for repeated LCA queries; use recursion for single queries.

Binary Search Tree

Properties: left < node < right. Balanced BSTs (AVL, Red-Black) guarantee O(log n).

Search/insert (naive)

Node insert(Node root, int key){
  if(root==null) return new Node(key);
  if(key < root.val) root.left = insert(root.left, key);
  else root.right = insert(root.right, key);
  return root;
}

Heap / Priority Queue

Binary heap supports push/pop in O(log n). Java: PriorityQueue.

Use-case: kth smallest

int kthSmallest(int[] a, int k){
  PriorityQueue<Integer> pq = new PriorityQueue<>();
  for(int x: a) pq.add(x);
  for(int i=1;i

Graphs

Representations: adjacency list (preferred), adjacency matrix (dense). Problems: connectivity, shortest path, cycles, topological order.

BFS & shortest unweighted

int[] distances(List<Integer>[] adj, int s){
  int n=adj.length; int[] dist = new int[n]; Arrays.fill(dist, -1);
  Queue<Integer> q = new LinkedList<>(); q.add(s); dist[s]=0;
  while(!q.isEmpty()){
    int u=q.remove();
    for(int v: adj[u]) if(dist[v]==-1){ dist[v]=dist[u]+1; q.add(v); }
  }
  return dist;
}

Dijkstra (weighted, non-negative)

void dijkstra(int src, List<Pair>[] adj) {
  int n=adj.length; long[] dist = new long[n]; Arrays.fill(dist, Long.MAX_VALUE);
  PriorityQueue<Pair> pq = new PriorityQueue<>((a,b)->Long.compare(a.w,b.w));
  dist[src]=0; pq.add(new Pair(src,0));
  while(!pq.isEmpty()){
    Pair p=pq.poll(); int u=p.v;
    if(p.w>dist[u]) continue;
    for(Pair e: adj[u]){
      if(dist[e.v] > dist[u] + e.w){
        dist[e.v] = dist[u] + e.w;
        pq.add(new Pair(e.v, dist[e.v]));
      }
    }
  }
}

Topological Sort (DAG)

List<Integer> topo(int n, List<Integer>[] adj){
  int[] indeg = new int[n]; for(int u=0;u

Dynamic Programming

Two approaches: memoization (top-down) and tabulation (bottom-up). Identify overlapping subproblems and optimal substructure.

Fibonacci — naive vs memo vs tabulation

int fib(int n){ if(n<=1) return n; return fib(n-1) + fib(n-2); } // exponential

int fibMemo(int n, int[] memo){
  if(n<=1) return n;
  if(memo[n]!=-1) return memo[n];
  return memo[n] = fibMemo(n-1, memo) + fibMemo(n-2, memo);
}

Knapsack (0/1) — DP table outline

// dp[i][w] = max value using first i items with capacity w
for(i=1..n) for(w=0..W) dp[i][w] = max(dp[i-1][w], val[i] + dp[i-1][w-weight[i]]);

Backtracking

Explore choices, backtrack on failure. Use for permutations, combinations, N-Queens, Sudoku.

N-Queens outline (place row-by-row)

void solve(int r, int n, boolean[] col, boolean[] diag1, boolean[] diag2){
  if(r==n){ /* found */ return; }
  for(int c=0;c

Greedy

Take local optimal choice; proof often by exchange argument. Examples: activity selection, Huffman coding, fractional knapsack.

Two Pointers

Use two indices to scan from ends or to maintain window boundaries. Reduce O(n^2) → O(n).

Two-sum (sorted)

int[] twoSumSorted(int[] a, int t){
  int l=0, r=a.length-1;
  while(l

Sliding Window

Use variable window [l..r] to maintain invariant (sum, counts). Classic: longest substring w/o repeating chars, subarray sum equals K (positives).

Longest substring without repeating

int longestUnique(String s){
  int[] last = new int[256]; Arrays.fill(last, -1);
  int l=0, best=0;
  for(int r=0;r

Bit Manipulation

Useful for parity, subsets, masks. Know: &, |, ^, ~, <<, >>, bit tricks (x & -x gives lowest set bit).

Count bits (Brian Kernighan)

int popcount(int x){
  int cnt=0;
  while(x!=0){ x &= (x-1); cnt++; }
  return cnt;
}

Union-Find (Disjoint Set)

Maintain connected components with union by rank & path compression: near O(1) amortized.

int[] parent, rank;
int find(int x){ return parent[x]==x ? x : (parent[x]=find(parent[x])); }
void union(int a, int b){
  a=find(a); b=find(b);
  if(a==b) return;
  if(rank[a]

Tries (Prefix Trees)

Fast prefix search and word validation. Memory-heavy but fast lookups for strings.

class TrieNode { TrieNode[] next = new TrieNode[26]; boolean end=false; }
void insert(TrieNode root, String s){
  TrieNode cur=root;
  for(char c: s.toCharArray()){
    int i = c-'a'; if(cur.next[i]==null) cur.next[i]=new TrieNode();
    cur = cur.next[i];
  }
  cur.end=true;
}

Segment Tree & Fenwick (Binary Indexed Tree)

Range queries & updates: Fenwick for prefix sums (simple), Segment tree for range queries combining arbitrary assoc ops.

class Fenwick {
  int n; long[] bit;
  Fenwick(int n){ this.n=n; bit=new long[n+1]; }
  void add(int i, long val){ for(; i<=n; i += i&-i) bit[i]+=val; }
  long sum(int i){ long s=0; for(; i>0; i -= i&-i) s+=bit[i]; return s; }
}

Problem Patterns

  • Sliding window — continuous subarray/string problems
  • Two pointers — sorted pair problems, remove duplicates
  • Prefix sum — subarray sums, range queries
  • Hashing — counting, dedupe, two-sum (unsorted)
  • DFS/BFS — traverse graphs/trees
  • DP patterns — knapsack, LIS, partition
  • Greedy — scheduling, interval selection

Coding Templates (copy & adapt)

Binary Search (lower_bound style)

int lowerBound(int[] a, int target){
  int l=0, r=a.length;
  while(l

DFS recursive template (graphs)

void dfs(int u, List<Integer>[] adj, boolean[] vis){
  vis[u]=true;
  // process u
  for(int v: adj[u]) if(!vis[v]) dfs(v, adj, vis);
}

Practice Problems (Easy → Hard)

  1. Easy: Two Sum (array), Reverse Linked List, Merge Two Sorted Lists, Valid Parentheses
  2. Medium: Longest Substring Without Repeating Characters, Group Anagrams, Lowest Common Ancestor
  3. Hard: Word Ladder II, N-Queens II, Median of Two Sorted Arrays, Graph longest path (DAG)

Interview strategy

  • Explain thought process clearly; pick correct data structure and complexity target.
  • Start with naive solution, then optimize.
  • Write clean code, mention edge cases & complexity.