FB top 100

fbtop100.js

# **Algorithmic Problem Solving: A Comprehensive JavaScript Guide**

## **Table of Contents**

---

## **Chapter 1: Fundamental Array Algorithms**

### **1.1 The Two Sum Problem**
**Problem Statement:** Given an array of integers and a target sum, find two numbers that add up to the target.

**Algorithmic Approach:**
```javascript
/**
 * Algorithm: Hash Table Complement Search
 * Time Complexity: O(n)
 * Space Complexity: O(n)
 * 
 * Theorem: For any element x in array A, if target - x exists in A,
 *          then x and (target - x) form a valid pair.
 */
function twoSum(nums, target) {
    // Initialize hash table for O(1) lookup
    const complementMap = new Map();
    
    // Single-pass algorithm
    for (let i = 0; i < nums.length; i++) {
        const complement = target - nums[i];
        
        // Check if complement exists
        if (complementMap.has(complement)) {
            return [complementMap.get(complement), i];
        }
        
        // Store current element with its index
        complementMap.set(nums[i], i);
    }
    
    return []; // No solution exists
}

// Proof of Correctness:
// 1. If solution exists, we'll find it in one pass
// 2. Hash table ensures we don't use same element twice
// 3. Time optimal: Ω(n) lower bound for unsorted array
```

### **1.2 Maximum Subarray (Kadane's Algorithm)**
**Problem Statement:** Find the contiguous subarray with maximum sum.

```javascript
/**
 * Algorithm: Dynamic Programming (Kadane's Algorithm)
 * Time Complexity: O(n)
 * Space Complexity: O(1)
 * 
 * Recurrence Relation:
 * maxEndingHere[i] = max(arr[i], maxEndingHere[i-1] + arr[i])
 */
function maxSubArray(nums) {
    let maxSoFar = nums[0];      // Global maximum
    let maxEndingHere = nums[0]; // Local maximum
    
    for (let i = 1; i < nums.length; i++) {
        // Decision: Start new subarray or extend existing
        maxEndingHere = Math.max(nums[i], maxEndingHere + nums[i]);
        
        // Update global maximum
        maxSoFar = Math.max(maxSoFar, maxEndingHere);
    }
    
    return maxSoFar;
}

// Mathematical Proof:
// At each position i, we have two choices:
// 1. Start new subarray from i
// 2. Extend previous subarray
// The optimal solution must make the right choice at each step
```

---

## **Chapter 2: Two Pointers Technique**

### **2.1 Container With Most Water**
**Problem Statement:** Find two lines that form a container holding maximum water.

```javascript
/**
 * Algorithm: Greedy Two Pointers
 * Time Complexity: O(n)
 * Space Complexity: O(1)
 * 
 * Invariant: The optimal solution exists in the search space
 *           we maintain between left and right pointers
 */
function maxArea(height) {
    let left = 0;
    let right = height.length - 1;
    let maxWater = 0;
    
    while (left < right) {
        // Calculate current area
        const width = right - left;
        const minHeight = Math.min(height[left], height[right]);
        const currentWater = width * minHeight;
        
        // Update maximum
        maxWater = Math.max(maxWater, currentWater);
        
        // Greedy choice: Move pointer with smaller height
        if (height[left] < height[right]) {
            left++;
        } else {
            right--;
        }
    }
    
    return maxWater;
}

// Correctness Proof:
// Moving the pointer with larger height cannot give better solution
// because area = min(h[l], h[r]) × width
// Reducing width with same min height decreases area
```

### **2.2 Trapping Rain Water**
**Problem Statement:** Calculate water trapped between elevation bars.

```javascript
/**
 * Algorithm: Two Pointers with Dynamic Programming
 * Time Complexity: O(n)
 * Space Complexity: O(1)
 * 
 * Key Insight: Water at position i = min(maxLeft, maxRight) - height[i]
 */
function trap(height) {
    let left = 0, right = height.length - 1;
    let leftMax = 0, rightMax = 0;
    let water = 0;
    
    while (left < right) {
        if (height[left] < height[right]) {
            // Process left side
            if (height[left] >= leftMax) {
                leftMax = height[left];
            } else {
                // Water can be trapped
                water += leftMax - height[left];
            }
            left++;
        } else {
            // Process right side
            if (height[right] >= rightMax) {
                rightMax = height[right];
            } else {
                // Water can be trapped
                water += rightMax - height[right];
            }
            right--;
        }
    }
    
    return water;
}

// Algorithm Analysis:
// We process from side with smaller height because
// water level is determined by minimum of max heights
```

