Latest c1questions end date September 2025

gistfile1.txt

# **Algorithmic Solutions for Technical Interviews**
## A Comprehensive Guide to Capital One Programming Problems

---

## **Chapter 1: Array and Dynamic Programming**

### **1.1 Best Time to Buy and Sell Stock**
**Problem:** Given an array of prices where prices[i] represents the stock price on day i, find the maximum profit from a single buy-sell transaction.

**Algorithm Design:**
- **Approach:** Single-pass dynamic programming with state tracking
- **Key Insight:** Track minimum price seen so far and maximum profit possible

```javascript
/**
 * Time Complexity: O(n) - Single pass through array
 * Space Complexity: O(1) - Constant extra space
 * 
 * Algorithm:
 * 1. Initialize minPrice to infinity and maxProfit to 0
 * 2. For each price in the array:
 *    - Update minPrice to be minimum of current minPrice and current price
 *    - Update maxProfit to be maximum of current maxProfit and (price - minPrice)
 * 3. Return maxProfit
 */
function maxProfit(prices) {
    let minPrice = Infinity;
    let maxProfit = 0;
    
    for (let price of prices) {
        minPrice = Math.min(minPrice, price);
        maxProfit = Math.max(maxProfit, price - minPrice);
    }
    
    return maxProfit;
}

// Example: prices = [7,1,5,3,6,4]
// Day 1: minPrice = 7, maxProfit = 0
// Day 2: minPrice = 1, maxProfit = 0
// Day 3: minPrice = 1, maxProfit = 4
// Day 4: minPrice = 1, maxProfit = 4
// Day 5: minPrice = 1, maxProfit = 5
// Day 6: minPrice = 1, maxProfit = 5
// Result: 5
```

---

### **1.2 Coin Change**
**Problem:** Given coins of different denominations and a total amount, find the minimum number of coins needed to make the amount.

**Algorithm Design:**
- **Approach:** Bottom-up dynamic programming
- **Key Insight:** Build solution for each amount from 0 to target

```javascript
/**
 * Time Complexity: O(amount × n) where n is number of coin denominations
 * Space Complexity: O(amount) for DP array
 * 
 * Recurrence Relation:
 * dp[i] = min(dp[i], dp[i - coin] + 1) for each coin ≤ i
 * 
 * Base Case: dp[0] = 0 (0 coins needed for amount 0)
 */
function coinChange(coins, amount) {
    // Initialize DP array with infinity (impossible states)
    const dp = Array(amount + 1).fill(Infinity);
    dp[0] = 0; // Base case
    
    // Build up solution for each amount
    for (let i = 1; i <= amount; i++) {
        for (let coin of coins) {
            if (i >= coin) {
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }
    }
    
    return dp[amount] === Infinity ? -1 : dp[amount];
}

// Example: coins = [1,2,5], amount = 11
// DP Table Construction:
// dp[0] = 0
// dp[1] = 1 (1 coin)
// dp[2] = 1 (1 coin of 2)
// dp[3] = 2 (1+2)
// dp[4] = 2 (2+2)
// dp[5] = 1 (1 coin of 5)
// ...
// dp[11] = 3 (5+5+1)
```

---

## **Chapter 2: Stack and String Manipulation**

### **2.1 Valid Parentheses**
**Problem:** Determine if a string containing just '(', ')', '{', '}', '[', ']' is valid.

**Algorithm Design:**
- **Approach:** Stack-based matching
- **Key Insight:** Last opened must be first closed (LIFO)

```javascript
/**
 * Time Complexity: O(n) - Single pass through string
 * Space Complexity: O(n) - Stack can contain at most n/2 elements
 * 
 * Algorithm:
 * 1. Use stack to track expected closing brackets
 * 2. For opening brackets: push corresponding closing bracket
 * 3. For closing brackets: check if it matches top of stack
 * 4. Valid if stack is empty at end
 */
function isValid(s) {
    const stack = [];
    const map = { '(': ')', '{': '}', '[': ']' };
    
    for (let char of s) {
        if (map[char]) {
            // Opening bracket - push expected closing
            stack.push(map[char]);
        } else if (stack.pop() !== char) {
            // Closing bracket - must match stack top
            return false;
        }
    }
    
    return stack.length === 0;
}

// Example: s = "({[]})"
// Step 1: '(' → stack = [')']
// Step 2: '{' → stack = [')', '}']
// Step 3: '[' → stack = [')', '}', ']']
// Step 4: ']' → pop and match ✓, stack = [')', '}']
// Step 5: '}' → pop and match ✓, stack = [')']
// Step 6: ')' → pop and match ✓, stack = []
// Result: true
```

