DSA-Algo.js

gistfile1.txt

# 🎯 Complete Coding Interview Patterns - Easy to Follow Version

## 🔥 ALL PATTERNS WITH SIMPLIFIED PROBLEMS & CODE

### 1️⃣ **TWO POINTERS PATTERN**

```javascript
// Time: O(n), Space: O(1)
function twoSumSorted(arr, target) {
    let left = 0, right = arr.length - 1;
    
    while (left < right) {
        const sum = arr[left] + arr[right];
        if (sum === target) return [left, right];
        if (sum < target) left++;
        else right--;
    }
    return [];
}

// Time: O(n²), Space: O(1)
function threeSum(nums) {
    nums.sort((a, b) => a - b);
    const result = [];
    
    for (let i = 0; i < nums.length - 2; i++) {
        if (i > 0 && nums[i] === nums[i-1]) continue;
        
        let left = i + 1, right = nums.length - 1;
        while (left < right) {
            const sum = nums[i] + nums[left] + nums[right];
            if (sum === 0) {
                result.push([nums[i], nums[left], nums[right]]);
                while (nums[left] === nums[left+1]) left++;
                while (nums[right] === nums[right-1]) right--;
                left++; right--;
            } else if (sum < 0) {
                left++;
            } else {
                right--;
            }
        }
    }
    return result;
}

// Time: O(n), Space: O(1)
function isPalindrome(s) {
    let left = 0, right = s.length - 1;
    
    while (left < right) {
        // Skip non-alphanumeric
        while (left < right && !/[a-z0-9]/i.test(s[left])) left++;
        while (left < right && !/[a-z0-9]/i.test(s[right])) right--;
        
        if (s[left].toLowerCase() !== s[right].toLowerCase()) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}

// Time: O(n), Space: O(1)
function containerWithMostWater(heights) {
    let left = 0, right = heights.length - 1;
    let maxWater = 0;
    
    while (left < right) {
        const width = right - left;
        const height = Math.min(heights[left], heights[right]);
        const water = width * height;
        
        maxWater = Math.max(maxWater, water);
        
        // Move pointer with smaller height
        if (heights[left] < heights[right]) {
            left++;
        } else {
            right--;
        }
    }
    return maxWater;
}
```

### 2️⃣ **HASH MAP PATTERN**

```javascript
// Time: O(n), Space: O(n)
function twoSumUnsorted(nums, target) {
    const seen = {};
    
    for (let i = 0; i < nums.length; i++) {
        const complement = target - nums[i];
        
        if (complement in seen) {
            return [seen[complement], i];
        }
        
        seen[nums[i]] = i;
    }
    return [];
}

// Time: O(1) - fixed 9x9 board, Space: O(1)
// Time: O(1) - fixed 9x9 board, Space: O(1)
function isValidSudoku(board) {
    const rows = Array(9).fill().map(() => new Set());
    const cols = Array(9).fill().map(() => new Set());
    // Create 3x3 grid of sets instead of flat array
    const boxes = Array(3).fill().map(() => Array(3).fill().map(() => new Set()));
    
    for (let r = 0; r < 9; r++) {
        for (let c = 0; c < 9; c++) {
            if (board[r][c] === '.') continue;
            
            const num = board[r][c];
            const boxRow = Math.floor(r / 3);
            const boxCol = Math.floor(c / 3);
            
            // Check if number already exists
            if (rows[r].has(num) || 
                cols[c].has(num) || 
                boxes[boxRow][boxCol].has(num)) {
                return false;
            }
            
            // Add to sets
            rows[r].add(num);
            cols[c].add(num);
            boxes[boxRow][boxCol].add(num);
        }
    }
    return true;
}

// Time: O(m×n), Space: O(m+n)
function setZeroMatrix(matrix) {
    const rows = new Set();
    const cols = new Set();
    
    // First pass: mark zeros
    for (let r = 0; r < matrix.length; r++) {
        for (let c = 0; c < matrix[0].length; c++) {
            if (matrix[r][c] === 0) {
                rows.add(r);
                cols.add(c);
            }
        }
    }
    
    // Second pass: set zeros
    for (let r = 0; r < matrix.length; r++) {
        for (let c = 0; c < matrix[0].length; c++) {
            if (rows.has(r) || cols.has(c)) {
                matrix[r][c] = 0;
            }
        }
    }
}
```

### 3️⃣ **LINKED LIST PATTERN**

```javascript
// Time: O(n), Space: O(1)
function reverseLinkedList(head) {
    let prev = null;
    let current = head;
    
    while (current) {
        const next = current.next;
        current.next = prev;
        prev = current;
        current = next;
    }
    
    return prev;
}

// Time: O(n), Space: O(1)
function removeNthFromEnd(head, n) {
    const dummy = new ListNode(0);
    dummy.next = head;
    
    let fast = dummy;
    let slow = dummy;
    
    // Move fast n+1 steps ahead
    for (let i = 0; i <= n; i++) {
        fast = fast.next;
    }
    
    // Move both pointers
    while (fast) {
        fast = fast.next;
        slow = slow.next;
    }
    
    // Skip the nth node
    slow.next = slow.next.next;
    
    return dummy.next;
}

// Time: O(n), Space: O(1)
function findIntersection(headA, headB) {
    if (!headA || !headB) return null;
    
    let pA = headA;
    let pB = headB;
    
    // When one reaches end, switch to other head
    while (pA !== pB) {
        pA = pA ? pA.next : headB;
        pB = pB ? pB.next : headA;
    }
    
    return pA;
}

// Time: O(1) for all operations, Space: O(capacity)
class LRUCache {
    constructor(capacity) {
        this.capacity = capacity;
        this.cache = new Map(); // Maintains insertion order
    }
    
    get(key) {
        if (!this.cache.has(key)) return -1;
        
        // Move to end (most recent)
        const value = this.cache.get(key);
        this.cache.delete(key);
        this.cache.set(key, value);
        return value;
    }
    
    put(key, value) {
        // Remove old entry if exists
        this.cache.delete(key);
        
        // Add new entry
        this.cache.set(key, value);
        
        // Check capacity
        if (this.cache.size > this.capacity) {
            // Remove least recently used (first item)
            const firstKey = this.cache.keys().next().value;
            this.cache.delete(firstKey);
        }
    }
}
```

### 4️⃣ **FAST & SLOW POINTERS PATTERN**

```javascript
// Time: O(n), Space: O(1)
function hasCycle(head) {
    if (!head || !head.next) return false;
    
    let slow = head;
    let fast = head.next;
    
    while (slow !== fast) {
        if (!fast || !fast.next) return false;
        
        slow = slow.next;
        fast = fast.next.next;
    }
    
    return true;
}

// Time: O(n), Space: O(1)
function findMiddle(head) {
    let slow = head;
    let fast = head;
    
    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
    }
    
    return slow;
}

// Time: O(log n), Space: O(1)
function isHappyNumber(n) {
    function getNext(num) {
        let sum = 0;
        while (num > 0) {
            const digit = num % 10;
            sum += digit * digit;
            num = Math.floor(num / 10);
        }
        return sum;
    }
    
    let slow = n;
    let fast = getNext(n);
    
    while (fast !== 1 && slow !== fast) {
        slow = getNext(slow);
        fast = getNext(getNext(fast));
    }
    
    return fast === 1;
}
```

### 5️⃣ **SLIDING WINDOW PATTERN**

