Data Structures & Algorithms

1. Why DSA Matters for Every Developer

Data Structures and Algorithms — popularly called DSA — are the core building blocks of computer science and software engineering. Whether you are preparing for campus placements, aiming at top product companies like Google, Microsoft, Flipkart, or Amazon, or simply trying to write better code in your day job, DSA knowledge is non-negotiable. Learn with LSGP's DSA curriculum is designed around one central idea: understanding the "why" behind every data structure and algorithm, not just memorising code snippets.

The Real Cost of Ignoring DSA

Imagine you write a function that checks whether a username already exists in a list of 10 million registered users. If you loop through the entire list each time, that is 10 million comparisons per lookup — your web server will crawl to a halt under real traffic. A hash set does the same lookup in effectively constant time regardless of list size. This is not theoretical; it is the difference between an app that scales and one that doesn't.

Companies like Google process billions of queries a day. Every millisecond of latency costs real money. Engineers at these companies are paid to think in terms of efficient algorithms, and that is exactly why every technical interview at a top company tests DSA heavily.

DSA in Everyday Software

Search engines use inverted indexes (hash maps + trees) to retrieve results in milliseconds.
Databases use B-Trees for indexing, allowing billions of records to be searched in a handful of disk reads.
GPS navigation uses Dijkstra's or A* shortest-path algorithms over enormous graph networks.
Social media feeds use priority queues and graph algorithms to rank and suggest content.
Compilers use stacks for expression parsing and trees for the abstract syntax representation of your code.
Operating systems use queues for process scheduling and trees for file system organisation.

In short: DSA is not an academic exercise. It is the vocabulary of software engineering. Learn with LSGP exists to make that vocabulary accessible to every CS/IT student in India.

💡 Learn with LSGP Tip Don't try to memorise every algorithm before coding a single one. Follow the sequence in this guide — understand the problem a data structure solves, implement it from scratch in Python or Java, then practice 5–10 problems on it before moving to the next topic.

2. Big O Notation & Complexity Analysis

Before studying any data structure or algorithm, you must understand how to measure the efficiency of code. Big O notation is the universal language programmers use to describe how an algorithm's performance scales with input size. At Learn with LSGP, we treat Big O as the first skill — not an optional add-on.

What Does "O" Mean?

The capital letter O stands for "Order of." When we say an algorithm is O(n), we mean that in the worst case, the number of operations it performs grows linearly with the size of the input n. We are not counting every single CPU instruction — we care about the dominant term that determines growth as n gets very large.

Common Complexity Classes

Notation	Name	Example	Feel at n=1,000,000
O(1)	Constant	Array index access	Instant
O(log n)	Logarithmic	Binary search	~20 steps
O(n)	Linear	Linear scan	1,000,000 steps
O(n log n)	Linearithmic	Merge sort	~20,000,000 steps
O(n²)	Quadratic	Bubble sort	1,000,000,000,000 steps
O(2ⁿ)	Exponential	Naive subset enumeration	Practically impossible

How to Calculate Big O

Follow these three rules when analysing your own code:

Drop constants. O(3n) simplifies to O(n). We don't care about constant multipliers.
Keep only the dominant term. O(n² + n) simplifies to O(n²) because n² grows much faster than n for large inputs.
Analyse loops independently. A single loop is O(n). A nested loop is O(n²). Two separate loops are O(n) + O(n) = O(2n) = O(n).

# O(n) — one loop over n elements def find_max(arr): max_val = arr[0] for x in arr: # runs n times if x > max_val: max_val = x return max_val # O(n²) — nested loop def has_duplicate(arr): for i in range(len(arr)): for j in range(i+1, len(arr)): # inner loop runs ~n times for each outer if arr[i] == arr[j]: return True return False

Space Complexity

Big O applies to memory too. A function that creates a copy of the input array uses O(n) extra space. A function that works in-place with a handful of variables uses O(1) extra space. Always report both time and space complexity when discussing your solution in an interview — Learn with LSGP's mock interviews always test this.

Best, Average, and Worst Case

When people say "Big O," they usually mean worst-case. But average case matters for real-world performance. Quick sort has a worst-case of O(n²) but an average case of O(n log n), making it fast in practice. Know all three cases for common algorithms.

3. Arrays & Strings

Arrays are the most fundamental data structure in programming. Every other structure — linked lists, heaps, hash tables — either wraps an array or contrasts with it. Mastering arrays thoroughly is the first concrete step in the Learn with LSGP DSA roadmap.

How Arrays Work in Memory

An array stores elements in contiguous memory locations. If an integer takes 4 bytes and your array starts at address 1000, element 0 is at 1000, element 1 at 1004, element 2 at 1008, and so on. This layout makes index access blazingly fast — O(1) — because the CPU can compute any element's address with a single multiplication: address = base + index × element_size.

The downside: inserting or deleting from the middle requires shifting elements, which costs O(n) time. This trade-off — fast access, slow insertion/deletion — defines when to use arrays versus other structures.

Key Array Operations & Complexities

Operation	Time Complexity	Notes
Access by index	O(1)	Direct memory calculation
Search (unsorted)	O(n)	Linear scan
Search (sorted)	O(log n)	Binary search
Insert at end	O(1) amortised	Dynamic array doubling
Insert at middle	O(n)	Shift elements right
Delete at middle	O(n)	Shift elements left

The Two-Pointer Technique

Two pointers is one of the most versatile array techniques and appears in dozens of interview problems. The idea: use two index variables that move through the array strategically instead of nesting loops.

# Two Sum II — sorted array, find pair summing to target def two_sum_sorted(nums, target): left, right = 0, len(nums) - 1 while left < right: s = nums[left] + nums[right] if s == target: return [left, right] elif s < target: left += 1 # need larger sum else: right -= 1 # need smaller sum

This runs in O(n) time and O(1) space — far better than the O(n²) brute force approach.

Sliding Window Technique

Sliding window is used for subarray problems — finding the maximum sum of a subarray of size k, the longest substring without repeating characters, and many more.