---

### **2.2 Simplify Path**
**Problem:** Given an absolute path for a Unix-style file system, simplify it to canonical form.

**Algorithm Design:**
- **Approach:** Stack-based directory navigation
- **Key Insight:** Use stack to handle '..' (parent directory) operations

```javascript
/**
 * Time Complexity: O(n) - Process each character once
 * Space Complexity: O(n) - Stack for path components
 * 
 * Rules:
 * - '.' means current directory (ignore)
 * - '..' means parent directory (pop from stack)
 * - Empty components are ignored
 * - Multiple slashes treated as single slash
 */
function simplifyPath(path) {
    const stack = [];
    const parts = path.split('/');
    
    for (let part of parts) {
        if (part === '..') {
            stack.pop(); // Go to parent directory
        } else if (part && part !== '.') {
            stack.push(part); // Valid directory name
        }
        // Ignore empty parts and '.'
    }
    
    return '/' + stack.join('/');
}

// Example: path = "/home/../usr//bin/./test"
// Split: ["", "home", "..", "usr", "", "bin", ".", "test"]
// Process:
// "home" → stack = ["home"]
// ".." → stack = []
// "usr" → stack = ["usr"]
// "bin" → stack = ["usr", "bin"]
// "test" → stack = ["usr", "bin", "test"]
// Result: "/usr/bin/test"
```

---

## **Chapter 3: Matrix Algorithms**

### **3.1 Number of Islands**
**Problem:** Given a 2D grid of '1's (land) and '0's (water), count the number of islands.

**Algorithm Design:**
- **Approach:** Depth-First Search with marking
- **Key Insight:** Each DFS explores one complete island

```javascript
/**
 * Time Complexity: O(m × n) - Visit each cell once
 * Space Complexity: O(m × n) - Recursion stack in worst case
 * 
 * Algorithm:
 * 1. Iterate through each cell in grid
 * 2. When land ('1') is found, increment island count
 * 3. Use DFS to mark all connected land as visited ('0')
 * 4. Continue until all cells are processed
 */
function numIslands(grid) {
    if (!grid || !grid.length) return 0;
    
    const m = grid.length;
    const n = grid[0].length;
    let islands = 0;
    
    function dfs(i, j) {
        // Boundary check and water check
        if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] === '0') {
            return;
        }
        
        // Mark as visited by converting to water
        grid[i][j] = '0';
        
        // Explore all 4 directions
        dfs(i + 1, j); // Down
        dfs(i - 1, j); // Up
        dfs(i, j + 1); // Right
        dfs(i, j - 1); // Left
    }
    
    // Main loop to find islands
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (grid[i][j] === '1') {
                islands++;
                dfs(i, j); // Sink the entire island
            }
        }
    }
    
    return islands;
}

// Example: 
// [['1','1','0','0'],
//  ['1','1','0','0'],
//  ['0','0','1','0'],
//  ['0','0','0','1']]
// 
// Island 1: (0,0), (0,1), (1,0), (1,1)
// Island 2: (2,2)
// Island 3: (3,3)
// Result: 3
```

---

### **3.2 Spiral Matrix**
**Problem:** Given an m×n matrix, return all elements in spiral order.

**Algorithm Design:**
- **Approach:** Layer-by-layer traversal with boundary tracking
- **Key Insight:** Maintain four boundaries and shrink after each direction