```javascript
// Time: O(n), Space: O(1) - alphabet size is constant
function substringAnagrams(s, t) {
    const lenS = s.length;
    const lenT = t.length;
    
    if (lenT > lenS) {
        return 0;
    }
    
    let count = 0;
    const expectedFreqs = new Array(26).fill(0);
    const windowFreqs = new Array(26).fill(0);
    
    // Populate 'expectedFreqs' with the characters in string 't'
    for (const c of t) {
        expectedFreqs[c.charCodeAt(0) - 'a'.charCodeAt(0)]++;
    }
    
    let left = 0;
    let right = 0;
    
    while (right < lenS) {
        // Add the character at the right pointer to 'windowFreqs'
        // before sliding the window
        windowFreqs[s[right].charCodeAt(0) - 'a'.charCodeAt(0)]++;
        
        // If the window has reached the expected fixed length, we
        // advance the left pointer as well as the right pointer to
        // slide the window
        if (right - left + 1 === lenT) {
            if (arraysEqual(windowFreqs, expectedFreqs)) {
                count++;
            }
            
            // Remove the character at the left pointer from
            // 'windowFreqs' before advancing the left pointer
            windowFreqs[s[left].charCodeAt(0) - 'a'.charCodeAt(0)]--;
            left++;
        }
        
        right++;
    }
    
    return count;
}

function arraysEqual(arr1, arr2) {
    return arr1.length === arr2.length && arr1.every((val, i) => val === arr2[i]);
}

// Time: O(n), Space: O(min(n,m)) where m is charset size
function longestSubstringNoRepeat(s) {
    const seen = new Set();
    let left = 0;
    let maxLen = 0;
    
    for (let right = 0; right < s.length; right++) {
        // Shrink window until no repeat
        while (seen.has(s[right])) {
            seen.delete(s[left]);
            left++;
        }
        
        seen.add(s[right]);
        maxLen = Math.max(maxLen, right - left + 1);
    }
    
    return maxLen;
}

// Time: O(n), Space: O(1)
const longestUniformSubstringAfterReplacements = (s, k) => {
    const freqs = {};
    let highestFreq = 0;
    let maxLen = 0;
    let left = 0;
    let right = 0;
    
    while (right < s.length) {
        // Update the frequency of the character at the right pointer
        // and the highest frequency for the current window.
        freqs[s[right]] = (freqs[s[right]] || 0) + 1;
        highestFreq = Math.max(highestFreq, freqs[s[right]]);
        
        // Calculate replacements needed for the current window.
        const numCharsToReplace = (right - left + 1) - highestFreq;
        
        // Slide the window if the number of replacements needed exceeds
        // 'k'. The right pointer always gets advanced, so we just need
        // to advance 'left'.
        if (numCharsToReplace > k) {
            // Remove the character at the left pointer from the hash map
            // before advancing the left pointer.
            freqs[s[left]] -= 1;
            left += 1;
        }
        
        // Since the length of the current window increases or stays the
        // same, assign the length of the current window to 'max_len'.
        maxLen = right - left + 1;
        
        // Expand the window.
        right += 1;
    }
    
    return maxLen;
};

// Example usage:
console.log(longestUniformSubstringAfterReplacements("ABAB", 2)); // 4
console.log(longestUniformSubstringAfterReplacements("AABABBA", 1)); // 4
```

### 6️⃣ **BINARY SEARCH PATTERN** ⭐

```javascript
// Time: O(log n), Space: O(1)
function binarySearch(arr, target) {
    let left = 0;
    let right = arr.length - 1;
    
    while (left <= right) {
        const mid = left + Math.floor((right - left) / 2);
        
        if (arr[mid] === target) return mid;
        if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    
    return -1;
}

// Time: O(log n), Space: O(1)
function findTheInsertionIndex(nums, target) {
    let left = 0;
    let right = nums.length;
    
    while (left < right) {
        const mid = Math.floor((left + right) / 2);
        
        // If the midpoint value is greater than or equal to the target,
        // the lower bound is either at the midpoint, or to its left.
        if (nums[mid] >= target) {
            right = mid;
        }
        // The midpoint value is less than the target, indicating the
        // lower bound is somewhere to the right.
        else {
            left = mid + 1;
        }
    }
    
    return left;
}

// Example usage:
console.log(findTheInsertionIndex([1, 3, 5, 6], 5));  // 2
console.log(findTheInsertionIndex([1, 3, 5, 6], 2));  // 1
console.log(findTheInsertionIndex([1, 3, 5, 6], 7));  // 4
console.log(findTheInsertionIndex([1, 3, 5, 6], 0));  // 0

// Time: O(log n), Space: O(1)
function findFirstAndLast(nums, target) {
    function findBound(isFirst) {
        let left = 0;
        let right = nums.length - 1;
        let bound = -1;
        
        while (left <= right) {
            const mid = left + Math.floor((right - left) / 2);
            
            if (nums[mid] === target) {
                bound = mid;
                if (isFirst) {
                    right = mid - 1; // Keep searching left
                } else {
                    left = mid + 1;  // Keep searching right
                }
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return bound;
    }
    
    return [findBound(true), findBound(false)];
}

// Time: O(n log maxLength), Space: O(1)
function woodCutting(woods, k) {
    function canCut(length) {
        let pieces = 0;
        for (const wood of woods) {
            pieces += Math.floor(wood / length);
        }
        return pieces >= k;
    }
    
    let left = 1;
    let right = Math.max(...woods);
    let result = 0;
    
    while (left <= right) {
        const mid = left + Math.floor((right - left) / 2);
        
        if (canCut(mid)) {
            result = mid;
            left = mid + 1; // Try longer length
        } else {
            right = mid - 1;
        }
    }
    
    return result;
}

// Time: O(log n), Space: O(1)
function searchRotatedArray(nums, target) {
    let left = 0;
    let right = nums.length - 1;
    
    while (left <= right) {
        const mid = left + Math.floor((right - left) / 2);
        
        if (nums[mid] === target) return mid;
        
        // Check which half is sorted
        if (nums[left] <= nums[mid]) {
            // Left half is sorted
            if (nums[left] <= target && target < nums[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        } else {
            // Right half is sorted
            if (nums[mid] < target && target <= nums[right]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    }
    
    return -1;
}
```

### 7️⃣ **STACK PATTERN**

```javascript
// Time: O(n), Space: O(n)
function isValidParentheses(s) {
    const stack = [];
    const pairs = {
        ')': '(',
        '}': '{',
        ']': '['
    };
    
    for (const char of s) {
        if (char in pairs) {
            // Closing bracket
            if (!stack.length || stack.pop() !== pairs[char]) {
                return false;
            }
        } else {
            // Opening bracket
            stack.push(char);
        }
    }
    
    return stack.length === 0;
}

// Time: O(n), Space: O(n)
function nextGreaterElement(nums) {
    const result = new Array(nums.length).fill(-1);
    const stack = []; // Store indices
    
    for (let i = 0; i < nums.length; i++) {
        // Pop all smaller elements
        while (stack.length && nums[stack[stack.length - 1]] < nums[i]) {
            const idx = stack.pop();
            result[idx] = nums[i];
        }
        stack.push(i);
    }
    
    return result;
}

// Time: O(n), Space: O(n)
function evaluateExpression(s) {
    const stack = [];
    let num = 0;
    let sign = '+';
    
    for (let i = 0; i < s.length; i++) {
        const char = s[i];
        
        if (!isNaN(char) && char !== ' ') {
            num = num * 10 + parseInt(char);
        }
        
        if ('+-*/'.includes(char) || i === s.length - 1) {
            if (sign === '+') {
                stack.push(num);
            } else if (sign === '-') {
                stack.push(-num);
            } else if (sign === '*') {
                stack.push(stack.pop() * num);
            } else if (sign === '/') {
                stack.push(Math.trunc(stack.pop() / num));
            }
            
            if (i < s.length - 1) {
                sign = char;
                num = 0;
            }
        }
    }
    
    return stack.reduce((a, b) => a + b, 0);
}
```

