27. Longest Increasing Subsequence (LIS): O(N^2) DP vs O(N log N) Patience Sort • Data Structures & Algorithms: Blind 75 & Big Tech Interview Prep • Rishabh Ki Kaksha

Data Structures & Algorithms: Blind 75 & Big Tech Interview Prep › 27. Longest Increasing Subsequence (LIS): O(N^2) DP vs O(N log N) Patience Sort

50 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

# 27. Longest Increasing Subsequence (LIS): O(N^2) DP vs O(N log N) Patience Sort

> DSA Blind 75 Notes by Rishabh - Topic 27

---

### 1. LeetCode #300: Longest Increasing Subsequence (LIS) 📈

*Problem:* Array me strictly increasing subsequence ki maximum length dhoondho.

#### Approach 1: Classic DP ($O(N^2)$ Time, $O(N)$ Space)
$$dp[i] = 1 + \max(\{dp[j] \mid j < i \text{ and } \text{nums}[j] < \text{nums}[i]\})$$

```python
def lengthOfLIS(nums: list[int]) -> int:
    dp = [1] * len(nums)
    for i in range(len(nums) - 1, -1, -1):
        for j in range(i + 1, len(nums)):
            if nums[i] < nums[j]:
                dp[i] = max(dp[i], 1 + dp[j])
    return max(dp)
```

---

### 2. Approach 2: Patience Sorting + Binary Search ($O(N \log N)$ ⚡)

Solitaire card game ki tarah: Har number ko uske pehle available pile me place karo jo usse bada ya barabar ho:

```python
import bisect

def lengthOfLIS_optimal(nums: list[int]) -> int:
    tails = []
    
    for num in nums:
        idx = bisect.bisect_left(tails, num)
        if idx == len(tails):
            tails.append(num) # Extends longest subsequence!
        else:
            tails[idx] = num  # Replaces element with smaller tail!
            
    return len(tails)
```
*Time Complexity:* $O(N \log N)$, *Space Complexity:* $O(N)$.

---

### 3. Master Comparison Matrix

| Approach | Time Complexity | Space Complexity | Can Reconstruct LIS Sequence? |
| :--- | :--- | :--- | :--- |
| **Standard 1D DP** | $O(N^2)$ | $O(N)$ | ✅ Yes (Follow parent pointers) |
| **Patience Binary Search**| ⚡ **$O(N \log N)$** | $O(N)$ | Length only (`tails` is not the actual LIS) |

---

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

1. **Russian Doll Envelopes (LeetCode #354 Hard) LIS se kaise solve hota hai?** -> Width ko ascending sort karo aur equal width par height ko **descending sort** karo, fir direct heights array par 1D LIS $O(N \log N)$ run karo!
2. **`tails` array actual LIS elements kyu nahi represent karta?** -> Kyunki replacements sirf future numbers ke liye smaller tail create karte hain; lekin `tails` array ka length hamesha exact maximum LIS length ke barabar hota hai.
3. **Number of Longest Increasing Subsequences (LeetCode #673) kaise count karte hain?** -> Ek extra `count` array maintain karke jo max length aane par previous path counts ko add karta hai.

---
**Next Topic:** 28. 2D Dynamic Programming: Unique Paths, Longest Common Subsequence (LCS) & Edit Distance

Loading lesson content...

JavaScript

Live Execution Terminal

Click "Execute Live" to run code.
                