```javascript
/**
 * Time Complexity: O(m × n) - Visit each element once
 * Space Complexity: O(m × n) - Output array
 * 
 * Algorithm:
 * 1. Initialize four boundaries: top, bottom, left, right
 * 2. Traverse in spiral order:
 *    - Left to right along top row
 *    - Top to bottom along right column
 *    - Right to left along bottom row (if row exists)
 *    - Bottom to top along left column (if column exists)
 * 3. Shrink boundaries after each direction
 */
function spiralOrder(matrix) {
    const result = [];
    if (!matrix.length) return result;
    
    let top = 0, bottom = matrix.length - 1;
    let left = 0, right = matrix[0].length - 1;
    
    while (top <= bottom && left <= right) {
        // Traverse right along top row
        for (let i = left; i <= right; i++) {
            result.push(matrix[top][i]);
        }
        top++;
        
        // Traverse down along right column
        for (let i = top; i <= bottom; i++) {
            result.push(matrix[i][right]);
        }
        right--;
        
        // Traverse left along bottom row (if row exists)
        if (top <= bottom) {
            for (let i = right; i >= left; i--) {
                result.push(matrix[bottom][i]);
            }
            bottom--;
        }
        
        // Traverse up along left column (if column exists)
        if (left <= right) {
            for (let i = bottom; i >= top; i--) {
                result.push(matrix[i][left]);
            }
            left++;
        }
    }
    
    return result;
}

// Example: [[1,2,3],[4,5,6],[7,8,9]]
// Iteration 1:
//   Right: 1,2,3 (top=0, left=0→2)
//   Down: 6,9 (right=2, top=1→2)
//   Left: 8,7 (bottom=2, right=1→0)
//   Up: 4 (left=0, bottom=1→1)
// Iteration 2:
//   Right: 5 (top=1, left=1→1)
// Result: [1,2,3,6,9,8,7,4,5]
```

---

### **3.3 Rotate Image**
**Problem:** Rotate an n×n matrix 90 degrees clockwise in-place.

**Algorithm Design:**
- **Approach:** Transpose + Reverse
- **Key Insight:** 90° rotation = Transpose + Horizontal flip

```javascript
/**
 * Time Complexity: O(n²) - Process each element twice
 * Space Complexity: O(1) - In-place transformation
 * 
 * Mathematical Transformation:
 * 1. Transpose: matrix[i][j] ↔ matrix[j][i]
 * 2. Reverse each row
 * 
 * Visual proof:
 * Original: [1,2,3]    Transpose: [1,4,7]    Reverse: [7,4,1]
 *           [4,5,6]               [2,5,8]             [8,5,2]
 *           [7,8,9]               [3,6,9]             [9,6,3]
 */
function rotate(matrix) {
    const n = matrix.length;
    
    // Step 1: Transpose matrix (swap along diagonal)
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            [matrix[i][j], matrix[j][i]] = [matrix[j][i], matrix[i][j]];
        }
    }
    
    // Step 2: Reverse each row
    for (let i = 0; i < n; i++) {
        matrix[i].reverse();
    }
}

// Alternative approach: Four-way swap
function rotateAlternative(matrix) {
    const n = matrix.length;
    
    // Process matrix in layers
    for (let layer = 0; layer < Math.floor(n / 2); layer++) {
        const first = layer;
        const last = n - 1 - layer;
        
        for (let i = first; i < last; i++) {
            const offset = i - first;
            const top = matrix[first][i];
            
            // left → top
            matrix[first][i] = matrix[last - offset][first];
            // bottom → left
            matrix[last - offset][first] = matrix[last][last - offset];
            // right → bottom
            matrix[last][last - offset] = matrix[i][last];
            // top → right
            matrix[i][last] = top;
        }
    }
}
```

---

## **Chapter 4: Linked List Algorithms**

### **4.1 Merge Two Sorted Lists**
**Problem:** Merge two sorted linked lists into one sorted list.

**Algorithm Design:**
- **Approach:** Two-pointer merge with dummy head
- **Key Insight:** Always attach the smaller node

```javascript
/**
 * Time Complexity: O(m + n) - Process each node once
 * Space Complexity: O(1) - Only pointer manipulation
 * 
 * Algorithm:
 * 1. Create dummy head for simplified logic
 * 2. Compare heads of both lists
 * 3. Attach smaller node to result
 * 4. Advance pointer of chosen list
 * 5. Attach remaining list when one exhausted
 */
function mergeTwoLists(list1, list2) {
    // Dummy head simplifies edge cases
    const dummy = new ListNode(0);
    let current = dummy;
    
    // Merge while both lists have nodes
    while (list1 && list2) {
        if (list1.val <= list2.val) {
            current.next = list1;
            list1 = list1.next;
        } else {
            current.next = list2;
            list2 = list2.next;
        }
        current = current.next;
    }
    
    // Attach remaining nodes (if any)
    current.next = list1 || list2;
    
    return dummy.next;
}

// Recursive approach (more elegant but uses O(m+n) stack space)
function mergeTwoListsRecursive(list1, list2) {
    if (!list1) return list2;
    if (!list2) return list1;
    
    if (list1.val <= list2.val) {
        list1.next = mergeTwoListsRecursive(list1.next, list2);
        return list1;
    } else {
        list2.next = mergeTwoListsRecursive(list1, list2.next);
        return list2;
    }
}
```