### 8️⃣ **HEAP PATTERN**

```javascript
// Time: O(n), Space: O(n) - using bucket sort
function topKFrequent(nums, k) {
    // Count frequencies
    const count = {};
    for (const num of nums) {
        count[num] = (count[num] || 0) + 1;
    }
    
    // Bucket sort by frequency
    const buckets = Array(nums.length + 1).fill().map(() => []);
    for (const [num, freq] of Object.entries(count)) {
        buckets[freq].push(parseInt(num));
    }
    
    // Collect top k
    const result = [];
    for (let i = buckets.length - 1; i >= 0 && result.length < k; i--) {
        result.push(...buckets[i]);
    }
    
    return result.slice(0, k);
}

// Time: O(n log k) where n is total nodes, Space: O(k)
function mergeKSortedLists(lists) {
    if (!lists || lists.length === 0) return null;
    
    // Helper: merge two lists
    function mergeTwoLists(l1, l2) {
        const dummy = new ListNode(0);
        let curr = dummy;
        
        while (l1 && l2) {
            if (l1.val <= l2.val) {
                curr.next = l1;
                l1 = l1.next;
            } else {
                curr.next = l2;
                l2 = l2.next;
            }
            curr = curr.next;
        }
        
        curr.next = l1 || l2;
        return dummy.next;
    }
    
    // Merge lists pair by pair
    while (lists.length > 1) {
        const merged = [];
        
        for (let i = 0; i < lists.length; i += 2) {
            const l1 = lists[i];
            const l2 = i + 1 < lists.length ? lists[i + 1] : null;
            merged.push(mergeTwoLists(l1, l2));
        }
        
        lists = merged;
    }
    
    return lists[0];
}

// Time: O(log n) add, O(1) find median, Space: O(n)
class MedianFinder {
    constructor() {
        this.small = []; // max heap (larger half)
        this.large = []; // min heap (smaller half)
    }
    
    addNum(num) {
        // Add to small heap first
        this.small.push(num);
        this.small.sort((a, b) => b - a);
        
        // Move largest from small to large
        this.large.push(this.small.shift());
        this.large.sort((a, b) => a - b);
        
        // Balance heaps
        if (this.large.length > this.small.length + 1) {
            this.small.push(this.large.shift());
            this.small.sort((a, b) => b - a);
        }
    }
    
    findMedian() {
        if (this.large.length > this.small.length) {
            return this.large[0];
        }
        return (this.large[0] + this.small[0]) / 2;
    }
}
```

### 9️⃣ **INTERVALS PATTERN**

```javascript
// Time: O(n log n), Space: O(n)
function mergeIntervals(intervals) {
    if (!intervals.length) return [];
    
    // Sort by start time
    intervals.sort((a, b) => a[0] - b[0]);
    
    const merged = [intervals[0]];
    
    for (let i = 1; i < intervals.length; i++) {
        const lastMerged = merged[merged.length - 1];
        const current = intervals[i];
        
        if (lastMerged[1] >= current[0]) {
            // Overlap - merge
            lastMerged[1] = Math.max(lastMerged[1], current[1]);
        } else {
            // No overlap - add new
            merged.push(current);
        }
    }
    
    return merged;
}

// Time: O(m + n), Space: O(min(m, n))
function intervalIntersection(firstList, secondList) {
    const result = [];
    let i = 0, j = 0;
    
    while (i < firstList.length && j < secondList.length) {
        // Find intersection
        const start = Math.max(firstList[i][0], secondList[j][0]);
        const end = Math.min(firstList[i][1], secondList[j][1]);
        
        if (start <= end) {
            result.push([start, end]);
        }
        
        // Move pointer with earlier end time
        if (firstList[i][1] < secondList[j][1]) {
            i++;
        } else {
            j++;
        }
    }
    
    return result;
}

// Time: O(n log n), Space: O(n)
function minMeetingRooms(intervals) {
    if (!intervals.length) return 0;
    
    // Separate start and end 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;
    
    for (const start of starts) {
        if (start < ends[endPtr]) {
            // Need new room
            rooms++;
        } else {
            // Reuse room
            endPtr++;
        }
    }
    
    return rooms;
}
```

### 🔟 **PREFIX SUM PATTERN**

```javascript
// Time: O(n) build, O(1) query, Space: O(n)
class RangeSum {
    constructor(nums) {
        this.prefix = [0];
        for (const num of nums) {
            this.prefix.push(this.prefix[this.prefix.length - 1] + num);
        }
    }
    
    sumRange(left, right) {
        return this.prefix[right + 1] - this.prefix[left];
    }
}

// Time: O(n), Space: O(n)
function subarraySum(nums, k) {
    let count = 0;
    let currentSum = 0;
    const prefixSums = {0: 1};
    
    for (const num of nums) {
        currentSum += num;
        
        // Check if (currentSum - k) exists
        if (currentSum - k in prefixSums) {
            count += prefixSums[currentSum - k];
        }
        
        // Add current sum
        prefixSums[currentSum] = (prefixSums[currentSum] || 0) + 1;
    }
    
    return count;
}

// Time: O(n), Space: O(1) - output array doesn't count
function productExceptSelf(nums) {
    const n = nums.length;
    const result = new Array(n).fill(1);
    
    // Left products
    for (let i = 1; i < n; i++) {
        result[i] = result[i - 1] * nums[i - 1];
    }
    
    // Right products
    let rightProduct = 1;
    for (let i = n - 1; i >= 0; i--) {
        result[i] *= rightProduct;
        rightProduct *= nums[i];
    }
    
    return result;
}
```

### 1️⃣1️⃣ **TREE PATTERNS**