---

## **Chapter 3: Sliding Window Algorithms**

### **3.1 Longest Substring Without Repeating Characters**
**Problem Statement:** Find length of longest substring without duplicate characters.

```javascript
/**
 * Algorithm: Sliding Window with Hash Set
 * Time Complexity: O(n)
 * Space Complexity: O(min(m, n)) where m is charset size
 * 
 * Window Invariant: No duplicate characters in current window
 */
function lengthOfLongestSubstring(s) {
    const charSet = new Set();
    let maxLength = 0;
    let left = 0;
    
    for (let right = 0; right < s.length; right++) {
        // Shrink window until no duplicate
        while (charSet.has(s[right])) {
            charSet.delete(s[left]);
            left++;
        }
        
        // Expand window
        charSet.add(s[right]);
        
        // Update maximum
        maxLength = Math.max(maxLength, right - left + 1);
    }
    
    return maxLength;
}

// Optimality Proof:
// Each character is visited at most twice (once by right, once by left)
// Therefore, O(2n) = O(n) time complexity
```

### **3.2 Minimum Window Substring**
**Problem Statement:** Find minimum window containing all characters of target string.

```javascript
/**
 * Algorithm: Sliding Window with Frequency Map
 * Time Complexity: O(|S| + |T|)
 * Space Complexity: O(|Σ|) where Σ is the character set
 */
function minWindow(s, t) {
    // Build frequency map for target
    const need = new Map();
    const window = new Map();
    
    for (let char of t) {
        need.set(char, (need.get(char) || 0) + 1);
    }
    
    let left = 0, right = 0;
    let valid = 0;  // Number of unique chars satisfied
    let start = 0, minLen = Infinity;
    
    while (right < s.length) {
        // Expand window
        const c = s[right];
        right++;
        
        if (need.has(c)) {
            window.set(c, (window.get(c) || 0) + 1);
            if (window.get(c) === need.get(c)) {
                valid++;
            }
        }
        
        // Contract window when valid
        while (valid === need.size) {
            // Update minimum window
            if (right - left < minLen) {
                start = left;
                minLen = right - left;
            }
            
            // Shrink window
            const d = s[left];
            left++;
            
            if (need.has(d)) {
                if (window.get(d) === need.get(d)) {
                    valid--;
                }
                window.set(d, window.get(d) - 1);
            }
        }
    }
    
    return minLen === Infinity ? "" : s.substring(start, start + minLen);
}
```

---

## **Chapter 4: Stack-Based Algorithms**

### **4.1 Valid Parentheses**
**Problem Statement:** Determine if parentheses string is valid.

```javascript
/**
 * Algorithm: Stack for Matching Pairs
 * Time Complexity: O(n)
 * Space Complexity: O(n)
 * 
 * Invariant: Stack contains unmatched opening brackets
 */
function isValid(s) {
    const stack = [];
    const pairs = { '(': ')', '{': '}', '[': ']' };
    
    for (let char of s) {
        if (pairs[char]) {
            // Opening bracket: push expected closing
            stack.push(pairs[char]);
        } else {
            // Closing bracket: check if matches
            if (stack.pop() !== char) {
                return false;
            }
        }
    }
    
    return stack.length === 0;
}

// Correctness: LIFO property ensures proper nesting
```

### **4.2 Largest Rectangle in Histogram**
**Problem Statement:** Find largest rectangular area in histogram.