---

### **4.2 Reverse Nodes in k-Group**
**Problem:** Reverse every k consecutive nodes in a linked list.

**Algorithm Design:**
- **Approach:** Recursive group reversal
- **Key Insight:** Check group size before reversing

```javascript
/**
 * Time Complexity: O(n) - Process each node twice
 * Space Complexity: O(n/k) - Recursion depth
 * 
 * Algorithm:
 * 1. Count if k nodes available
 * 2. If yes, reverse k nodes
 * 3. Recursively process remaining list
 * 4. Connect reversed group to processed remainder
 */
function reverseKGroup(head, k) {
    // Count available nodes
    let count = 0;
    let node = head;
    while (node && count < k) {
        node = node.next;
        count++;
    }
    
    // If k nodes available, reverse them
    if (count === k) {
        let current = head;
        let prev = null;
        let next = null;
        
        // Reverse k nodes
        for (let i = 0; i < k; i++) {
            next = current.next;
            current.next = prev;
            prev = current;
            current = next;
        }
        
        // head is now the tail of reversed group
        // Recursively reverse remaining groups
        head.next = reverseKGroup(current, k);
        
        // prev is the new head of this group
        return prev;
    }
    
    // Less than k nodes remain
    return head;
}

// Iterative approach with dummy head
function reverseKGroupIterative(head, k) {
    const dummy = new ListNode(0);
    dummy.next = head;
    let prevGroup = dummy;
    
    while (head) {
        // Check if k nodes available
        let tail = prevGroup;
        for (let i = 0; i < k; i++) {
            tail = tail.next;
            if (!tail) return dummy.next;
        }
        
        // Save next group head
        let nextGroup = tail.next;
        
        // Reverse current group
        let prev = tail.next;
        let current = head;
        while (current !== nextGroup) {
            let next = current.next;
            current.next = prev;
            prev = current;
            current = next;
        }
        
        // Connect to previous group
        let tmp = prevGroup.next;
        prevGroup.next = tail;
        prevGroup = tmp;
        head = nextGroup;
    }
    
    return dummy.next;
}
```

---

## **Chapter 5: Tree and Graph Algorithms**

### **5.1 Binary Tree Paths**
**Problem:** Return all root-to-leaf paths in a binary tree.

**Algorithm Design:**
- **Approach:** DFS with path building
- **Key Insight:** Build path string during traversal

```javascript
/**
 * Time Complexity: O(n) - Visit each node once
 * Space Complexity: O(n) - Path strings and recursion
 * 
 * Algorithm:
 * 1. Use DFS to traverse tree
 * 2. Build path string as we go down
 * 3. When leaf reached, add complete path to result
 * 4. Backtrack automatically via recursion
 */
function binaryTreePaths(root) {
    const result = [];
    
    function dfs(node, path) {
        if (!node) return;
        
        // Add current node to path
        path += node.val;
        
        // Check if leaf node
        if (!node.left && !node.right) {
            result.push(path);
        } else {
            // Continue path with arrow
            path += '->';
            dfs(node.left, path);
            dfs(node.right, path);
        }
    }
    
    dfs(root, '');
    return result;
}

// Iterative approach using stack
function binaryTreePathsIterative(root) {
    if (!root) return [];
    
    const result = [];
    const stack = [[root, String(root.val)]];
    
    while (stack.length) {
        const [node, path] = stack.pop();
        
        // Check if leaf
        if (!node.left && !node.right) {
            result.push(path);
        }
        
        // Add children to stack
        if (node.right) {
            stack.push([node.right, path + '->' + node.right.val]);
        }
        if (node.left) {
            stack.push([node.left, path + '->' + node.left.val]);
        }
    }
    
    return result;
}
```

---

### **5.2 Word Search II (Trie + Backtracking)**
**Problem:** Find all words from a dictionary that exist in a 2D board.