```javascript
// Time: O(n), Space: O(h) where h is height
function invertBinaryTree(root) {
    if (!root) return null;
    
    // Swap children
    [root.left, root.right] = [root.right, root.left];
    
    // Recursively invert subtrees
    invertBinaryTree(root.left);
    invertBinaryTree(root.right);
    
    return root;
}

// Time: O(n), Space: O(h)
function isBalancedTree(root) {
    function checkHeight(node) {
        if (!node) return 0;
        
        const leftHeight = checkHeight(node.left);
        if (leftHeight === -1) return -1;
        
        const rightHeight = checkHeight(node.right);
        if (rightHeight === -1) return -1;
        
        // Check if balanced
        if (Math.abs(leftHeight - rightHeight) > 1) {
            return -1;
        }
        
        return Math.max(leftHeight, rightHeight) + 1;
    }
    
    return checkHeight(root) !== -1;
}

// Time: O(n), Space: O(w) where w is max width
function rightSideView(root) {
    if (!root) return [];
    
    const result = [];
    const queue = [root];
    
    while (queue.length) {
        const levelSize = queue.length;
        
        for (let i = 0; i < levelSize; i++) {
            const node = queue.shift();
            
            // Add rightmost node of each level
            if (i === levelSize - 1) {
                result.push(node.val);
            }
            
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
    }
    
    return result;
}

// Time: O(n), Space: O(w)
function maxWidthOfBinaryTree(root) {
    if (!root) return 0;
    
    let maxWidth = 0;
    const queue = [[root, 0]]; // [node, position]
    
    while (queue.length) {
        const levelSize = queue.length;
        const firstPos = queue[0][1];
        const lastPos = queue[levelSize - 1][1];
        
        maxWidth = Math.max(maxWidth, lastPos - firstPos + 1);
        
        for (let i = 0; i < levelSize; i++) {
            const [node, pos] = queue.shift();
            const normalizedPos = pos - firstPos; // Prevent overflow
            
            if (node.left) {
                queue.push([node.left, 2 * normalizedPos]);
            }
            if (node.right) {
                queue.push([node.right, 2 * normalizedPos + 1]);
            }
        }
    }
    
    return maxWidth;
}

// Time: O(n), Space: O(h)
function isValidBST(root) {
    function validate(node, min, max) {
        if (!node) return true;
        
        if (node.val <= min || node.val >= max) {
            return false;
        }
        
        return validate(node.left, min, node.val) && 
               validate(node.right, node.val, max);
    }
    
    return validate(root, -Infinity, Infinity);
}

// Time: O(n), Space: O(h)
function lowestCommonAncestor(root, p, q) {
    if (!root || root === p || root === q) {
        return root;
    }
    
    const left = lowestCommonAncestor(root.left, p, q);
    const right = lowestCommonAncestor(root.right, p, q);
    
    if (left && right) {
        return root; // Both found in different subtrees
    }
    
    return left || right;
}

// Time: O(n), Space: O(n)
function buildTreeFromTraversals(preorder, inorder) {
    if (!preorder.length || !inorder.length) return null;
    
    // First element of preorder is root
    const root = new TreeNode(preorder[0]);
    const mid = inorder.indexOf(preorder[0]);
    
    // Build left and right subtrees
    root.left = buildTreeFromTraversals(
        preorder.slice(1, mid + 1),
        inorder.slice(0, mid)
    );
    root.right = buildTreeFromTraversals(
        preorder.slice(mid + 1),
        inorder.slice(mid + 1)
    );
    
    return root;
}

// Time: O(n), Space: O(h)
function maxPathSum(root) {
    let maxSum = -Infinity;
    
    function maxGain(node) {
        if (!node) return 0;
        
        // Get max sum going through left and right child
        const leftGain = Math.max(maxGain(node.left), 0);
        const rightGain = Math.max(maxGain(node.right), 0);
        
        // Max path through current node
        const currentMax = node.val + leftGain + rightGain;
        maxSum = Math.max(maxSum, currentMax);
        
        // Return max gain if we continue path through current node
        return node.val + Math.max(leftGain, rightGain);
    }
    
    maxGain(root);
    return maxSum;
}
```

### 1️⃣2️⃣ **TRIE PATTERN**

```javascript
// Time: O(m) for all operations where m is word length
class Trie {
    constructor() {
        this.root = {};
    }
    
    insert(word) {
        let node = this.root;
        for (const char of word) {
            if (!node[char]) {
                node[char] = {};
            }
            node = node[char];
        }
        node.isEnd = true;
    }
    
    search(word) {
        let node = this.root;
        for (const char of word) {
            if (!node[char]) return false;
            node = node[char];
        }
        return node.isEnd === true;
    }
    
    startsWith(prefix) {
        let node = this.root;
        for (const char of prefix) {
            if (!node[char]) return false;
            node = node[char];
        }
        return true;
    }
}

// Time: O(m) for add, O(m×26^k) for search where k is number of dots
class WordDictionary {
    constructor() {
        this.root = {};
    }
    
    addWord(word) {
        let node = this.root;
        for (const char of word) {
            if (!node[char]) {
                node[char] = {};
            }
            node = node[char];
        }
        node.isEnd = true;
    }
    
    search(word) {
        function dfs(node, index) {
            if (index === word.length) {
                return node.isEnd === true;
            }
            
            const char = word[index];
            
            if (char === '.') {
                // Try all possible characters
                for (const key in node) {
                    if (key !== 'isEnd' && dfs(node[key], index + 1)) {
                        return true;
                    }
                }
                return false;
            } else {
                if (!node[char]) return false;
                return dfs(node[char], index + 1);
            }
        }
        
        return dfs(this.root, 0);
    }
}

// Time: O(m×n×4^L) where L is max word length, Space: O(total chars)
function wordSearchII(board, words) {
    // Build trie from words
    const root = {};
    for (const word of words) {
        let node = root;
        for (const char of word) {
            if (!node[char]) {
                node[char] = {};
            }
            node = node[char];
        }
        node.word = word;
    }
    
    const result = [];
    const m = board.length, n = board[0].length;
    
    function dfs(i, j, node) {
        const char = board[i][j];
        
        if (!node[char]) return;
        
        node = node[char];
        
        if (node.word) {
            result.push(node.word);
            node.word = null; // Avoid duplicates
        }
        
        board[i][j] = '#'; // Mark visited
        
        // Try all 4 directions
        const dirs = [[0,1], [1,0], [0,-1], [-1,0]];
        for (const [di, dj] of dirs) {
            const ni = i + di, nj = j + dj;
            if (ni >= 0 && ni < m && nj >= 0 && nj < n && board[ni][nj] !== '#') {
                dfs(ni, nj, node);
            }
        }
        
        board[i][j] = char; // Restore
    }
    
    // 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;
}
```

### 1️⃣3️⃣ **GRAPH PATTERNS**