```javascript
/**
 * Algorithm: Monotonic Stack
 * Time Complexity: O(n)
 * Space Complexity: O(n)
 * 
 * Key Insight: For each bar, find nearest smaller bars on both sides
 */
function largestRectangleArea(heights) {
    const stack = [];  // Stores indices
    let maxArea = 0;
    heights.push(0);  // Sentinel to flush stack
    
    for (let i = 0; i < heights.length; i++) {
        // Maintain increasing stack
        while (stack.length && heights[i] < heights[stack[stack.length - 1]]) {
            const h = heights[stack.pop()];
            const w = stack.length ? i - stack[stack.length - 1] - 1 : i;
            maxArea = Math.max(maxArea, h * w);
        }
        stack.push(i);
    }
    
    return maxArea;
}

// Algorithm Analysis:
// Each element pushed and popped exactly once → O(n)
// Stack maintains indices of bars in increasing height order
```

---

## **Chapter 5: Binary Search Algorithms**

### **5.1 Search in Rotated Sorted Array**
**Problem Statement:** Search in sorted array that has been rotated.

```javascript
/**
 * Algorithm: Modified Binary Search
 * Time Complexity: O(log n)
 * Space Complexity: O(1)
 * 
 * Key Insight: At least one half is always sorted
 */
function search(nums, target) {
    let left = 0, right = nums.length - 1;
    
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        
        if (nums[mid] === target) return mid;
        
        // Determine which half is sorted
        if (nums[left] <= nums[mid]) {
            // Left half is sorted
            if (target >= nums[left] && target < nums[mid]) {
                right = mid - 1;  // Target in left half
            } else {
                left = mid + 1;   // Target in right half
            }
        } else {
            // Right half is sorted
            if (target > nums[mid] && target <= nums[right]) {
                left = mid + 1;   // Target in right half
            } else {
                right = mid - 1;  // Target in left half
            }
        }
    }
    
    return -1;
}

// Correctness Proof:
// 1. Array has at most one rotation point
// 2. At least one half is always sorted
// 3. We can determine target location in O(1)
```

### **5.2 Median of Two Sorted Arrays**
**Problem Statement:** Find median of two sorted arrays.

```javascript
/**
 * Algorithm: Binary Search on Partition
 * Time Complexity: O(log(min(m, n)))
 * Space Complexity: O(1)
 * 
 * Mathematical Foundation: Partition arrays such that:
 * 1. Left partition size = Right partition size
 * 2. All left elements ≤ All right elements
 */
function findMedianSortedArrays(nums1, nums2) {
    // Ensure nums1 is smaller
    if (nums1.length > nums2.length) {
        return findMedianSortedArrays(nums2, nums1);
    }
    
    const m = nums1.length, n = nums2.length;
    let low = 0, high = m;
    
    while (low <= high) {
        const partitionX = Math.floor((low + high) / 2);
        const partitionY = Math.floor((m + n + 1) / 2) - partitionX;
        
        const maxLeftX = partitionX === 0 ? -Infinity : nums1[partitionX - 1];
        const minRightX = partitionX === m ? Infinity : nums1[partitionX];
        
        const maxLeftY = partitionY === 0 ? -Infinity : nums2[partitionY - 1];
        const minRightY = partitionY === n ? Infinity : nums2[partitionY];
        
        if (maxLeftX <= minRightY && maxLeftY <= minRightX) {
            // Found correct partition
            if ((m + n) % 2 === 0) {
                return (Math.max(maxLeftX, maxLeftY) + 
                        Math.min(minRightX, minRightY)) / 2;
            } else {
                return Math.max(maxLeftX, maxLeftY);
            }
        } else if (maxLeftX > minRightY) {
            high = partitionX - 1;  // Move left
        } else {
            low = partitionX + 1;   // Move right
        }
    }
}
```

---

## **Chapter 6: Dynamic Programming**

### **6.1 Climbing Stairs (Fibonacci Pattern)**
**Problem Statement:** Count ways to climb n stairs (1 or 2 steps at a time).

```javascript
/**
 * Algorithm: Dynamic Programming (Space Optimized)
 * Time Complexity: O(n)
 * Space Complexity: O(1)
 * 
 * Recurrence: f(n) = f(n-1) + f(n-2)
 * Base Cases: f(1) = 1, f(2) = 2
 */
function climbStairs(n) {
    if (n <= 2) return n;
    
    let prev2 = 1;  // f(n-2)
    let prev1 = 2;  // f(n-1)
    
    for (let i = 3; i <= n; i++) {
        const current = prev1 + prev2;
        prev2 = prev1;
        prev1 = current;
    }
    
    return prev1;
}

// Mathematical Analysis:
// This is the Fibonacci sequence shifted by one
// Closed form: φⁿ/√5 where φ = (1+√5)/2
```