# Maximum sum subarray of size k def max_sum_subarray(arr, k): window_sum = sum(arr[:k]) max_sum = window_sum for i in range(k, len(arr)): window_sum += arr[i] - arr[i - k] # slide: add new, remove old max_sum = max(max_sum, window_sum) return max_sum

Important Array Problems to Practice

Two Sum (LeetCode #1) — hash map approach
Best Time to Buy and Sell Stock (#121) — single pass with min tracker
Container With Most Water (#11) — two pointers
Maximum Subarray (#53) — Kadane's Algorithm (O(n) DP)
Product of Array Except Self (#238) — prefix + suffix products
Rotate Array (#189) — in-place reversal trick
Merge Intervals (#56) — sort + greedy merge

4. Linked Lists

A linked list is a chain of nodes where each node holds a value and a pointer (reference) to the next node. Unlike arrays, nodes do not sit in contiguous memory — they can be scattered anywhere in the heap. This makes insertion and deletion at any position O(1) once you have a pointer to that position, but index access becomes O(n) because you must traverse from the head.

Types of Linked Lists

Singly Linked List: Each node has a next pointer only. Memory efficient. Cannot traverse backwards.
Doubly Linked List: Each node has both next and prev pointers. Allows O(1) deletion when you have a pointer to a node. Used in LRU Cache implementations.
Circular Linked List: The last node's next points back to the head. Used in round-robin scheduling.

# Singly Linked List implementation in Python class Node: def __init__(self, val): self.val = val self.next = None class LinkedList: def __init__(self): self.head = None def append(self, val): new_node = Node(val) if not self.head: self.head = new_node return cur = self.head while cur.next: cur = cur.next cur.next = new_node # O(n) — traverse to tail def delete(self, val): if self.head and self.head.val == val: self.head = self.head.next return cur = self.head while cur.next: if cur.next.val == val: cur.next = cur.next.next # bypass the node return cur = cur.next

Fast & Slow Pointer (Floyd's Cycle Detection)

The fast-slow pointer technique solves cycle detection, finding the middle of a list, and more. The slow pointer moves one step at a time; the fast pointer moves two. If there is a cycle, they will eventually meet.

def has_cycle(head): slow = fast = head while fast and fast.next: slow = slow.next fast = fast.next.next if slow == fast: return True return False

Reversing a Linked List

One of the most tested linked list operations in every technical interview. The iterative approach uses three pointers:

def reverse_list(head): prev, cur = None, head while cur: nxt = cur.next cur.next = prev prev = cur cur = nxt return prev # new head

Merging Two Sorted Linked Lists

This problem appears in nearly every company's question bank and tests your ability to handle pointers carefully without losing references. The trick is to use a dummy head node so you never have to special-case the first node.

def merge_two_lists(l1, l2): dummy = Node(0) cur = dummy while l1 and l2: if l1.val <= l2.val: cur.next = l1; l1 = l1.next else: cur.next = l2; l2 = l2.next cur = cur.next cur.next = l1 if l1 else l2 # attach remaining return dummy.next

Memory Management Implications

In languages like C and C++, linked list nodes are manually allocated on the heap with malloc and freed with free. Forgetting to free a deleted node causes a memory leak. In Java and Python, garbage collection handles this, but it's worth understanding the underlying mechanics — interviewers at systems-level companies sometimes ask about it. The discipline of tracking pointers carefully in linked list problems is also excellent training for pointer-heavy systems code.

Key Linked List Problems

Reverse a Linked List (#206)
Merge Two Sorted Lists (#21)
Linked List Cycle (#141)
Find the Middle of a Linked List (#876)
Remove Nth Node From End (#19)
Reorder List (#143) — split, reverse, merge
LRU Cache Implementation (#146) — uses doubly linked list + hash map

5. Stacks & Queues

Stacks and queues are restricted-access linear structures. They don't expose arbitrary index access — they enforce a discipline on how elements enter and leave, and that discipline is exactly what makes them powerful for specific classes of problems.

Stack — Last In, First Out (LIFO)

A stack is a pile: you can only add or remove from the top. Think of a stack of plates. In Python, a list with append() and pop() works perfectly as a stack. Both operations are O(1).

Stacks appear naturally whenever you need to track a "current context" that must be restored when you're done — function call stacks, undo history, expression parsers.

# Valid Parentheses — classic stack problem def is_valid(s): stack = [] pairs = {')': '(', '}': '{', ']': '['} for ch in s: if ch in '({[': stack.append(ch) elif not stack or stack[-1] != pairs[ch]: return False else: stack.pop() return not stack

Monotonic Stack

A monotonic stack maintains elements in either strictly increasing or strictly decreasing order. It is the go-to technique for "next greater element" and histogram-type problems.

# Next Greater Element for each position def next_greater(nums): result = [-1] * len(nums) stack = [] # stores indices for i, val in enumerate(nums): while stack and nums[stack[-1]] < val: result[stack.pop()] = val stack.append(i) return result

Queue — First In, First Out (FIFO)

A queue is a line: the first person to arrive is the first to be served. In Python, use collections.deque for O(1) append and popleft. Queues are central to BFS (Breadth-First Search) on graphs and trees.

Deque (Double-Ended Queue)

A deque allows O(1) insertion and deletion from both ends. It generalises both stacks and queues. The Sliding Window Maximum problem (finding the max in every window of size k) is solved elegantly with a monotonic deque in O(n) time.

Key Stack & Queue Problems

Valid Parentheses (#20) — stack
Min Stack (#155) — stack with O(1) min retrieval
Largest Rectangle in Histogram (#84) — monotonic stack
Sliding Window Maximum (#239) — monotonic deque
Implement Queue using Stacks (#232) — two-stack amortised O(1)
BFS Level Order Traversal (#102) — queue

6. Hashing & Hash Maps

If you could only learn one data structure beyond arrays, it would be the hash map (also called dictionary, map, or associative array). Hash maps enable O(1) average-time lookup, insertion, and deletion, and they unlock solutions to problems that would otherwise require O(n²) brute force.

How Hashing Works

A hash map uses a hash function to convert a key (a string, number, or object) into an index into an underlying array. For example, hash("username") % array_size might return 7, so "username"'s value is stored at index 7. Lookups work the same way — hash the key, jump to that index, done in O(1).

Collisions & Handling

Two different keys can hash to the same index — this is a collision. The two main strategies:

Chaining: Each bucket holds a linked list of all key-value pairs that hash there. Simple and widely used (Python's dict uses a variant of this).
Open addressing (linear probing): On collision, try the next bucket. More cache-friendly but requires careful load factor management.

When the hash map gets too full (load factor typically > 0.75), it resizes — creates a new, larger array and rehashes all entries. This is O(n) but happens rarely, giving amortised O(1) operations.

Using Hash Maps to Reduce Complexity

# Two Sum — O(n) with hash map vs O(n²) brute force def two_sum(nums, target): seen = {} for i, num in enumerate(nums): complement = target - num if complement in seen: return [seen[complement], i] seen[num] = i

Hash Sets for O(1) Membership

A hash set is a hash map where only keys matter (no values). Use it whenever you need fast "have I seen this before?" checks.

# Longest Consecutive Sequence — O(n) using set def longest_consecutive(nums): num_set = set(nums) best = 0 for n in num_set: if n - 1 not in num_set: # start of a sequence length = 1 while n + length in num_set: length += 1 best = max(best, length) return best

Key Hashing Problems

Group Anagrams (#49) — hash map with sorted key
Top K Frequent Elements (#347) — hash map + bucket sort or heap
Longest Consecutive Sequence (#128) — set
Subarray Sum Equals K (#560) — prefix sums with hash map
LRU Cache (#146) — hash map + doubly linked list

7. Trees & Binary Search Trees

A tree is a hierarchical, non-linear data structure where each node has a value and a list of child nodes. Unlike linear structures, trees naturally represent hierarchical data — file systems, HTML DOM, organisational charts, decision trees in ML, and more. Trees are also the foundation of the most important data structures in databases and operating systems.

Binary Tree Basics

A binary tree is a tree where each node has at most two children: left and right. Binary trees support three classic depth-first traversals:

Inorder (Left → Root → Right): For a BST, this gives elements in sorted order.
Preorder (Root → Left → Right): Used to copy/clone a tree.
Postorder (Left → Right → Root): Used to delete a tree, evaluate expression trees.

class TreeNode: def __init__(self, val=0): self.val = val self.left = self.right = None def inorder(root): if not root: return [] return inorder(root.left) + [root.val] + inorder(root.right) def max_depth(root): # O(n) — visit every node if not root: return 0 return 1 + max(max_depth(root.left), max_depth(root.right))

Binary Search Tree (BST)

A BST is a binary tree with one extra rule: for every node, all values in its left subtree are less than its value, and all values in its right subtree are greater. This rule makes search, insertion, and deletion all O(log n) on average — because at each step you eliminate half the remaining tree.

However, a BST can degenerate into a linked list if elements are inserted in sorted order (e.g., 1, 2, 3, 4, 5 gives a right-skewed tree of height n). Self-balancing BSTs like AVL trees and Red-Black Trees prevent this, maintaining O(log n) height always. These are the basis for Java's TreeMap and C++'s std::map.

Level-Order Traversal (BFS on Trees)

BFS uses a queue to visit nodes level by level — essential for problems asking about tree depth, width, or zigzag patterns.

from collections import deque def level_order(root): if not root: return [] result, q = [], deque([root]) while q: level = [] for _ in range(len(q)): node = q.popleft() level.append(node.val) if node.left: q.append(node.left) if node.right: q.append(node.right) result.append(level) return result

Key Tree Problems

Maximum Depth of Binary Tree (#104)
Invert Binary Tree (#226)
Symmetric Tree (#101)
Path Sum (#112, #113)
Lowest Common Ancestor of a BST (#235) and General Tree (#236)
Validate Binary Search Tree (#98)
Construct Binary Tree from Preorder and Inorder (#105)
Serialize and Deserialize Binary Tree (#297)

8. Heaps & Priority Queues

A heap is a specialised tree-based structure that satisfies the heap property: in a min-heap, every parent is smaller than or equal to its children. The root always holds the minimum element, and extraction takes O(log n). This makes heaps perfect for "always get me the smallest/largest item" scenarios.

Min-Heap vs Max-Heap

Min-Heap: Root = minimum element. Python's heapq is a min-heap by default.
Max-Heap: Root = maximum. Simulate in Python by inserting negative values.

import heapq # Top K Frequent Elements using a heap def top_k_frequent(nums, k): freq = {} for n in nums: freq[n] = freq.get(n, 0) + 1 # Use a min-heap of size k — push and pop to keep top k heap = [] for num, count in freq.items(): heapq.heappush(heap, (count, num)) if len(heap) > k: heapq.heappop(heap) return [item[1] for item in heap]

When to Use a Heap

Finding the K-th largest or smallest element
Merging K sorted lists
Dijkstra's shortest path algorithm
Real-time median tracking (two heaps: one max-heap for lower half, one min-heap for upper half)
Task scheduling by priority

🧠 Learn with LSGP Insight Whenever an interview problem says "find the top K" or "always pick the minimum/maximum," immediately think heap. Heaps give you O(log k) per operation instead of O(n) for finding the extreme each time.

9. Graphs & Graph Traversal

Graphs are the most powerful and versatile data structure in CS. A graph consists of vertices (nodes) and edges (connections between nodes). Almost any real-world network is a graph: roads, social connections, internet links, dependency chains in build systems.

Graph Representations

Adjacency List: Each vertex stores a list of its neighbours. Space: O(V + E). Best for sparse graphs (few edges relative to vertices). Most common in interview problems.
Adjacency Matrix: A V×V grid where matrix[i][j] = 1 if there's an edge. Space: O(V²). Fast for edge lookups but wasteful for sparse graphs.
Edge List: A list of (u, v) pairs. Used in algorithms like Kruskal's MST.

Depth-First Search (DFS)

DFS explores as deep as possible along each branch before backtracking. Implemented recursively or with an explicit stack. Used for: cycle detection, topological sort, connected components, path finding.

def dfs(graph, node, visited): if node in visited: return visited.add(node) print(node) for neighbour in graph[node]: dfs(graph, neighbour, visited)

Breadth-First Search (BFS)

BFS explores all neighbours of a node before going deeper. Uses a queue. Key property: BFS finds the shortest path in an unweighted graph. Used for: shortest path, level-order problems, multi-source spreading (like rotten oranges).

from collections import deque def bfs(graph, start): visited = {start} q = deque([start]) while q: node = q.popleft() print(node) for neighbour in graph[node]: if neighbour not in visited: visited.add(neighbour) q.append(neighbour)

Topological Sort

Topological sort orders vertices of a Directed Acyclic Graph (DAG) so every edge goes from earlier to later in the ordering. Used for task scheduling, build systems, and course prerequisites. Implemented via DFS (reverse post-order) or Kahn's algorithm (BFS-based with in-degree counting).

Union-Find (Disjoint Set Union)

Union-Find tracks connected components efficiently. Uses two optimisations — path compression and union by rank — to achieve near-O(1) per operation. Essential for Kruskal's MST and detecting cycles in undirected graphs.

Dijkstra's Shortest Path

For weighted graphs, Dijkstra's algorithm finds the shortest path from a source to all other nodes. It uses a min-heap to always process the nearest unvisited node first. Time complexity: O((V + E) log V) with a heap.

Key Graph Problems

Number of Islands (#200) — DFS/BFS on 2D grid
Clone Graph (#133)
Course Schedule (#207, #210) — topological sort / cycle detection
Pacific Atlantic Water Flow (#417)
Rotting Oranges (#994) — multi-source BFS
Number of Connected Components (#323) — Union-Find or DFS
Network Delay Time (#743) — Dijkstra's
Word Ladder (#127) — BFS on implicit graph

10. Sorting Algorithms

Sorting is one of the most studied problems in computer science. Knowing when and why to use each algorithm — not just how to code it — separates junior developers from strong engineers. Most languages sort in O(n log n) using hybrid algorithms (Python uses Timsort, a merge sort + insertion sort hybrid), but understanding the internals matters for interviews and edge cases.

Sorting Algorithm Comparison

Algorithm	Best	Average	Worst	Space	Stable?
Bubble Sort	O(n)	O(n²)	O(n²)	O(1)	Yes
Selection Sort	O(n²)	O(n²)	O(n²)	O(1)	No
Insertion Sort	O(n)	O(n²)	O(n²)	O(1)	Yes
Merge Sort	O(n log n)	O(n log n)	O(n log n)	O(n)	Yes
Quick Sort	O(n log n)	O(n log n)	O(n²)	O(log n)	No
Heap Sort	O(n log n)	O(n log n)	O(n log n)	O(1)	No
Counting Sort	O(n+k)	O(n+k)	O(n+k)	O(k)	Yes

Merge Sort — Divide & Conquer

Merge sort divides the array in half, recursively sorts both halves, then merges them in sorted order. It is guaranteed O(n log n) and stable, making it ideal for sorting linked lists and when stability matters.

def merge_sort(arr): if len(arr) <= 1: return arr mid = len(arr) // 2 left = merge_sort(arr[:mid]) right = merge_sort(arr[mid:]) return merge(left, right) def merge(left, right): result = [] i = j = 0 while i < len(left) and j < len(right): if left[i] <= right[j]: result.append(left[i]); i += 1 else: result.append(right[j]); j += 1 return result + left[i:] + right[j:]

Quick Sort — Average-Case King

Quick sort picks a pivot, partitions elements smaller than pivot to the left and larger to the right, then recursively sorts each partition. With a good pivot selection (random or median-of-three), it is extremely fast in practice despite the O(n²) worst case.

Non-Comparison Sorts

Comparison-based sorts are bounded by O(n log n) — it's mathematically provable. But if you know something about your data, you can do better:

Counting Sort: For integers in range [0, k]. Count occurrences, then reconstruct. O(n + k).
Radix Sort: Sort digit by digit from least significant to most. O(d × (n + b)) where d is digits and b is base.
Bucket Sort: Distribute elements into buckets, sort each bucket, concatenate. Works well for uniformly distributed floats.

11. Searching Algorithms

Searching is the act of finding a target value within a data structure. The choice of searching algorithm depends almost entirely on whether the data is sorted.

Linear Search — O(n)

Scan every element. Works on unsorted data. No preprocessing required. Use it when the data is small, unsorted, or when you only search once.

Binary Search — O(log n)

Binary search requires sorted data. It repeatedly halves the search space: check the middle element, discard the half that cannot contain the target, repeat. For n = 1,000,000, it finds the answer in at most 20 comparisons.

def binary_search(arr, target): left, right = 0, len(arr) - 1 while left <= right: mid = (left + right) // 2 if arr[mid] == target: return mid elif arr[mid] < target: left = mid + 1 else: right = mid - 1 return -1 # not found

Binary Search on the Answer

One of the most powerful interview patterns: if a problem asks "find the minimum value of X such that condition C holds," and C is monotonic (once it becomes true it stays true), you can binary search on the answer space rather than a sorted array.

# Minimum days to make M bouquets (LeetCode #1482) def min_days(bloomDay, m, k): def can_make(days): bouquets = flowers = 0 for d in bloomDay: if d <= days: flowers += 1 if flowers == k: bouquets += 1; flowers = 0 else: flowers = 0 return bouquets >= m lo, hi = min(bloomDay), max(bloomDay) while lo < hi: mid = (lo + hi) // 2 if can_make(mid): hi = mid else: lo = mid + 1 return lo

Key Binary Search Problems

Binary Search (#704) — baseline
Search in Rotated Sorted Array (#33)
Find Minimum in Rotated Sorted Array (#153)
Koko Eating Bananas (#875) — binary search on answer
Median of Two Sorted Arrays (#4) — hard, partition-based

12. Recursion & Backtracking

Recursion is a function calling itself to solve a smaller version of the same problem. It is the natural language of divide-and-conquer, tree traversal, and combinatorial enumeration. Every recursive solution has two parts: a base case (smallest sub-problem with a direct answer) and a recursive case (reduce the problem and call yourself).

Thinking Recursively

The key mental model: "Trust the recursion." When writing a recursive function, assume the recursive call correctly solves the smaller sub-problem. Your job is only to define the base case and how to combine results.

# Fibonacci — naive O(2^n) vs memoised O(n) def fib(n, memo={}): if n <= 1: return n if n in memo: return memo[n] memo[n] = fib(n-1, memo) + fib(n-2, memo) return memo[n]

Backtracking

Backtracking is systematic exploration of all possible configurations, abandoning (pruning) a path as soon as it violates constraints. It is the algorithm behind Sudoku solvers, N-Queens, permutation generators, and subset enumeration.

The pattern is always: choose → explore → unchoose.

# All permutations of a list def permutations(nums): result = [] def backtrack(path, remaining): if not remaining: result.append(path[:]) return for i, num in enumerate(remaining): path.append(num) # choose backtrack(path, remaining[:i] + remaining[i+1:]) # explore path.pop() # unchoose backtrack([], nums) return result

Key Recursion & Backtracking Problems

Subsets (#78, #90)
Permutations (#46, #47)
Combination Sum (#39, #40)
N-Queens (#51) — classic backtracking with pruning
Word Search (#79) — backtracking on 2D grid
Generate Parentheses (#22)
Palindrome Partitioning (#131)

13. Dynamic Programming

Dynamic programming (DP) is the hardest and most rewarding topic in the DSA curriculum. It applies to problems with two properties: optimal substructure (the optimal solution contains optimal solutions to sub-problems) and overlapping sub-problems (the same sub-problems are solved multiple times). DP avoids redundant computation by storing results — either top-down with memoisation or bottom-up with tabulation.

The DP Thinking Framework

Define the state. What does dp[i] or dp[i][j] represent?
Write the recurrence. How does the current state relate to previous states?
Identify base cases. What are the simplest sub-problems with known answers?
Determine the order. Which direction do you fill the table?
Extract the answer. Which state(s) give the final result?

Classic DP: 0/1 Knapsack

You have n items each with a weight and value, and a bag of capacity W. Maximise the value you can fit without exceeding W.

def knapsack(weights, values, W): n = len(weights) dp = [[0] * (W+1) for _ in range(n+1)] for i in range(1, n+1): for w in range(W+1): dp[i][w] = dp[i-1][w] # skip item i if weights[i-1] <= w: dp[i][w] = max(dp[i][w], values[i-1] + dp[i-1][w - weights[i-1]]) return dp[n][W]

Longest Common Subsequence (LCS)

LCS is foundational to string DP problems. Given two strings, find the length of their longest common subsequence (characters need not be contiguous).

def lcs(s1, s2): m, n = len(s1), len(s2) dp = [[0] * (n+1) for _ in range(m+1)] for i in range(1, m+1): for j in range(1, n+1): if s1[i-1] == s2[j-1]: dp[i][j] = 1 + dp[i-1][j-1] else: dp[i][j] = max(dp[i-1][j], dp[i][j-1]) return dp[m][n]

DP Problem Patterns at Learn with LSGP

Pattern	Key Problems
1D DP (linear)	Climbing Stairs, House Robber, Decode Ways
2D DP (grid)	Unique Paths, Minimum Path Sum, Edit Distance
Interval DP	Burst Balloons, Matrix Chain Multiplication
Subsequence DP	LCS, LIS, Edit Distance
Knapsack variants	Partition Equal Subset Sum, Coin Change, Target Sum
State machine DP	Best Time to Buy Stock with Cooldown

⚠️ Learn with LSGP Warning Do NOT jump to memorising DP solutions. The skill in DP is defining the state and recurrence. Practice writing those two things first on paper, then coding. After 20–30 DP problems with this approach, patterns become automatic.

14. Greedy Algorithms

A greedy algorithm makes the locally optimal choice at each step, hoping this leads to a globally optimal solution. Greedy algorithms are faster than DP — usually O(n log n) due to sorting — but only work when the greedy choice property holds: a local best leads to a global best.

When is Greedy Safe?

Greedy works when the problem has optimal substructure AND the greedy choice never needs to be revised. Common greedy domains: interval scheduling, Huffman coding, minimum spanning trees (Kruskal's, Prim's), Dijkstra's algorithm, and fractional knapsack.

Activity Selection Problem

Given n activities with start and end times, select the maximum number of non-overlapping activities. Greedy: sort by end time, always pick the earliest-ending compatible activity.

def max_activities(activities): activities.sort(key=lambda x: x[1]) # sort by end time count = 1 last_end = activities[0][1] for start, end in activities[1:]: if start >= last_end: count += 1 last_end = end return count

Key Greedy Problems

Jump Game (#55) — greedy reach extension
Jump Game II (#45) — minimum jumps
Gas Station (#134) — circular greedy
Meeting Rooms II (#253) — interval heap
Task Scheduler (#621) — frequency-based greedy
Minimum Number of Arrows to Burst Balloons (#452)

Bonus: Tries (Prefix Trees)

A Trie (pronounced "try," from retrieval) is a tree-like structure specialised for storing strings. Each node represents a character, and paths from root to leaves form words. Tries are the foundation of autocomplete systems, spell checkers, and IP routing tables.

Why Not Just Use a Hash Map?

A hash map tells you whether an exact word exists in O(1). A Trie tells you whether a prefix exists in O(m) where m is the prefix length, and it can enumerate all words with a given prefix efficiently. This prefix search capability is what makes Tries indispensable for search-as-you-type features.

class TrieNode: def __init__(self): self.children = {} self.is_end = False class Trie: def __init__(self): self.root = TrieNode() def insert(self, word): node = self.root for ch in word: if ch not in node.children: node.children[ch] = TrieNode() node = node.children[ch] node.is_end = True def search(self, word): node = self.root for ch in word: if ch not in node.children: return False node = node.children[ch] return node.is_end def starts_with(self, prefix): node = self.root for ch in prefix: if ch not in node.children: return False node = node.children[ch] return True

Complexity of Trie Operations

Operation	Time	Space
Insert word of length m	O(m)	O(m × alphabet_size)
Search exact word	O(m)	O(1) extra
Prefix search	O(p)	O(1) extra
Delete word	O(m)	O(1) extra

Real-World Trie Applications

Search autocomplete: Google's search bar suggests completions as you type — powered by a Trie over indexed queries.
Spell checkers: Tries with Levenshtein distance computation power correction suggestions.
IP routing: Routers use binary Tries to find the longest prefix match for packet forwarding.
Word games: Boggle solvers use Tries to prune the search space — if a prefix is not in the Trie, no word starts with it, so backtrack immediately.

Key Trie Problems

Implement Trie (#208)
Design Add and Search Words Data Structure (#211) — wildcard '.' matching with DFS
Word Search II (#212) — Trie + backtracking on 2D board

Bonus: Segment Trees & Advanced Topics

Once you have mastered the fundamentals covered in this guide, the next frontier includes segment trees, Fenwick trees (Binary Indexed Trees), advanced graph algorithms, and string algorithms. Learn with LSGP covers these in our advanced DSA track, but here is a primer to orient you.

Segment Tree

A segment tree is a binary tree built over an array. Each leaf stores one element; each internal node stores a summary (sum, min, max) of a range of elements. Segment trees answer range queries and support point updates both in O(log n), far better than the O(n) brute-force approach.

Use case: "given an array of numbers, answer 1000 queries of the form: what is the sum of elements from index L to R?" Brute force is O(n × 1000). Segment tree builds in O(n) and answers each query in O(log n).

# Range sum query using a flat array segment tree class SegTree: def __init__(self, arr): self.n = len(arr) self.tree = [0] * (4 * self.n) self.build(arr, 0, 0, self.n - 1) def build(self, arr, node, start, end): if start == end: self.tree[node] = arr[start] else: mid = (start + end) // 2 self.build(arr, 2*node+1, start, mid) self.build(arr, 2*node+2, mid+1, end) self.tree[node] = self.tree[2*node+1] + self.tree[2*node+2] def query(self, node, start, end, l, r): if r < start or end < l: # completely outside return 0 if l <= start and end <= r: # completely inside return self.tree[node] mid = (start + end) // 2 return (self.query(2*node+1, start, mid, l, r) + self.query(2*node+2, mid+1, end, l, r))

Fenwick Tree (Binary Indexed Tree)

A Fenwick tree is a more compact alternative to a segment tree for prefix sum and range sum queries. It uses clever bit manipulation to achieve O(log n) updates and queries with far less code and a constant-size array. Competitive programmers love it for its simplicity despite its cryptic indexing.

Advanced Graph Algorithms

Bellman-Ford: Shortest path in graphs with negative-weight edges. Detects negative cycles. O(V × E).
Floyd-Warshall: All-pairs shortest paths in O(V³). Suitable for dense graphs with at most a few hundred vertices.
Prim's & Kruskal's: Minimum Spanning Tree algorithms. Kruskal's uses Union-Find; Prim's uses a min-heap. Both achieve O(E log V).
Tarjan's SCC: Finds Strongly Connected Components of a directed graph in O(V + E). Used in compilers and dependency analysis.
Articulation Points & Bridges: Finds critical nodes and edges whose removal disconnects a graph. Critical for network reliability analysis.

String Algorithms

KMP (Knuth-Morris-Pratt): Finds all occurrences of a pattern in a text in O(n + m) vs O(n × m) for brute force. Uses a prefix function to avoid re-examining characters.
Rabin-Karp: Rolling hash for substring search. Average O(n + m) with simple code.
Z-Algorithm: Computes for each position in a string the length of the longest substring starting there that is also a prefix of the entire string. O(n).
Manacher's Algorithm: Finds the longest palindromic substring in O(n), used in problems like palindrome partitioning variants.

🗺️ Learn with LSGP Advanced Track Segment trees, Fenwick trees, and advanced graph algorithms are covered in depth in Learn with LSGP's Advanced DSA module, which includes implementation templates, complexity proofs, and 50+ practice problems calibrated to GATE CS and top-tier product company interviews.

Connecting DSA to Real Projects

Theory without application feels abstract. Learn with LSGP strongly believes that every major DSA topic should be connected to a concrete mini-project or system design scenario. Here are five projects that directly exercise the data structures and algorithms covered in this guide — build these alongside your LeetCode practice and you will gain a depth of understanding that purely algorithmic practice cannot provide.

Project 1: In-Memory Key-Value Store (Hash Maps)

Build a simplified version of Redis. Implement a dictionary with set, get, delete operations. Add a TTL (time-to-live) feature using a min-heap to expire keys efficiently. This exercises hash maps, heaps, and teaches you how real databases manage in-memory data. Extend it with an LRU eviction policy using a doubly linked list + hash map — exactly LeetCode #146.

Project 2: File System Simulator (Trees)

Model a file system as an n-ary tree where each node is a directory or file. Implement commands: mkdir, ls, cd, find. The find command exercises DFS; ls -R exercises BFS or DFS with depth tracking. Add a du command (disk usage) that recursively sums file sizes — a postorder tree traversal. This is the system design of every OS you've ever used.

Project 3: Mini Search Engine (Tries + Inverted Index)

Index a collection of text documents. Use an inverted index (hash map from word → list of document IDs) for keyword search. Add a Trie for autocomplete as the user types. Rank results by frequency (max-heap). This combines hashing, Tries, and heaps into a cohesive system and gives you a concrete intuition for how Google's core indexing works at a simplified level.

Project 4: Route Planner (Graphs + Dijkstra)

Model a city map as a weighted undirected graph where nodes are intersections and edges are roads with weights representing distance or time. Implement Dijkstra's algorithm to find the shortest path between two points. Display the path. Add a feature to find the shortest path avoiding a specific road (edge removal). This is GPS navigation in miniature and solidifies your graph traversal and heap usage simultaneously.

Project 5: Expression Evaluator (Stacks)

Build a calculator that evaluates mathematical expressions given as strings: "3 + 4 * 2 / (1 - 5)". This requires a two-step process: convert the infix expression to postfix (Reverse Polish Notation) using the Shunting Yard algorithm (a stack-based algorithm), then evaluate the postfix expression using a value stack. This is exactly what compilers do when parsing your code — and it's a beautiful, self-contained application of stacks.

How to Approach Each Project

Read the project spec and identify which data structures are needed.
Write the interface first (function signatures, class names) before implementation.
Implement core operations with correct complexity.
Write test cases: normal input, edge cases, large input.
Profile if possible: measure actual time on large inputs and see if it matches your Big O prediction.

These projects are available as guided assignments in the Learn with LSGP coding module, with starter code, test suites, and step-by-step walkthroughs for students who get stuck.

Mental Models for Choosing the Right Data Structure

One of the most practical skills you will develop through DSA practice is the ability to look at a problem and immediately know which data structure or algorithmic pattern to reach for. This pattern recognition does not come from reading — it comes from solving hundreds of problems. But you can accelerate it by internalising the following decision frameworks that Learn with LSGP teaches in its live classes.

The "What Do You Need?" Framework

If you need to…	Use…
Access elements by index instantly	Array
Insert/delete anywhere in O(1) (with pointer)	Doubly Linked List
Track "last seen" or undo history	Stack
Process elements in arrival order	Queue
Always get the minimum or maximum	Heap (Priority Queue)
Fast key-based lookup / counting	Hash Map / Hash Set
Prefix search / autocomplete	Trie
Hierarchical data / recursive structure	Tree
Sorted data + range queries	Balanced BST / Segment Tree
Relationships between entities	Graph
Group elements into connected sets	Union-Find
Range sum / min / max with updates	Segment Tree / Fenwick Tree

Algorithm Pattern Recognition

Problem Signal	Pattern
"Find pair/triplet with sum X"	Two Pointers or Hash Map
"Longest/shortest subarray satisfying condition"	Sliding Window
"Top K / K-th largest"	Heap of size K
"All combinations/subsets/permutations"	Backtracking
"Minimum/maximum over all ways to do X"	Dynamic Programming
"Shortest path between nodes"	BFS (unweighted) or Dijkstra (weighted)
"Task ordering with dependencies"	Topological Sort
"Valid parentheses / balanced brackets"	Stack
"Find something in sorted data"	Binary Search
"Overlapping sub-problems in recursion"	Memoisation → Dynamic Programming
"Next greater/smaller element"	Monotonic Stack
"Interval merging / scheduling"	Sort by start/end + Greedy

The "Complexity Budget" Mental Model

In an interview, you usually have an implicit complexity budget based on the input size n that the problem states. Learn with LSGP teaches students to read input constraints to immediately know what complexity is acceptable:

n ≤ 20 → O(2ⁿ) or O(n!) is fine — backtracking, full enumeration
n ≤ 300 → O(n³) is fine — Floyd-Warshall, 3D DP
n ≤ 5,000 → O(n²) is fine — O(n²) DP, brute force with two loops
n ≤ 100,000 → O(n log n) required — sorting, heaps, binary search
n ≤ 1,000,000 → O(n) required — sliding window, hashing, linear DP
n ≤ 10⁹ → O(log n) or O(1) — mathematical formula or binary search on answer

Practise reading constraints before reading the problem body. It narrows your search space dramatically and often tells you which algorithm family to use before you've even understood the full problem.

15. Interview Strategy & Learn with LSGP Study Plan

Knowing DSA concepts is half the battle. Translating that knowledge into interview success requires deliberate practice, communication skills, and a structured plan. Learn with LSGP has designed the following study system specifically for Indian CS/IT students targeting product companies and service firms alike.

Understanding What Interviewers Actually Evaluate

A technical interview is not a test of whether you have memorised solutions. Experienced interviewers at companies like Google, Microsoft, Amazon, Atlassian, Flipkart, and Swiggy are simultaneously evaluating four things: your problem-solving process, your coding fluency, your communication clarity, and your ability to reason about trade-offs. A candidate who arrives at a suboptimal solution but clearly articulates why it is suboptimal and how they would improve it often outscores someone who silently codes a perfect solution.

Understand this distinction deeply: the goal is not to appear smart. The goal is to demonstrate how you think under pressure and whether you would be a good engineering collaborator. In on-campus drives and off-campus interviews alike, Learn with LSGP's mock interview sessions specifically train this communication dimension — not just the algorithmic one. Preparation without mock interviews is like studying cricket by reading about it but never picking up a bat.

Indian placement cycles have a specific rhythm: online assessments (OAs) first, then technical phone screens, then onsite or virtual panel interviews. OAs test speed and correctness under time pressure, so you need to be fluent enough to code standard patterns without thinking. Panel interviews go deeper — expect follow-up questions like "can you do this in O(1) space?" or "how would this solution change if the input were streamed rather than all available at once?" Learn with LSGP's placement prep track covers both phases explicitly.

The Four-Step Interview Framework

Understand the problem. Restate it in your own words. Ask about edge cases: empty input? Negative numbers? Duplicates? Integer overflow? Show the interviewer you think before you code.
Discuss approaches. Start with brute force — state its complexity. Then propose an optimised approach. Explain the insight that makes it faster (the data structure you're using and why).
Code cleanly. Write readable variable names. Add brief comments for non-obvious steps. Do not silently code — narrate your logic as you write.
Test and trace. Walk through your code with the given example. Then test edge cases manually. Trace through the tricky part of the algorithm step by step.

12-Week Learn with LSGP DSA Study Plan

Week	Topic	Goal
1	Arrays, Strings, Two Pointers	20 easy/medium problems
2	Hash Maps, Sliding Window	15 problems, all two-sum variants
3	Linked Lists, Fast-Slow Pointer	10 problems, implement LL from scratch
4	Stacks, Queues, Monotonic Stack	10 problems, implement stack-based calculator
5	Binary Trees, BFS, DFS	15 problems, traverse all 4 ways by heart
6	BST, Heaps, Priority Queue	10 problems, implement min-heap from scratch
7	Binary Search (arrays + answer space)	15 problems
8	Sorting + Recursion + Backtracking	12 problems, implement merge sort and quick sort
9	Graphs — BFS, DFS, Union-Find	15 problems, solve Number of Islands 5 different ways
10	Dynamic Programming — 1D and 2D	12 problems, write state and recurrence first
11	Advanced DP, Greedy, Tries	10 problems
12	Mock Interviews + Company-Specific Review	Full 45-min timed mocks daily

Problem Volume Targets

Quality beats quantity, but you need enough volume to build pattern recognition. Learn with LSGP recommends:

Minimum viable preparation: 75 problems across all major topics (the Blind 75 list)
Strong preparation: 150–200 problems with at least 30% medium difficulty
Top-company target: 250+ problems including 40–50 hard problems on your weakest topics

For each problem: if you cannot solve it in 25 minutes, look at the hint or solution. Study it, close it, then re-implement it from scratch the next day. This spaced repetition is how you internalise patterns rather than memorising.

Common Interview Mistakes to Avoid

Silent coding: Interviewers want to hear your thought process. Talk through every decision.
Jumping to code: Spend 5–8 minutes understanding and designing before writing a single line.
Ignoring edge cases: Always ask about empty input, single element, and overflow.
Off-by-one errors: Binary search and sliding window are notorious for these. Trace through small examples carefully.
Not stating complexity: Always volunteer time and space complexity without being asked — it shows maturity.
Giving up publicly: If stuck, show your thinking: "I know I need O(n log n), and this looks like a heap or merge-sort problem…" Partial progress is valued.

Resources Recommended by Learn with LSGP

LeetCode — primary practice platform; filter by topic, then by company
NeetCode.io — curated problem lists with video walkthroughs
CP-Algorithms — deep algorithmic theory with proofs
CLRS (Introduction to Algorithms) — the definitive textbook for rigorous understanding
Learn with LSGP Practice Module — our own MCQ bank, mock tests, and coding problem bank designed around the Indian placement cycle

🎯 Learn with LSGP Final Advice DSA mastery is not an event — it is a habit. Code for at least 45 minutes every day. Review one problem you've already solved to reinforce patterns. Stay patient: most students see a dramatic improvement in weeks 8–10 of consistent practice, not in week one. Keep going.

Company Type	Heavy Topics	Typical Difficulty
Product (Google, Microsoft, Atlassian)	Graphs, DP, Trees, System Design	Medium–Hard
Fintech (Zerodha, Razorpay, CRED)	Arrays, Hashing, Sliding Window, SQL	Easy–Medium
E-Commerce (Flipkart, Amazon, Meesho)	Arrays, DP, Graphs, OOP Design	Medium
Service (TCS, Infosys, Wipro, Cognizant)	Basic DSA, Aptitude, SQL	Easy
Startup (vary widely)	Practical coding, Full-stack, DSA basics	Easy–Medium

Structure / Algorithm	Key Operation	Complexity
Array	Random access	O(1)
Hash Map	Insert / Search / Delete	O(1) average
BST (balanced)	Insert / Search / Delete	O(log n)
Heap	Insert / Extract-min	O(log n)
Merge Sort	Sort	O(n log n)
Binary Search	Search in sorted array	O(log n)
BFS / DFS	Graph traversal	O(V + E)
Dijkstra (heap)	Shortest path	O((V+E) log V)
Trie	Insert / Search length-m word	O(m)
Segment Tree	Range query / update	O(log n)
Union-Find (optimised)	Union / Find	O(α(n)) ≈ O(1)

📋 What You Will Learn

1. Why DSA Matters for Every Developer

The Real Cost of Ignoring DSA

DSA in Everyday Software

2. Big O Notation & Complexity Analysis

What Does "O" Mean?

Common Complexity Classes

How to Calculate Big O

Space Complexity

Best, Average, and Worst Case

3. Arrays & Strings

How Arrays Work in Memory

Key Array Operations & Complexities

The Two-Pointer Technique

Sliding Window Technique

Important Array Problems to Practice

4. Linked Lists

Types of Linked Lists

Fast & Slow Pointer (Floyd's Cycle Detection)

Reversing a Linked List

Merging Two Sorted Linked Lists

Memory Management Implications

Key Linked List Problems

5. Stacks & Queues

Stack — Last In, First Out (LIFO)

Monotonic Stack

Queue — First In, First Out (FIFO)

Deque (Double-Ended Queue)

Key Stack & Queue Problems

6. Hashing & Hash Maps

How Hashing Works

Collisions & Handling

Using Hash Maps to Reduce Complexity

Hash Sets for O(1) Membership

Key Hashing Problems

7. Trees & Binary Search Trees

Binary Tree Basics

Binary Search Tree (BST)

Level-Order Traversal (BFS on Trees)

Key Tree Problems

8. Heaps & Priority Queues

Min-Heap vs Max-Heap

When to Use a Heap

9. Graphs & Graph Traversal

Graph Representations

Depth-First Search (DFS)

Breadth-First Search (BFS)

Topological Sort

Union-Find (Disjoint Set Union)

Dijkstra's Shortest Path

Key Graph Problems

10. Sorting Algorithms

Sorting Algorithm Comparison

Merge Sort — Divide & Conquer

Quick Sort — Average-Case King

Non-Comparison Sorts

11. Searching Algorithms

Linear Search — O(n)

Binary Search — O(log n)

Binary Search on the Answer

Key Binary Search Problems

12. Recursion & Backtracking

Thinking Recursively

Backtracking

Key Recursion & Backtracking Problems

13. Dynamic Programming

The DP Thinking Framework

Classic DP: 0/1 Knapsack

Longest Common Subsequence (LCS)

DP Problem Patterns at Learn with LSGP

14. Greedy Algorithms

When is Greedy Safe?

Activity Selection Problem

Key Greedy Problems

Bonus: Tries (Prefix Trees)

Why Not Just Use a Hash Map?

Complexity of Trie Operations

Real-World Trie Applications

Key Trie Problems

Bonus: Segment Trees & Advanced Topics