```javascript
// Time: O(V + E), Space: O(V)
function cloneGraph(node) {
    if (!node) return null;
    
    const cloned = new Map();
    
    function dfs(node) {
        if (cloned.has(node)) {
            return cloned.get(node);
        }
        
        const copy = new Node(node.val);
        cloned.set(node, copy);
        
        for (const neighbor of node.neighbors) {
            copy.neighbors.push(dfs(neighbor));
        }
        
        return copy;
    }
    
    return dfs(node);
}

// Time: O(m×n), Space: O(m×n)
function numberOfIslands(grid) {
    if (!grid || !grid.length) return 0;
    
    const m = grid.length, n = grid[0].length;
    let islands = 0;
    
    function dfs(i, j) {
        // Check bounds and if water
        if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] === '0') {
            return;
        }
        
        grid[i][j] = '0'; // Mark as visited
        
        // Visit all 4 directions
        dfs(i + 1, j);
        dfs(i - 1, j);
        dfs(i, j + 1);
        dfs(i, j - 1);
    }
    
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (grid[i][j] === '1') {
                islands++;
                dfs(i, j);
            }
        }
    }
    
    return islands;
}

// Time: O(m×n), Space: O(m×n)
function rottingOranges(grid) {
    const m = grid.length, n = grid[0].length;
    const queue = [];
    let fresh = 0;
    
    // Find all rotten oranges and count fresh
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (grid[i][j] === 2) {
                queue.push([i, j]);
            } else if (grid[i][j] === 1) {
                fresh++;
            }
        }
    }
    
    if (fresh === 0) return 0;
    
    let minutes = 0;
    const dirs = [[0,1], [1,0], [0,-1], [-1,0]];
    
    while (queue.length && fresh > 0) {
        minutes++;
        const size = queue.length;
        
        for (let i = 0; i < size; i++) {
            const [x, y] = queue.shift();
            
            for (const [dx, dy] of dirs) {
                const nx = x + dx, ny = y + dy;
                
                if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] === 1) {
                    grid[nx][ny] = 2;
                    fresh--;
                    queue.push([nx, ny]);
                }
            }
        }
    }
    
    return fresh === 0 ? minutes : -1;
}

// Time: O(V + E), Space: O(V)
function isBipartite(graph) {
    const n = graph.length;
    const colors = new Array(n).fill(-1);
    
    function dfs(node, color) {
        colors[node] = color;
        
        for (const neighbor of graph[node]) {
            if (colors[neighbor] === color) {
                return false; // Same color - not bipartite
            }
            
            if (colors[neighbor] === -1) {
                if (!dfs(neighbor, 1 - color)) {
                    return false;
                }
            }
        }
        
        return true;
    }
    
    for (let i = 0; i < n; i++) {
        if (colors[i] === -1) {
            if (!dfs(i, 0)) {
                return false;
            }
        }
    }
    
    return true;
}

// Time: O(m×n), Space: O(m×n)
function longestIncreasingPath(matrix) {
    if (!matrix || !matrix.length) return 0;
    
    const m = matrix.length, n = matrix[0].length;
    const cache = {};
    
    function dfs(i, j) {
        const key = `${i},${j}`;
        if (key in cache) return cache[key];
        
        let maxPath = 1;
        const dirs = [[0,1], [1,0], [0,-1], [-1,0]];
        
        for (const [di, dj] of dirs) {
            const ni = i + di, nj = j + dj;
            
            if (ni >= 0 && ni < m && nj >= 0 && nj < n && 
                matrix[ni][nj] > matrix[i][j]) {
                maxPath = Math.max(maxPath, 1 + dfs(ni, nj));
            }
        }
        
        cache[key] = maxPath;
        return maxPath;
    }
    
    let result = 0;
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            result = Math.max(result, dfs(i, j));
        }
    }
    
    return result;
}

// Time: O(M²×N) where M is word length, N is number of words
function wordLadder(beginWord, endWord, wordList) {
    if (!wordList.includes(endWord)) return 0;
    
    const wordSet = new Set(wordList);
    const queue = [[beginWord, 1]];
    
    while (queue.length) {
        const [word, level] = queue.shift();
        
        if (word === endWord) return level;
        
        // Try changing each character
        for (let i = 0; i < word.length; i++) {
            for (let j = 0; j < 26; j++) {
                const char = String.fromCharCode(97 + j);
                const newWord = word.slice(0, i) + char + word.slice(i + 1);
                
                if (wordSet.has(newWord)) {
                    wordSet.delete(newWord);
                    queue.push([newWord, level + 1]);
                }
            }
        }
    }
    
    return 0;
}

// Time: O(E×α(V)) ≈ O(E), Space: O(V)
class UnionFind {
    constructor(n) {
        this.parent = Array.from({length: n}, (_, i) => i);
        this.rank = new Array(n).fill(0);
    }
    
    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 px = this.find(x);
        const py = this.find(y);
        
        if (px === py) return false;
        
        // Union by rank
        if (this.rank[px] < this.rank[py]) {
            this.parent[px] = py;
        } else if (this.rank[px] > this.rank[py]) {
            this.parent[py] = px;
        } else {
            this.parent[py] = px;
            this.rank[px]++;
        }
        
        return true;
    }
}

function countComponents(n, edges) {
    const uf = new UnionFind(n);
    let components = n;
    
    for (const [u, v] of edges) {
        if (uf.union(u, v)) {
            components--;
        }
    }
    
    return components;
}

// Time: O(V + E), Space: O(V + E)
function courseSchedule(numCourses, prerequisites) {
    const graph = Array(numCourses).fill().map(() => []);
    
    // Build adjacency list
    for (const [course, prereq] of prerequisites) {
        graph[prereq].push(course);
    }
    
    // 0: unvisited, 1: visiting, 2: visited
    const states = new Array(numCourses).fill(0);
    
    function hasCycle(course) {
        if (states[course] === 1) return true;  // Back edge - cycle
        if (states[course] === 2) return false; // Already processed
        
        states[course] = 1; // Mark as visiting
        
        for (const next of graph[course]) {
            if (hasCycle(next)) return true;
        }
        
        states[course] = 2; // Mark as visited
        return false;
    }
    
    for (let i = 0; i < numCourses; i++) {
        if (hasCycle(i)) return false;
    }
    
    return true;
}
```

### 1️⃣4️⃣ **BACKTRACKING PATTERN**

```javascript
// Time: O(n!), Space: O(n)
function permutations(nums) {
    const result = [];
    
    function backtrack(start = 0) {
        if (start === nums.length) {
            result.push([...nums]);
            return;
        }
        
        for (let i = start; i < nums.length; i++) {
            // Swap
            [nums[start], nums[i]] = [nums[i], nums[start]];
            
            backtrack(start + 1);
            
            // Restore
            [nums[start], nums[i]] = [nums[i], nums[start]];
        }
    }
    
    backtrack();
    return result;
}

// Time: O(2^n), Space: O(n)
function subsets(nums) {
    const result = [];
    
    function backtrack(start, path) {
        result.push([...path]);
        
        for (let i = start; i < nums.length; i++) {
            path.push(nums[i]);
            backtrack(i + 1, path);
            path.pop();
        }
    }
    
    backtrack(0, []);
    return result;
}

// Time: O(n!), Space: O(n²)
function nQueens(n) {
    const result = [];
    const board = Array(n).fill().map(() => Array(n).fill('.'));
    
    function isSafe(row, col) {
        // Check column
        for (let i = 0; i < row; i++) {
            if (board[i][col] === 'Q') return false;
        }
        
        // Check upper left diagonal
        for (let i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (board[i][j] === 'Q') return false;
        }
        
        // Check upper right 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) {
        if (row === n) {
            result.push(board.map(r => r.join('')));
            return;
        }
        
        for (let col = 0; col < n; col++) {
            if (isSafe(row, col)) {
                board[row][col] = 'Q';
                backtrack(row + 1);
                board[row][col] = '.';
            }
        }
    }
    
    backtrack(0);
    return result;
}
```

### 1️⃣5️⃣ **DYNAMIC PROGRAMMING PATTERN**