**Algorithm Design:**
- **Approach:** Trie for prefix matching + DFS backtracking
- **Key Insight:** Trie enables efficient prefix checking

```javascript
/**
 * Time Complexity: O(m×n×4^L) where L is max word length
 * Space Complexity: O(total characters in dictionary)
 * 
 * Algorithm:
 * 1. Build Trie from word dictionary
 * 2. DFS from each cell with Trie node tracking
 * 3. Mark cells as visited during DFS
 * 4. Collect words when Trie leaf reached
 * 5. Backtrack by restoring cell values
 */
class TrieNode {
    constructor() {
        this.children = {};
        this.word = null; // Store complete word at leaf
    }
}

function findWords(board, words) {
    // Build Trie
    const root = new TrieNode();
    for (let word of words) {
        let node = root;
        for (let char of word) {
            if (!node.children[char]) {
                node.children[char] = new TrieNode();
            }
            node = node.children[char];
        }
        node.word = word;
    }
    
    const result = [];
    const m = board.length, n = board[0].length;
    
    function dfs(i, j, node) {
        const char = board[i][j];
        
        // No matching prefix
        if (!node.children[char]) return;
        
        node = node.children[char];
        
        // Found a word
        if (node.word) {
            result.push(node.word);
            node.word = null; // Avoid duplicates
        }
        
        // Mark as visited
        board[i][j] = '#';
        
        // Explore 4 directions
        if (i > 0) dfs(i - 1, j, node);
        if (i < m - 1) dfs(i + 1, j, node);
        if (j > 0) dfs(i, j - 1, node);
        if (j < n - 1) dfs(i, j + 1, node);
        
        // Backtrack
        board[i][j] = char;
    }
    
    // Start DFS from each cell
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            dfs(i, j, root);
        }
    }
    
    return result;
}

// Optimization: Prune Trie branches after finding words
function findWordsOptimized(board, words) {
    // Similar setup...
    
    function dfs(i, j, parent, char) {
        const node = parent.children[char];
        
        if (node.word) {
            result.push(node.word);
            node.word = null;
        }
        
        board[i][j] = '#';
        
        // Explore neighbors...
        
        board[i][j] = char;
        
        // Prune: Remove leaf nodes with no words
        if (Object.keys(node.children).length === 0) {
            delete parent.children[char];
        }
    }
    
    // Rest of implementation...
}
```

---

## **Chapter 6: Advanced Algorithms**

### **6.1 Largest Rectangle in Histogram**
**Problem:** Find the largest rectangle area in a histogram.

**Algorithm Design:**
- **Approach:** Monotonic stack for tracking potential rectangles
- **Key Insight:** Rectangle height limited by smallest bar

```javascript
/**
 * Time Complexity: O(n) - Each bar pushed/popped once
 * Space Complexity: O(n) - Stack storage
 * 
 * Algorithm:
 * 1. Use stack to maintain increasing heights
 * 2. When smaller height found, calculate areas
 * 3. Width determined by stack indices
 * 4. Add sentinel value to process remaining bars
 */
function largestRectangleArea(heights) {
    const stack = [];
    let maxArea = 0;
    
    // Add sentinel to handle remaining bars
    heights.push(0);
    
    for (let i = 0; i < heights.length; i++) {
        // Pop and calculate area while current height is smaller
        while (stack.length && heights[i] < heights[stack[stack.length - 1]]) {
            const h = heights[stack.pop()];
            // Width calculation:
            // If stack empty: width = i (all bars to left were taller)
            // Else: width = i - stack.top - 1 (bars between stack.top and i)
            const w = stack.length ? i - stack[stack.length - 1] - 1 : i;
            maxArea = Math.max(maxArea, h * w);
        }
        stack.push(i);
    }
    
    return maxArea;
}

// Example walkthrough: [2,1,5,6,2,3]
// i=0: stack=[0], heights[0]=2
// i=1: heights[1]=1 < 2
//      Pop 0: h=2, w=1, area=2
//      stack=[1]
// i=2: stack=[1,2], heights[2]=5
// i=3: stack=[1,2,3], heights[3]=6
// i=4: heights[4]=2 < 6
//      Pop 3: h=6, w=1, area=6
//      Pop 2: h=5, w=2, area=10
//      stack=[1,4]
// Continue...
// maxArea = 10
```