### **6.2 Edit Distance (Levenshtein Distance)**
**Problem Statement:** Find minimum operations to convert string A to string B.

```javascript
/**
 * Algorithm: 2D Dynamic Programming
 * Time Complexity: O(m × n)
 * Space Complexity: O(m × n)
 * 
 * State: dp[i][j] = min operations for word1[0..i-1] → word2[0..j-1]
 */
function minDistance(word1, word2) {
    const m = word1.length, n = word2.length;
    const dp = Array(m + 1).fill().map(() => Array(n + 1).fill(0));
    
    // Base cases
    for (let i = 0; i <= m; i++) dp[i][0] = i;  // Deletions
    for (let j = 0; j <= n; j++) dp[0][j] = j;  // Insertions
    
    // Fill DP table
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (word1[i - 1] === word2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1];  // No operation
            } else {
                dp[i][j] = 1 + Math.min(
                    dp[i - 1][j],      // Delete
                    dp[i][j - 1],      // Insert
                    dp[i - 1][j - 1]   // Replace
                );
            }
        }
    }
    
    return dp[m][n];
}

// Optimal Substructure Proof:
// If we know optimal way to transform s1[0..i-1] to s2[0..j-1],
// we can compute s1[0..i] to s2[0..j] in O(1)
```

### **6.3 Longest Increasing Subsequence**
**Problem Statement:** Find length of longest increasing subsequence.

```javascript
/**
 * Algorithm: DP with Binary Search
 * Time Complexity: O(n log n)
 * Space Complexity: O(n)
 * 
 * Patience Sorting Algorithm
 */
function lengthOfLIS(nums) {
    const tails = [];  // tails[i] = smallest tail of LIS of length i+1
    
    for (let num of nums) {
        let left = 0, right = tails.length;
        
        // Binary search for insertion position
        while (left < right) {
            const mid = Math.floor((left + right) / 2);
            if (tails[mid] < num) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        
        // Update or append
        tails[left] = num;
    }
    
    return tails.length;
}

// Theorem: tails array is always sorted
// Proof by induction on array operations
```

---

## **Chapter 7: Tree Algorithms**

### **7.1 Binary Tree Traversals**

```javascript
/**
 * Iterative Inorder Traversal
 * Time Complexity: O(n)
 * Space Complexity: O(h) where h is height
 */
function inorderTraversal(root) {
    const result = [];
    const stack = [];
    let current = root;
    
    while (current || stack.length) {
        // Go to leftmost node
        while (current) {
            stack.push(current);
            current = current.left;
        }
        
        // Process node
        current = stack.pop();
        result.push(current.val);
        
        // Move to right subtree
        current = current.right;
    }
    
    return result;
}

/**
 * Morris Inorder Traversal (Threaded Binary Tree)
 * Time Complexity: O(n)
 * Space Complexity: O(1)
 */
function morrisInorderTraversal(root) {
    const result = [];
    let current = root;
    
    while (current) {
        if (!current.left) {
            result.push(current.val);
            current = current.right;
        } else {
            // Find inorder predecessor
            let predecessor = current.left;
            while (predecessor.right && predecessor.right !== current) {
                predecessor = predecessor.right;
            }
            
            if (!predecessor.right) {
                // Create thread
                predecessor.right = current;
                current = current.left;
            } else {
                // Remove thread
                predecessor.right = null;
                result.push(current.val);
                current = current.right;
            }
        }
    }
    
    return result;
}
```

### **7.2 Validate Binary Search Tree**

```javascript
/**
 * Algorithm: Bounded DFS
 * Time Complexity: O(n)
 * Space Complexity: O(h)
 * 
 * BST Property: left < node < right for all nodes
 */
function isValidBST(root) {
    function validate(node, min, max) {
        if (!node) return true;
        
        // Check BST property
        if (node.val <= min || node.val >= max) {
            return false;
        }
        
        // Recursively validate subtrees with updated bounds
        return validate(node.left, min, node.val) && 
               validate(node.right, node.val, max);
    }
    
    return validate(root, -Infinity, Infinity);
}

// Proof of Correctness:
// 1. Empty tree is valid BST
// 2. Node value must be within (min, max) bounds
// 3. Bounds are correctly propagated to subtrees
```