```javascript
// Time: O(n), Space: O(1)
function climbingStairs(n) {
    if (n <= 2) return n;
    
    let prev2 = 1;
    let prev1 = 2;
    
    for (let i = 3; i <= n; i++) {
        const current = prev1 + prev2;
        prev2 = prev1;
        prev1 = current;
    }
    
    return prev1;
}

// Time: O(amount × coins), Space: O(amount)
function coinChange(coins, amount) {
    const dp = new Array(amount + 1).fill(Infinity);
    dp[0] = 0;
    
    for (let i = 1; i <= amount; i++) {
        for (const coin of coins) {
            if (coin <= i) {
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }
    }
    
    return dp[amount] === Infinity ? -1 : dp[amount];
}

// Time: O(m×n), Space: O(m×n)
function uniquePaths(m, n) {
    const dp = Array(m).fill().map(() => Array(n).fill(1));
    
    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
            dp[i][j] = dp[i-1][j] + dp[i][j-1];
        }
    }
    
    return dp[m-1][n-1];
}

// Time: O(n), Space: O(1)
function houseRobber(nums) {
    if (!nums.length) return 0;
    if (nums.length === 1) return nums[0];
    
    let prev2 = nums[0];
    let prev1 = Math.max(nums[0], nums[1]);
    
    for (let i = 2; i < nums.length; i++) {
        const current = Math.max(prev1, prev2 + nums[i]);
        prev2 = prev1;
        prev1 = current;
    }
    
    return prev1;
}

// Time: O(m×n), Space: O(m×n)
function longestCommonSubsequence(text1, text2) {
    const m = text1.length, n = text2.length;
    const dp = Array(m + 1).fill().map(() => Array(n + 1).fill(0));
    
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (text1[i-1] === text2[j-1]) {
                dp[i][j] = dp[i-1][j-1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
            }
        }
    }
    
    return dp[m][n];
}

// Time: O(n²), Space: O(1)
function longestPalindrome(s) {
    function expandAroundCenter(left, right) {
        while (left >= 0 && right < s.length && s[left] === s[right]) {
            left--;
            right++;
        }
        return right - left - 1;
    }
    
    let start = 0, maxLen = 0;
    
    for (let i = 0; i < s.length; i++) {
        const len1 = expandAroundCenter(i, i);     // Odd length
        const len2 = expandAroundCenter(i, i + 1); // Even length
        const len = Math.max(len1, len2);
        
        if (len > maxLen) {
            maxLen = len;
            start = i - Math.floor((len - 1) / 2);
        }
    }
    
    return s.substring(start, start + maxLen);
}

// Time: O(n), Space: O(1)
function maxSubarray(nums) {
    let maxCurrent = nums[0];
    let maxGlobal = nums[0];
    
    for (let i = 1; i < nums.length; i++) {
        maxCurrent = Math.max(nums[i], maxCurrent + nums[i]);
        maxGlobal = Math.max(maxGlobal, maxCurrent);
    }
    
    return maxGlobal;
}

// Time: O(n×W), Space: O(W)
function knapsack01(weights, values, capacity) {
    const n = weights.length;
    const dp = new Array(capacity + 1).fill(0);
    
    for (let i = 0; i < n; i++) {
        // Traverse backwards for 0/1 knapsack
        for (let w = capacity; w >= weights[i]; w--) {
            dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
        }
    }
    
    return dp[capacity];
}
```

### 1️⃣6️⃣ **GREEDY PATTERN**

```javascript
// Time: O(n), Space: O(1)
function canJump(nums) {
    let maxReach = 0;
    
    for (let i = 0; i < nums.length; i++) {
        if (i > maxReach) return false;
        maxReach = Math.max(maxReach, i + nums[i]);
    }
    
    return true;
}

// Time: O(n), Space: O(1)
function gasStation(gas, cost) {
    let totalGas = 0, totalCost = 0;
    let tank = 0, start = 0;
    
    for (let i = 0; i < gas.length; i++) {
        totalGas += gas[i];
        totalCost += cost[i];
        tank += gas[i] - cost[i];
        
        if (tank < 0) {
            start = i + 1;
            tank = 0;
        }
    }
    
    return totalGas >= totalCost ? start : -1;
}

// Time: O(n), Space: O(n)
function candyDistribution(ratings) {
    const n = ratings.length;
    const candies = new Array(n).fill(1);
    
    // Left to right pass
    for (let i = 1; i < n; i++) {
        if (ratings[i] > ratings[i-1]) {
            candies[i] = candies[i-1] + 1;
        }
    }
    
    // Right to left pass
    for (let i = n - 2; i >= 0; i--) {
        if (ratings[i] > ratings[i+1]) {
            candies[i] = Math.max(candies[i], candies[i+1] + 1);
        }
    }
    
    return candies.reduce((a, b) => a + b, 0);
}
```

### 1️⃣7️⃣ **SORTING PATTERNS**

```javascript
// Time: O(n log n), Space: O(log n)
function sortLinkedList(head) {
    if (!head || !head.next) return head;
    
    // Find middle using slow-fast pointers
    let slow = head, fast = head, prev = null;
    while (fast && fast.next) {
        prev = slow;
        slow = slow.next;
        fast = fast.next.next;
    }
    prev.next = null;
    
    // Recursively sort both halves
    const left = sortLinkedList(head);
    const right = sortLinkedList(slow);
    
    // Merge sorted halves
    function merge(l1, l2) {
        const dummy = new ListNode(0);
        let curr = dummy;
        
        while (l1 && l2) {
            if (l1.val < l2.val) {
                curr.next = l1;
                l1 = l1.next;
            } else {
                curr.next = l2;
                l2 = l2.next;
            }
            curr = curr.next;
        }
        
        curr.next = l1 || l2;
        return dummy.next;
    }
    
    return merge(left, right);
}

// Time: O(n log n) average, Space: O(log n)
function quickSort(nums) {
    function sort(left, right) {
        if (left >= right) return;
        
        // Random pivot
        const pivotIdx = left + Math.floor(Math.random() * (right - left + 1));
        [nums[pivotIdx], nums[right]] = [nums[right], nums[pivotIdx]];
        
        const pivot = nums[right];
        let i = left;
        
        for (let j = left; j < right; j++) {
            if (nums[j] < pivot) {
                [nums[i], nums[j]] = [nums[j], nums[i]];
                i++;
            }
        }
        
        [nums[i], nums[right]] = [nums[right], nums[i]];
        
        sort(left, i - 1);
        sort(i + 1, right);
    }
    
    sort(0, nums.length - 1);
    return nums;
}

// Time: O(n) average, Space: O(1)
function findKthLargest(nums, k) {
    k = nums.length - k; // Convert to kth smallest
    
    function quickSelect(left, right) {
        // Random pivot
        const pivotIdx = left + Math.floor(Math.random() * (right - left + 1));
        [nums[pivotIdx], nums[right]] = [nums[right], nums[pivotIdx]];
        
        const pivot = nums[right];
        let i = left;
        
        for (let j = left; j < right; j++) {
            if (nums[j] < pivot) {
                [nums[i], nums[j]] = [nums[j], nums[i]];
                i++;
            }
        }
        
        [nums[i], nums[right]] = [nums[right], nums[i]];
        
        if (i === k) return nums[i];
        else if (i < k) return quickSelect(i + 1, right);
        else return quickSelect(left, i - 1);
    }
    
    return quickSelect(0, nums.length - 1);
}
```

### 1️⃣8️⃣ **BIT MANIPULATION PATTERN**

```javascript
// Time: O(k) where k is number of 1s, Space: O(1)
function hammingWeight(n) {
    let count = 0;
    
    while (n !== 0) {
        n &= n - 1; // Remove rightmost 1
        count++;
    }
    
    return count;
}

// Time: O(n), Space: O(1)
function singleNumber(nums) {
    let result = 0;
    
    for (const num of nums) {
        result ^= num; // XOR cancels duplicates
    }
    
    return result;
}

// Time: O(1), Space: O(1)
function swapEvenOddBits(n) {
    const EVEN_MASK = 0xAAAAAAAA; // 1010...
    const ODD_MASK = 0x55555555;  // 0101...
    
    const evenBits = n & EVEN_MASK;
    const oddBits = n & ODD_MASK;
    
    return (evenBits >>> 1) | (oddBits << 1);
}
```

### 1️⃣9️⃣ **MATH & GEOMETRY PATTERN**

