11. Stack Fundamentals: Valid Parentheses & Min Stack in O(1) Time • Data Structures & Algorithms: Blind 75 & Big Tech Interview Prep • Rishabh Ki Kaksha

Data Structures & Algorithms: Blind 75 & Big Tech Interview Prep › 11. Stack Fundamentals: Valid Parentheses & Min Stack in O(1) Time

35 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

# 11. Stack Fundamentals: Valid Parentheses & Min Stack in O(1) Time

> DSA Blind 75 Notes by Rishabh - Topic 11

---

### 1. Stack: LIFO (Last-In, First-Out 🥞)

Stack plate ki stack jaisa hota hai — sabse aakhri me dali gayi plate sabse pehle nikalti hai.

---

### 2. LeetCode #20: Valid Parentheses

```python
def isValid(s: str) -> bool:
    stack = []
    close_to_open = {')': '(', '}': '{', ']': '['}
    
    for char in s:
        if char in close_to_open:
            # Closing bracket -> Match with top of stack:
            if stack and stack[-1] == close_to_open[char]:
                stack.pop()
            else:
                return False
        else:
            stack.append(char) # Opening bracket
            
    return len(stack) == 0
```
*Time Complexity:* $O(N)$, *Space Complexity:* $O(N)$.

---

### 3. LeetCode #155: Min Stack in $O(1)$ Time

*Requirement:* `push`, `pop`, `top`, aur `getMin` saare operations **$O(1)$ time** me hone chahiye!

```python
class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = [] # Tracks current minimum at each level
        
    def push(self, val: int) -> None:
        self.stack.append(val)
        current_min = min(val, self.min_stack[-1] if self.min_stack else val)
        self.min_stack.append(current_min)
        
    def pop(self) -> None:
        self.stack.pop()
        self.min_stack.pop()
        
    def top(self) -> int:
        return self.stack[-1]
        
    def getMin(self) -> int:
        return self.min_stack[-1] # ⚡ O(1) instant lookup!
```

---

### 4. Master Comparison Matrix

| Stack Operation | Array Implementation | Linked List Implementation | Time Complexity |
| :--- | :--- | :--- | :--- |
| **`push(x)`** | `arr.append(x)` | Insert at head | $O(1)$ amortized |
| **`pop()`** | `arr.pop()` | Delete head | $O(1)$ |
| **`peek() / top()`** | `arr[-1]` | `head.val` | $O(1)$ |
| **`getMin()`** | Auxiliary Min Stack | Min tracking node | $O(1)$ |

---

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

1. **Bina extra `min_stack` array ke single stack me $O(1)$ Min Stack kaise implement karte hain?** -> Stack me values ke badle `2 * val - current_min` formula se encoded delta values store karke.
2. **Evaluate Reverse Polish Notation (LeetCode #150) me stack kaise help karta hai?** -> Operands ko push karte hain aur operator aate hi top 2 numbers ko pop karke calculate karke result wapas push karte hain.
3. **Recursion aur Stack me kya relation hai?** -> Har recursive function call OS Call Stack me ek naya stack frame push karti hai; kisi bhi recursive solution ko explicitly Stack use karke iterative banaya ja sakta hai.

---
**Next Topic:** 12. Monotonic Stack Pattern: Daily Temperatures & Next Greater Element

Loading lesson content...

JavaScript

Live Execution Terminal

Click "Execute Live" to run code.
                