28. 2D Dynamic Programming: Unique Paths, Longest Common Subsequence (LCS) & Edit Distance • Data Structures & Algorithms: Blind 75 & Big Tech Interview Prep • Rishabh Ki Kaksha

Data Structures & Algorithms: Blind 75 & Big Tech Interview Prep › 28. 2D Dynamic Programming: Unique Paths, Longest Common Subsequence (LCS) & Edit Distance

55 mins

← Prev Next →

Course Syllabus

Module 1: Big-O Asymptotics, Arrays & Sliding Window

01. Time & Space Complexity Masterclass: Big-O, Big-Theta, Big-Omega & Amortized Analysis 02. Arrays & Hashing: Two Sum, Contains Duplicate & Valid Anagram (Hash Table Lookups) 03. Prefix Sum & Kadane's Algorithm (Maximum Subarray Problem in O(N)) 04. Sliding Window Pattern: Fixed vs Dynamic Windows (Best Time to Buy/Sell Stock)

Module 2: Two Pointers & Binary Search Systems

05. Two Pointers Pattern: Valid Palindrome, 3Sum & Container With Most Water 06. Binary Search Foundations: Search in Rotated Sorted Array & Find Minimum 07. Binary Search on Answer Space: Koko Eating Bananas & Capacity to Ship Packages

Module 3: Linked Lists & Fast-Slow Pointer Patterns