```javascript
// Time: O(m×n), Space: O(1) excluding output
function spiralMatrix(matrix) {
    if (!matrix.length) return [];
    
    const result = [];
    let top = 0, bottom = matrix.length - 1;
    let left = 0, right = matrix[0].length - 1;
    
    while (top <= bottom && left <= right) {
        // Move right
        for (let j = left; j <= right; j++) {
            result.push(matrix[top][j]);
        }
        top++;
        
        // Move down
        for (let i = top; i <= bottom; i++) {
            result.push(matrix[i][right]);
        }
        right--;
        
        // Move left (if row exists)
        if (top <= bottom) {
            for (let j = right; j >= left; j--) {
                result.push(matrix[bottom][j]);
            }
            bottom--;
        }
        
        // Move up (if column exists)
        if (left <= right) {
            for (let i = bottom; i >= top; i--) {
                result.push(matrix[i][left]);
            }
            left++;
        }
    }
    
    return result;
}

// Time: O(log n), Space: O(1)
function reverseInteger(x) {
    const INT_MAX = 2147483647;
    const INT_MIN = -2147483648;
    
    let result = 0;
    const sign = x < 0 ? -1 : 1;
    x = Math.abs(x);
    
    while (x !== 0) {
        const digit = x % 10;
        x = Math.floor(x / 10);
        
        // Check overflow
        if (result > Math.floor(INT_MAX / 10) || 
            (result === Math.floor(INT_MAX / 10) && digit > 7)) {
            return 0;
        }
        
        result = result * 10 + digit;
    }
    
    return sign * result;
}

// Time: O(n²), Space: O(n)
function maxPointsOnLine(points) {
    if (points.length <= 2) return points.length;
    
    function gcd(a, b) {
        return b === 0 ? a : gcd(b, a % b);
    }
    
    let maxPoints = 0;
    
    for (let i = 0; i < points.length; i++) {
        const slopes = {};
        let duplicate = 1;
        
        for (let j = i + 1; j < points.length; j++) {
            let dx = points[j][0] - points[i][0];
            let dy = points[j][1] - points[i][1];
            
            if (dx === 0 && dy === 0) {
                duplicate++;
            } else {
                const g = gcd(Math.abs(dx), Math.abs(dy));
                dx /= g;
                dy /= g;
                
                const slope = `${dx},${dy}`;
                slopes[slope] = (slopes[slope] || 0) + 1;
            }
        }
        
        let currentMax = duplicate;
        for (const count of Object.values(slopes)) {
            currentMax = Math.max(currentMax, count + duplicate);
        }
        
        maxPoints = Math.max(maxPoints, currentMax);
    }
    
    return maxPoints;
}
```

---

## 🎯 COMPLETE PROBLEM INDEX

| # | Problem | Pattern | Time | Key Trick |
|---|---------|---------|------|-----------|
| 1 | Two Sum Sorted | Two Pointers | O(n) | Move based on sum |
| 2 | Three Sum | Two Pointers | O(n²) | Fix one, two pointers |
| 3 | Valid Palindrome | Two Pointers | O(n) | Skip non-alphanumeric |
| 4 | Container Water | Two Pointers | O(n) | Move shorter height |
| 5 | Two Sum Unsorted | HashMap | O(n) | Store complement |
| # | Problem | Pattern | Time | Key Trick |
|---|---------|---------|------|-----------|
| 6 | Valid Sudoku | HashSet | O(1) | Track row/col/box |
| 7 | Zero Matrix | HashSet | O(mn) | Mark then update |
| 8 | Reverse Linked List | Linked List | O(n) | Track prev/curr/next |
| 9 | Remove Nth From End | Linked List | O(n) | Two pointers with gap |
| 10 | Linked List Intersection | Linked List | O(n) | Switch heads at end |
| 11 | LRU Cache | Design | O(1) | Map + insertion order |
| 12 | Has Cycle | Fast/Slow | O(n) | Floyd's algorithm |
| 13 | Find Middle | Fast/Slow | O(n) | Fast moves 2x |
| 14 | Happy Number | Fast/Slow | O(log n) | Cycle detection |
| 15 | Find Anagrams | Sliding Window | O(n) | Fixed window |
| 16 | Longest No Repeat | Sliding Window | O(n) | Variable window |
| 17 | Longest Repeating K | Sliding Window | O(n) | Track max frequency |
| 18 | Binary Search | Binary Search | **O(log n)** | Divide search space |
| 19 | Search Insert | Binary Search | **O(log n)** | Return left pointer |
| 20 | First and Last | Binary Search | **O(log n)** | Continue after found |
| 21 | Wood Cutting | Binary Search | **O(n log m)** | Search answer space |
| 22 | Search Rotated | Binary Search | **O(log n)** | Find sorted half |
| 23 | Valid Parentheses | Stack | O(n) | Match pairs |
| 24 | Next Greater | Stack | O(n) | Monotonic stack |
| 25 | Evaluate Expression | Stack | O(n) | Process operators |
| 26 | Top K Frequent | Heap | O(n) | Bucket sort |
| 27 | Merge K Lists | Heap | **O(n log k)** | K-way merge |
| 28 | Median Stream | Two Heaps | **O(log n)** | Balance heaps |
| 29 | Merge Intervals | Intervals | **O(n log n)** | Sort by start |
| 30 | Interval Intersection | Intervals | O(m+n) | Two pointers |
| 31 | Meeting Rooms | Intervals | **O(n log n)** | Track overlaps |
| 32 | Range Sum | Prefix Sum | O(1) query | Precompute sums |
| 33 | Subarray Sum K | Prefix Sum | O(n) | sum - k exists? |
| 34 | Product Except Self | Prefix Sum | O(n) | Left and right pass |
| 35 | Invert Tree | Tree DFS | O(n) | Swap children |
| 36 | Is Balanced | Tree DFS | O(n) | Return height or -1 |
| 37 | Right Side View | Tree BFS | O(n) | Last of each level |
| 38 | Max Width | Tree BFS | O(n) | Track positions |
| 39 | Valid BST | Tree DFS | O(n) | Min/max bounds |
| 40 | LCA | Tree DFS | O(n) | Both found = root |
| 41 | Build Tree | Tree DFS | O(n) | Pre/in order split |
| 42 | Max Path Sum | Tree DFS | O(n) | Track global max |
| 43 | Implement Trie | Trie | O(m) | Character nodes |
| 44 | Word Dictionary | Trie | O(m×26^k) | DFS for wildcard |
| 45 | Word Search II | Trie+DFS | O(mn×4^L) | Prune with trie |
| 46 | Clone Graph | Graph DFS | O(V+E) | HashMap cloned |
| 47 | Number Islands | Graph DFS | O(mn) | Mark visited |
| 48 | Rotting Oranges | Graph BFS | O(mn) | Multi-source BFS |
| 49 | Is Bipartite | Graph DFS | O(V+E) | Color alternating |
| 50 | Longest Inc Path | Graph DFS | O(mn) | Memoization |
| 51 | Word Ladder | Graph BFS | O(M²N) | Implicit graph |
| 52 | Union Find | Graph | O(α(n)) | Path compression |
| 53 | Course Schedule | Graph | O(V+E) | Detect cycle |
| 54 | Permutations | Backtrack | O(n!) | Swap approach |
| 55 | Subsets | Backtrack | O(2^n) | Include/exclude |
| 56 | N-Queens | Backtrack | O(n!) | Check safe |
| 57 | Climbing Stairs | DP | O(n) | Fibonacci |
| 58 | Coin Change | DP | O(n×m) | Min coins |
| 59 | Unique Paths | DP | O(mn) | Grid paths |
| 60 | House Robber | DP | O(n) | Max no adjacent |
| 61 | LCS | DP | O(mn) | 2D table |
| 62 | Longest Palindrome | DP | O(n²) | Expand center |
| 63 | Max Subarray | DP | O(n) | Kadane's |
| 64 | 0/1 Knapsack | DP | O(nW) | Backward traverse |
| 65 | Jump Game | Greedy | O(n) | Track max reach |
| 66 | Gas Station | Greedy | O(n) | Track deficit |
| 67 | Candy | Greedy | O(n) | Two passes |
| 68 | Sort List | Sort | **O(n log n)** | Merge sort |
| 69 | Quick Sort | Sort | **O(n log n)** | Random pivot |
| 70 | Kth Largest | Sort | O(n) avg | QuickSelect |
| 71 | Hamming Weight | Bit | O(k) | n & (n-1) trick |
| 72 | Single Number | Bit | O(n) | XOR property |
| 73 | Swap Bits | Bit | O(1) | Mask and shift |
| 74 | Spiral Matrix | Math | O(mn) | Layer by layer |
| 75 | Reverse Integer | Math | O(log n) | Check overflow |
| 76 | Max Points Line | Math | O(n²) | GCD for slope |