---

## **Chapter 8: Graph Algorithms**

### **8.1 Word Search (DFS with Backtracking)**

```javascript
/**
 * Algorithm: DFS with Backtracking
 * Time Complexity: O(M×N×4^L) where L is word length
 * Space Complexity: O(L) for recursion stack
 */
function exist(board, word) {
    const m = board.length, n = board[0].length;
    
    function dfs(i, j, index) {
        // Base case: word found
        if (index === word.length) return true;
        
        // Boundary and character check
        if (i < 0 || i >= m || j < 0 || j >= n || 
            board[i][j] !== word[index]) {
            return false;
        }
        
        // Mark as visited
        const temp = board[i][j];
        board[i][j] = '#';
        
        // Explore 4 directions
        const found = dfs(i+1, j, index+1) || 
                     dfs(i-1, j, index+1) || 
                     dfs(i, j+1, index+1) || 
                     dfs(i, j-1, index+1);
        
        // Backtrack
        board[i][j] = temp;
        
        return found;
    }
    
    // Try starting from each cell
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (dfs(i, j, 0)) return true;
        }
    }
    
    return false;
}
```

---

## **Chapter 9: Backtracking Algorithms**

### **9.1 N-Queens Problem**

```javascript
/**
 * Algorithm: Backtracking with Constraint Propagation
 * Time Complexity: O(N!)
 * Space Complexity: O(N)
 */
function solveNQueens(n) {
    const result = [];
    const board = Array(n).fill().map(() => Array(n).fill('.'));
    
    function isValid(row, col) {
        // Check column
        for (let i = 0; i < row; i++) {
            if (board[i][col] === 'Q') return false;
        }
        
        // Check diagonal (↖)
        for (let i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (board[i][j] === 'Q') return false;
        }
        
        // Check anti-diagonal (↗)
        for (let i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
            if (board[i][j] === 'Q') return false;
        }
        
        return true;
    }
    
    function backtrack(row) {
        // Base case: all queens placed
        if (row === n) {
            result.push(board.map(row => row.join('')));
            return;
        }
        
        // Try placing queen in each column
        for (let col = 0; col < n; col++) {
            if (isValid(row, col)) {
                board[row][col] = 'Q';
                backtrack(row + 1);
                board[row][col] = '.';  // Backtrack
            }
        }
    }
    
    backtrack(0);
    return result;
}

// Optimization: Use bit manipulation for O(1) conflict detection
function solveNQueensOptimized(n) {
    const result = [];
    const board = Array(n).fill().map(() => Array(n).fill('.'));
    
    function backtrack(row, cols, diag1, diag2) {
        if (row === n) {
            result.push(board.map(r => r.join('')));
            return;
        }
        
        for (let col = 0; col < n; col++) {
            const d1 = row - col + n - 1;
            const d2 = row + col;
            
            if ((cols >> col) & 1 || (diag1 >> d1) & 1 || (diag2 >> d2) & 1) {
                continue;
            }
            
            board[row][col] = 'Q';
            backtrack(row + 1, 
                     cols | (1 << col), 
                     diag1 | (1 << d1), 
                     diag2 | (1 << d2));
            board[row][col] = '.';
        }
    }
    
    backtrack(0, 0, 0, 0);
    return result;
}
```

### **9.2 Sudoku Solver**