08. Singly vs Doubly Linked Lists & In-Place Pointer Manipulation (Reverse Linked List) 09. Fast & Slow Pointer (Floyd's Cycle Detection): Linked List Cycle & Middle Node 10. Merging & Reordering: Merge Two Sorted Lists, Reorder List & Remove Nth Node

Module 4: Stacks, Queues & Monotonic Stack Architecture

11. Stack Fundamentals: Valid Parentheses & Min Stack in O(1) Time 12. Monotonic Stack Pattern: Daily Temperatures & Next Greater Element 13. Hard Stack Coding: Largest Rectangle in Histogram & Trapping Rain Water

Module 5: Trees, Binary Search Trees & DFS/BFS Traversals

14. Binary Tree Architecture: Max Depth, Same Tree & Invert Binary Tree 15. BFS Level-Order Traversal & Binary Tree Right Side View 16. Binary Search Tree (BST) Properties: Validate BST & Lowest Common Ancestor (LCA) 17. Tree Path Sums & Serialize / Deserialize Binary Tree (Hard)

Module 6: Heaps, Priority Queues & Top-K Problems

18. Min Heap & Max Heap Internals: Array Representation & Heapify in O(N) 19. Top-K Elements Pattern: Kth Largest Element in an Array & Top K Frequent Elements 20. Two-Heap Pattern: Find Median from Data Stream (Hard)

Module 7: Graphs, Topological Sort & Shortest Paths (Dijkstra)

21. Graph Representations (Adjacency Matrix vs List) & DFS/BFS Traversal 22. Matrix Graph Traversal: Number of Islands, Max Area of Island & Clone Graph 23. Topological Sort (Kahn's Algorithm): Course Schedule I & II (Cycle Detection) 24. Disjoint Set Union (DSU / Union-Find): Redundant Connection & Number of Connected Components

Module 8: Dynamic Programming, Backtracking & Bit Manipulation

25. Backtracking Pattern: Subsets, Permutations, Combination Sum & Word Search 26. 1D Dynamic Programming: Climbing Stairs, House Robber & Coin Change 27. Longest Increasing Subsequence (LIS): O(N^2) DP vs O(N log N) Patience Sort 28. 2D Dynamic Programming: Unique Paths, Longest Common Subsequence (LCS) & Edit Distance 29. 0/1 Knapsack Pattern & Partition Equal Subset Sum 30. Bit Manipulation Tricks: Number of 1 Bits (Hamming Weight), Counting Bits & Missing Number

Interactive Lesson Studio

# 28. 2D Dynamic Programming: Unique Paths, Longest Common Subsequence (LCS) & Edit Distance

> DSA Blind 75 Notes by Rishabh - Topic 28

---

### 1. LeetCode #62: Unique Paths (Grid DP)

$$dp[r][c] = dp[r+1][c] + dp[r][c+1]$$

```python
def uniquePaths(m: int, n: int) -> int:
    row = [1] * n # Bottom row is all 1s
    for _ in range(m - 1):
        new_row = [1] * n
        for c in range(n - 2, -1, -1):
            new_row[c] = new_row[c + 1] + row[c]
        row = new_row
    return row[0]
```
*Complexity:* $O(M \cdot N)$ Time, $O(N)$ Space.

---

### 2. LeetCode #1143: Longest Common Subsequence (LCS) 🧬

*Match:* $1 + dp[i+1][j+1]$  
*Mismatch:* $\max(dp[i+1][j], dp[i][j+1])$

```python
def longestCommonSubsequence(text1: str, text2: str) -> int:
    dp = [[0] * (len(text2) + 1) for _ in range(len(text1) + 1)]
    
    for i in range(len(text1) - 1, -1, -1):
        for j in range(len(text2) - 1, -1, -1):
            if text1[i] == text2[j]:
                dp[i][j] = 1 + dp[i + 1][j + 1]
            else:
                dp[i][j] = max(dp[i + 1][j], dp[i][j + 1])
                
    return dp[0][0]
```

---

### 3. LeetCode #72: Edit Distance (Levenshtein Distance Hard ✏️)

Operations: Insert, Delete, Replace.

```python
def minDistance(word1: str, word2: str) -> int:
    m, n = len(word1), len(word2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    for i in range(m + 1): dp[i][n] = m - i
    for j in range(n + 1): dp[m][j] = n - j
        
    for i in range(m - 1, -1, -1):
        for j in range(n - 1, -1, -1):
            if word1[i] == word2[j]:
                dp[i][j] = dp[i + 1][j + 1]
            else:
                dp[i][j] = 1 + min(
                    dp[i][j + 1],     # Insert
                    dp[i + 1][j],     # Delete
                    dp[i + 1][j + 1]  # Replace
                )
    return dp[0][0]
```

---

### 4. Master Comparison Matrix

| Problem | Transition on Match | Transition on Mismatch | Complexity |
| :--- | :--- | :--- | :--- |
| **Unique Paths** | N/A | $dp[r][c] = \text{Down} + \text{Right}$ | $O(M \cdot N) / O(N)$ |
| **LCS** | $1 + dp[i+1][j+1]$ | $\max(\text{Skip } 1, \text{Skip } 2)$ | $O(M \cdot N) / O(\min(M, N))$ |
| **Edit Distance** | $dp[i+1][j+1]$ | $1 + \min(\text{Insert}, \text{Delete}, \text{Replace})$| $O(M \cdot N) / O(N)$ |

---

### 5. Interview Ke 3 Sawal Is Topic Se

1. **2D DP me Space Optimization $O(N)$ kaise ki jaati hai?** -> Kyunki current cell calculate karne ke liye sirf previous row aur current row chahiye hoti hai, isliye $M \times N$ matrix ke badle 2 rows maintain ki jaati hain.
2. **Diff algorithms (Git diff) me LCS kaise use hota hai?** -> Files ke lines ko string tokens treat karke longest common sequence dhoondhi jaati hai aur non-matching parts addition `+` ya deletion `-` bante hain.
3. **Unique Paths II (with Obstacles) kaise handle hota hai?** -> Obstacle cell (`grid[r][c] == 1`) par $dp[r][c] = 0$ set kar dete hain.

---
**Next Topic:** 29. 0/1 Knapsack Pattern & Partition Equal Subset Sum

Loading lesson content...

JavaScript

Full IDE

Live Execution Terminal

Click "Execute Live" to run code.
                

Lesson Mastery AI Quiz

AI Doubt Solver

CERTIFICATE OF COMPLETION

Rishabh Gehlot

PHP 8+ & Laravel 11 Master Track