---

## 🚀 QUICK COMPLEXITY LOOKUP

### **By Time Complexity:**

**O(1) - Constant:**
- HashMap/Set operations
- Stack push/pop
- Math calculations
- Bit operations

**O(log n) - Logarithmic:** ⭐
- Binary Search
- Balanced Tree operations
- Heap push/pop
- Binary Search on answer

**O(n) - Linear:**
- Single pass array
- Two pointers
- Sliding window
- Tree/Graph traversal (V+E)
- Kadane's algorithm

**O(n log n) - Linearithmic:**
- Efficient sorting
- Merge sort
- Heap sort
- Divide & conquer

**O(n²) - Quadratic:**
- Nested loops
- 2D DP
- All pairs
- Bubble sort

**O(2^n) - Exponential:**
- All subsets
- Backtracking
- Recursive without memo

**O(n!) - Factorial:**
- Permutations
- N-Queens
- TSP brute force

### **By Space Complexity:**

**O(1) - Constant:**
- Two pointers
- Math operations
- Bit manipulation
- Greedy

**O(log n) - Logarithmic:**
- Recursion stack (balanced)
- Binary search recursion

**O(n) - Linear:**
- HashMap/Set
- 1D DP
- Stack/Queue
- Recursion stack

**O(n²) - Quadratic:**
- 2D DP table
- Adjacency matrix
- N-Queens board

---

## 📝 INTERVIEW ANSWER TEMPLATE

```javascript
// PROBLEM: [Name]
// PATTERN: [Pattern Used]
// TIME: O(?)
// SPACE: O(?)

function solution(input) {
    // 1. Handle edge cases
    if (!input || input.length === 0) return [];
    
    // 2. Initialize variables
    // [Set up data structures]
    
    // 3. Main algorithm
    // [Core logic]
    
    // 4. Return result
    return result;
}

// TEST CASES:
// Normal: [1,2,3] → [3,2,1]
// Edge: [] → []
// Single: [1] → [1]
```

---

## 🎪 PATTERN SELECTION FLOWCHART

```
Is input sorted?
  YES → Binary Search O(log n)
  NO ↓

Need pairs/triplets?
  YES → Two Pointers or HashMap
  NO ↓

Substring/Subarray?
  YES → Sliding Window
  NO ↓

Tree/Graph?
  YES → DFS for paths, BFS for levels
  NO ↓

Need optimization?
  YES → DP (overlapping) or Greedy (local optimal)
  NO ↓

All combinations?
  YES → Backtracking
  NO ↓

Need K elements?
  YES → Heap or QuickSelect
  NO ↓

Default → Try HashMap or sorting first
```

---

## ⚡ LAST MINUTE CHEAT CODES

### **Most Versatile Patterns (Learn First):**
1. **Two Pointers** - Works for many array problems
2. **HashMap** - O(1) lookup solves many problems
3. **DFS/BFS** - All tree/graph problems
4. **Binary Search** - Any sorted data
5. **Sliding Window** - Substring/subarray

### **Common Mistakes to Avoid:**
```javascript
// ❌ WRONG
for (let i = 0; i <= arr.length; i++)  // Off by one

// ✅ CORRECT  
for (let i = 0; i < arr.length; i++)

// ❌ WRONG
const mid = (left + right) / 2  // Can overflow

// ✅ CORRECT
const mid = left + Math.floor((right - left) / 2)

// ❌ WRONG
if (node == null)  // Use strict equality

// ✅ CORRECT
if (node === null)

// ❌ WRONG
return arr.sort()  // Sorts alphabetically!

// ✅ CORRECT
return arr.sort((a, b) => a - b)
```

### **Quick Wins:**
- **See "maximum/minimum"** → Think DP or Greedy
- **See "all possible"** → Think Backtracking  
- **See "shortest path"** → Think BFS
- **See "detect cycle"** → Think DFS with states
- **See "top/kth"** → Think Heap or QuickSelect
- **See "sorted"** → Think Binary Search

---

## 💯 SUCCESS FORMULA

### **During Interview:**

```
1. UNDERSTAND (2 min)
   - Clarify inputs/outputs
   - Ask about edge cases
   - Confirm examples

2. MATCH (1 min)
   - Identify pattern
   - State complexity goals
   
3. PSEUDOCODE (2 min)
   - Write high-level steps
   - Verify with example
   
4. CODE (5 min)
   - Implement cleanly
   - Use good variable names
   
5. TRACE (2 min)
   - Walk through example
   - Check edge cases
   
6. OPTIMIZE (2 min)
   - Mention trade-offs
   - Suggest improvements
```

### **If Stuck:**
1. Start with brute force
2. Think: Can I sort first?
3. Think: Can I use extra space?
4. Draw the problem
5. Try a simpler example

### **Power Phrases:**
- "Let me think about the pattern here..."
- "The brute force would be O(n²), but..."
- "I'm thinking we can optimize this with..."
- "Let me trace through an example..."
- "The trade-off here is..."

---

## 🏁 FINAL CHECKLIST

**Before coding:**
- [ ] Understood problem completely
- [ ] Identified the pattern
- [ ] Know time/space complexity
- [ ] Have a plan

**After coding:**
- [ ] Handled edge cases
- [ ] No off-by-one errors
- [ ] Good variable names
- [ ] Tested with example

**Common edge cases:**
- [ ] Empty input
- [ ] Single element
- [ ] All duplicates
- [ ] Very large input
- [ ] Negative numbers

---

## 🎯 YOU'VE GOT THIS!

Remember:
- **Think out loud** - Interviewers want to hear your process
- **Start simple** - Get a working solution first
- **Stay calm** - It's OK to take a moment to think
- **Ask questions** - Clarification shows good judgment
- **Be coachable** - Take hints gracefully

**The interviewer is on your side!** They want you to succeed. Show them how you think, and even if you don't get the perfect solution, demonstrating good problem-solving skills is what matters most.

**Good luck! You're going to do great! 🚀**