```javascript
/**
 * Algorithm: Backtracking with Constraint Satisfaction
 * Time Complexity: O(9^m) where m is number of empty cells
 * Space Complexity: O(1)
 */
function solveSudoku(board) {
    function isValid(board, row, col, num) {
        // Check row
        for (let i = 0; i < 9; i++) {
            if (board[row][i] === num) return false;
        }
        
        // Check column
        for (let i = 0; i < 9; i++) {
            if (board[i][col] === num) return false;
        }
        
        // Check 3×3 box
        const boxRow = 3 * Math.floor(row / 3);
        const boxCol = 3 * Math.floor(col / 3);
        for (let i = 0; i < 3; i++) {
            for (let j = 0; j < 3; j++) {
                if (board[boxRow + i][boxCol + j] === num) return false;
            }
        }
        
        return true;
    }
    
    function solve() {
        for (let row = 0; row < 9; row++) {
            for (let col = 0; col < 9; col++) {
                if (board[row][col] === '.') {
                    // Try digits 1-9
                    for (let num = 1; num <= 9; num++) {
                        const numStr = num.toString();
                        if (isValid(board, row, col, numStr)) {
                            board[row][col] = numStr;
                            
                            if (solve()) return true;
                            
                            board[row][col] = '.';  // Backtrack
                        }
                    }
                    return false;  // No valid number found
                }
            }
        }
        return true;  // Board completely filled
    }
    
    solve();
}
```

---

## **Chapter 10: Advanced Techniques**

### **10.1 Monotonic Stack Pattern**

```javascript
/**
 * Next Greater Element
 * Time Complexity: O(n)
 * Space Complexity: O(n)
 */
function nextGreaterElements(nums) {
    const n = nums.length;
    const result = Array(n).fill(-1);
    const stack = [];  // Stores indices
    
    // Process array twice for circular property
    for (let i = 0; i < n * 2; i++) {
        const num = nums[i % n];
        
        // Pop smaller elements
        while (stack.length && nums[stack[stack.length - 1]] < num) {
            result[stack.pop()] = num;
        }
        
        // Only push in first pass
        if (i < n) {
            stack.push(i);
        }
    }
    
    return result;
}
```

### **10.2 Union-Find (Disjoint Set Union)**

```javascript
/**
 * Union-Find with Path Compression and Union by Rank
 * Time Complexity: O(α(n)) ≈ O(1) per operation
 */
class UnionFind {
    constructor(n) {
        this.parent = Array(n).fill().map((_, i) => i);
        this.rank = Array(n).fill(0);
        this.components = n;
    }
    
    find(x) {
        if (this.parent[x] !== x) {
            this.parent[x] = this.find(this.parent[x]);  // Path compression
        }
        return this.parent[x];
    }
    
    union(x, y) {
        const rootX = this.find(x);
        const rootY = this.find(y);
        
        if (rootX === rootY) return false;
        
        // Union by rank
        if (this.rank[rootX] < this.rank[rootY]) {
            this.parent[rootX] = rootY;
        } else if (this.rank[rootX] > this.rank[rootY]) {
            this.parent[rootY] = rootX;
        } else {
            this.parent[rootY] = rootX;
            this.rank[rootX]++;
        }
        
        this.components--;
        return true;
    }
    
    isConnected(x, y) {
        return this.find(x) === this.find(y);
    }
}
```

---

## **Complexity Analysis Summary**

| Pattern | Time Complexity | Space Complexity | When to Use |
|---------|----------------|------------------|-------------|
| Two Pointers | O(n) | O(1) | Sorted arrays, palindromes |
| Sliding Window | O(n) | O(k) | Subarray/substring problems |
| Binary Search | O(log n) | O(1) | Sorted data, optimization |
| BFS/DFS | O(V + E) | O(V) | Graph/tree traversal |
| Dynamic Programming | O(n²) | O(n) | Optimization, counting |
| Backtracking | O(b^d) | O(d) | Constraint satisfaction |
| Monotonic Stack | O(n) | O(n) | Next greater/smaller |
| Union-Find | O(α(n)) | O(n) | Connected components |

---

## **Master Theorem Applications**

For divide-and-conquer recurrences T(n) = aT(n/b) + f(n):

1. **Merge Sort**: T(n) = 2T(n/2) + O(n) → O(n log n)
2. **Binary Search**: T(n) = T(n/2) + O(1) → O(log n)
3. **Karatsuba**: T(n) = 3T(n/2) + O(n) → O(n^1.58)

---

## **Final Notes**

This algorithmic guide demonstrates that mastering ~15 core patterns covers 90% of interview problems. Each pattern has:
- Clear problem indicators
- Standard implementation template
- Time/space complexity analysis
- Correctness proof

The key to algorithmic mastery is recognizing patterns and applying the appropriate technique with proper optimization.