---

### **6.2 Text Justification**
**Problem:** Format text with full justification (even spacing between words).

**Algorithm Design:**
- **Approach:** Greedy line packing with space distribution
- **Key Insight:** Distribute extra spaces from left to right

```javascript
/**
 * Time Complexity: O(n) - Process each word once
 * Space Complexity: O(n) - Output storage
 * 
 * Algorithm:
 * 1. Pack words greedily into lines
 * 2. Calculate spaces needed for justification
 * 3. Distribute spaces evenly (extra spaces go left)
 * 4. Handle special cases: last line, single word
 */
function fullJustify(words, maxWidth) {
    const result = [];
    let i = 0;
    
    while (i < words.length) {
        // Find words for current line
        let j = i + 1;
        let lineLength = words[i].length;
        
        // Add words while they fit
        while (j < words.length && 
               lineLength + words[j].length + (j - i) <= maxWidth) {
            lineLength += words[j].length;
            j++;
        }
        
        const gaps = j - i - 1;
        let line = '';
        
        // Case 1: Last line or single word - left justify
        if (j === words.length || gaps === 0) {
            for (let k = i; k < j; k++) {
                line += words[k];
                if (k < j - 1) line += ' ';
            }
            // Pad with spaces
            while (line.length < maxWidth) line += ' ';
        } 
        // Case 2: Middle line - full justify
        else {
            const spaces = maxWidth - lineLength;
            const spacesPerGap = Math.floor(spaces / gaps);
            const extraSpaces = spaces % gaps;
            
            for (let k = i; k < j; k++) {
                line += words[k];
                if (k < j - 1) {
                    // Add base spaces plus extra (from left)
                    line += ' '.repeat(spacesPerGap + (k - i < extraSpaces ? 1 : 0));
                }
            }
        }
        
        result.push(line);
        i = j;
    }
    
    return result;
}

// Example: words = ["This", "is", "an", "example"], maxWidth = 16
// Line 1: "This" + "is" + "an" = 8 chars, 2 gaps
//         Spaces needed: 16 - 8 = 8
//         Distribution: 4 spaces per gap
//         Result: "This    is    an"
// Line 2: "example" = 7 chars (last line)
//         Left justify: "example         "
```

---

### **6.3 Meeting Rooms II**
**Problem:** Find minimum number of meeting rooms required.

**Algorithm Design:**
- **Approach:** Separate start/end times with two-pointer technique
- **Key Insight:** Track room usage at each time point

```javascript
/**
 * Time Complexity: O(n log n) - Sorting
 * Space Complexity: O(n) - Separate arrays
 * 
 * Algorithm:
 * 1. Separate and sort start/end times
 * 2. Use two pointers to simulate timeline
 * 3. If start < end: need new room
 * 4. If start >= end: can reuse room
 */
function minMeetingRooms(intervals) {
    if (!intervals.length) return 0;
    
    // Separate and sort times
    const starts = intervals.map(i => i[0]).sort((a, b) => a - b);
    const ends = intervals.map(i => i[1]).sort((a, b) => a - b);
    
    let rooms = 0;
    let endPtr = 0;
    
    // Process each start time
    for (let i = 0; i < starts.length; i++) {
        if (starts[i] < ends[endPtr]) {
            // Meeting starts before earliest end - need new room
            rooms++;
        } else {
            // Can reuse a room that just ended
            endPtr++;
        }
    }
    
    return rooms;
}

// Priority Queue approach
function minMeetingRoomsHeap(intervals) {
    if (!intervals.length) return 0;
    
    // Sort by start time
    intervals.sort((a, b) => a[0] - b[0]);
    
    // Min heap of end times
    const minHeap = new MinPriorityQueue();
    minHeap.enqueue(intervals[0][1]);
    
    for (let i = 1; i < intervals.length; i++) {
        // If earliest ending meeting has ended
        if (intervals[i][0] >= minHeap.front().element) {
            minHeap.dequeue();
        }
        // Add current meeting end time
        minHeap.enqueue(intervals[i][1]);
    }
    
    return minHeap.size();
}

// Example: [[0,30],[5,10],[15,20]]
// Starts: [0,5,15]
// Ends: [10,20,30]
// 
// i=0: start=0 < end=10 → rooms=1
// i=1: start=5 < end=10 → rooms=2
// i=2: start=15 >= end=10 → endPtr=1 (reuse room)
// Result: 2 rooms needed
```

---

## **Chapter 7: Design Problems**

### **7.1 Simple Bank System**
**Problem:** Design a bank system with transfer, deposit, and withdraw operations.

**Algorithm Design:**
- **Approach:** Array-based account storage with validation
- **Key Insight:** Account numbers are 1-indexed

```javascript
/**
 * Time Complexity: O(1) per operation
 * Space Complexity: O(n) for n accounts
 * 
 * Design Principles:
 * 1. Validate account existence
 * 2. Check sufficient balance for operations
 * 3. Maintain data consistency
 */
class Bank {
    constructor(balance) {
        this.balance = balance;
        this.n = balance.length;
    }
    
    /**
     * Transfer money between accounts
     * @param {number} account1 - Source account (1-indexed)
     * @param {number} account2 - Destination account (1-indexed)
     * @param {number} money - Amount to transfer
     * @return {boolean} - Success status
     */
    transfer(account1, account2, money) {
        // Validate both accounts exist
        if (!this.isValid(account1) || !this.isValid(account2)) {
            return false;
        }
        
        // Check sufficient balance
        if (this.balance[account1 - 1] < money) {
            return false;
        }
        
        // Perform atomic transfer
        this.balance[account1 - 1] -= money;
        this.balance[account2 - 1] += money;
        return true;
    }
    
    deposit(account, money) {
        if (!this.isValid(account)) return false;
        this.balance[account - 1] += money;
        return true;
    }
    
    withdraw(account, money) {
        if (!this.isValid(account)) return false;
        if (this.balance[account - 1] < money) return false;
        this.balance[account - 1] -= money;
        return true;
    }
    
    // Helper: Validate account number
    isValid(account) {
        return account >= 1 && account <= this.n;
    }
}

// Extension: Thread-safe version (conceptual)
class ThreadSafeBank extends Bank {
    constructor(balance) {
        super(balance);
        this.locks = new Array(balance.length).fill(false);
    }
    
    async transfer(account1, account2, money) {
        // Acquire locks in order to prevent deadlock
        const [first, second] = account1 < account2 
            ? [account1, account2] 
            : [account2, account1];
        
        await this.acquireLock(first);
        await this.acquireLock(second);
        
        try {
            return super.transfer(account1, account2, money);
        } finally {
            this.releaseLock(first);
            this.releaseLock(second);
        }
    }
}
```

---

## **Appendix A: Complexity Analysis Summary**

| Problem | Time Complexity | Space Complexity | Key Technique |
|---------|----------------|------------------|---------------|
| Best Time to Buy and Sell Stock | O(n) | O(1) | Dynamic Programming |
| Valid Parentheses | O(n) | O(n) | Stack |
| Number of Islands | O(m×n) | O(m×n) | DFS/BFS |
| Coin Change | O(amount×n) | O(amount) | Dynamic Programming |
| Spiral Matrix | O(m×n) | O(m×n) | Simulation |
| Meeting Rooms II | O(n log n) | O(n) | Sorting + Two Pointers |
| Word Search II | O(m×n×4^L) | O(total chars) | Trie + Backtracking |
| Largest Rectangle | O(n) | O(n) | Monotonic Stack |
| Text Justification | O(n) | O(n) | Greedy + String |
| Reverse Nodes k-Group | O(n) | O(n/k) | Recursion |

---

## **Appendix B: Common Patterns**

### **Two Pointers**
- Merge sorted arrays/lists
- Find pairs with target sum
- Partition arrays

### **Sliding Window**
- Subarray/substring problems
- Fixed or variable window size
- Track window properties

### **Dynamic Programming**
- Optimization problems
- Count ways/paths
- Decision making

### **Backtracking**
- Generate combinations/permutations
- Path finding with constraints
- Puzzle solving

### **Graph Traversal**
- Connected components
- Shortest path
- Topological sort

### **Monotonic Stack/Queue**
- Next greater/smaller element
- Maximum rectangle/histogram
- Sliding window maximum

---

This algorithmic guide provides comprehensive solutions with detailed explanations, complexity analysis, and implementation patterns commonly found in technical interviews. Each solution is optimized for both time and space complexity while maintaining code clarity and correctness.