48C1

48Cp.js

const capitalOneSolutions = {
  easy: [
    {
      name: "Best Time to Buy and Sell Stock",
      companies: 110,
      timeComplexity: "O(n)",
      spaceComplexity: "O(1)",
      topics: ["Array", "Dynamic Programming"],
      solution: `
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;
}`
    },
    {
      name: "Valid Parentheses",
      companies: 96,
      timeComplexity: "O(n)",
      spaceComplexity: "O(n)",
      topics: ["String", "Stack"],
      solution: `
function isValid(s) {
    const stack = [];
    const map = { '(': ')', '{': '}', '[': ']' };
    
    for (let char of s) {
        if (map[char]) {
            stack.push(map[char]);
        } else if (stack.pop() !== char) {
            return false;
        }
    }
    return stack.length === 0;
}`
    },
    {
      name: "Merge Two Sorted Lists",
      companies: 38,
      timeComplexity: "O(m + n)",
      spaceComplexity: "O(1)",
      topics: ["Linked List", "Recursion"],
      solution: `
function mergeTwoLists(list1, list2) {
    const dummy = new ListNode(0);
    let current = dummy;
    
    while (list1 && list2) {
        if (list1.val <= list2.val) {
            current.next = list1;
            list1 = list1.next;
        } else {
            current.next = list2;
            list2 = list2.next;
        }
        current = current.next;
    }
    
    current.next = list1 || list2;
    return dummy.next;
}`
    },
    {
      name: "Roman to Integer",
      companies: 34,
      timeComplexity: "O(n)",
      spaceComplexity: "O(1)",
      topics: ["Hash Table", "Math", "String"],
      solution: `
function romanToInt(s) {
    const map = { 'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000 };
    let result = 0;
    
    for (let i = 0; i < s.length; i++) {
        const current = map[s[i]];
        const next = map[s[i + 1]];
        
        if (next > current) {
            result -= current;
        } else {
            result += current;
        }
    }
    return result;
}`
    },
    {
      name: "Palindrome Number",
      companies: 32,
      timeComplexity: "O(log n)",
      spaceComplexity: "O(1)",
      topics: ["Math"],
      solution: `
function isPalindrome(x) {
    if (x < 0 || (x % 10 === 0 && x !== 0)) return false;
    
    let reversed = 0;
    while (x > reversed) {
        reversed = reversed * 10 + x % 10;
        x = Math.floor(x / 10);
    }
    
    return x === reversed || x === Math.floor(reversed / 10);
}`
    },
    {
      name: "Add Strings",
      companies: 5,
      timeComplexity: "O(max(m, n))",
      spaceComplexity: "O(max(m, n))",
      topics: ["Math", "String", "Simulation"],
      solution: `
function addStrings(num1, num2) {
    let result = '';
    let carry = 0;
    let i = num1.length - 1;
    let j = num2.length - 1;
    
    while (i >= 0 || j >= 0 || carry) {
        const digit1 = i >= 0 ? parseInt(num1[i--]) : 0;
        const digit2 = j >= 0 ? parseInt(num2[j--]) : 0;
        const sum = digit1 + digit2 + carry;
        
        result = (sum % 10) + result;
        carry = Math.floor(sum / 10);
    }
    
    return result;
}`
    },
    {
      name: "Binary Tree Paths",
      companies: 3,
      timeComplexity: "O(n)",
      spaceComplexity: "O(n)",
      topics: ["String", "Backtracking", "Tree", "Depth-First Search", "Binary Tree"],
      solution: `
function binaryTreePaths(root) {
    const result = [];
    
    function dfs(node, path) {
        if (!node) return;
        
        path += node.val;
        
        if (!node.left && !node.right) {
            result.push(path);
        } else {
            path += '->';
            dfs(node.left, path);
            dfs(node.right, path);
        }
    }
    
    dfs(root, '');
    return result;
}`
    },
    {
      name: "Count Operations to Obtain Zero",
      companies: 3,
      timeComplexity: "O(log(max(num1, num2)))",
      spaceComplexity: "O(1)",
      topics: ["Math", "Simulation"],
      solution: `
function countOperations(num1, num2) {
    let count = 0;
    
    while (num1 > 0 && num2 > 0) {
        if (num1 >= num2) {
            num1 -= num2;
        } else {
            num2 -= num1;
        }
        count++;
    }
    
    return count;
}`
    },
    {
      name: "Count Prefix and Suffix Pairs I",
      companies: 2,
      timeComplexity: "O(n² * m)",
      spaceComplexity: "O(1)",
      topics: ["Array", "String", "Trie", "Rolling Hash", "String Matching", "Hash Function"],
      solution: `
function countPrefixSuffixPairs(words) {
    let count = 0;
    
    function isPrefixAndSuffix(str1, str2) {
        return str2.startsWith(str1) && str2.endsWith(str1);
    }
    
    for (let i = 0; i < words.length; i++) {
        for (let j = i + 1; j < words.length; j++) {
            if (isPrefixAndSuffix(words[i], words[j])) {
                count++;
            }
        }
    }
    
    return count;
}`
    }
  ],

  medium: [
    {
      name: "Number of Islands",
      companies: 76,
      timeComplexity: "O(m * n)",
      spaceComplexity: "O(m * n)",
      topics: ["Array", "Depth-First Search", "Breadth-First Search", "Union Find", "Matrix"],
      solution: `
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) {
        if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] === '0') {
            return;
        }
        
        grid[i][j] = '0';
        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;
}`
    },
    {
      name: "Spiral Matrix",
      companies: 44,
      timeComplexity: "O(m * n)",
      spaceComplexity: "O(m * n)",
      topics: ["Array", "Matrix", "Simulation"],
      solution: `
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) {
        for (let i = left; i <= right; i++) result.push(matrix[top][i]);
        top++;
        
        for (let i = top; i <= bottom; i++) result.push(matrix[i][right]);
        right--;
        
        if (top <= bottom) {
            for (let i = right; i >= left; i--) result.push(matrix[bottom][i]);
            bottom--;
        }
        
        if (left <= right) {
            for (let i = bottom; i >= top; i--) result.push(matrix[i][left]);
            left++;
        }
    }
    return result;
}`
    },
    {
      name: "Add Two Numbers",
      companies: 37,
      timeComplexity: "O(max(m, n))",
      spaceComplexity: "O(max(m, n))",
      topics: ["Linked List", "Math", "Recursion"],
      solution: `
function addTwoNumbers(l1, l2) {
    const dummy = new ListNode(0);
    let current = dummy;
    let carry = 0;
    
    while (l1 || l2 || carry) {
        const val1 = l1 ? l1.val : 0;
        const val2 = l2 ? l2.val : 0;
        const sum = val1 + val2 + carry;
        
        carry = Math.floor(sum / 10);
        current.next = new ListNode(sum % 10);
        current = current.next;
        
        if (l1) l1 = l1.next;
        if (l2) l2 = l2.next;
    }
    
    return dummy.next;
}`
    },
    {
      name: "Rotate Image",
      companies: 33,
      timeComplexity: "O(n²)",
      spaceComplexity: "O(1)",
      topics: ["Array", "Math", "Matrix"],
      solution: `
function rotate(matrix) {
    const n = matrix.length;
    
    // Transpose
    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]];
        }
    }
    
    // Reverse each row
    for (let i = 0; i < n; i++) {
        matrix[i].reverse();
    }
}`
    },
    {
      name: "Meeting Rooms II",
      companies: 31,
      timeComplexity: "O(n log n)",
      spaceComplexity: "O(n)",
      topics: ["Array", "Two Pointers", "Greedy", "Sorting", "Heap (Priority Queue)", "Prefix Sum"],
      solution: `
function minMeetingRooms(intervals) {
    if (!intervals.length) return 0;
    
    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, endPtr = 0;
    
    for (let i = 0; i < starts.length; i++) {
        if (starts[i] < ends[endPtr]) {
            rooms++;
        } else {
            endPtr++;
        }
    }
    
    return rooms;
}`
    },
    {
      name: "Word Search",
      companies: 31,
      timeComplexity: "O(m*n*4^L)",
      spaceComplexity: "O(L)",
      topics: ["Array", "String", "Backtracking", "Depth-First Search", "Matrix"],
      solution: `
function exist(board, word) {
    const m = board.length, n = board[0].length;
    
    function dfs(i, j, index) {
        if (index === word.length) return true;
        if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] !== word[index]) {
            return false;
        }
        
        const temp = board[i][j];
        board[i][j] = '#';
        
        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);
        
        board[i][j] = temp;
        return found;
    }
    
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (dfs(i, j, 0)) return true;
        }
    }
    return false;
}`
    },
    {
      name: "Best Time to Buy and Sell Stock II",
      companies: 29,
      timeComplexity: "O(n)",
      spaceComplexity: "O(1)",
      topics: ["Array", "Dynamic Programming", "Greedy"],
      solution: `
function maxProfit(prices) {
    let profit = 0;
    
    for (let i = 1; i < prices.length; i++) {
        if (prices[i] > prices[i - 1]) {
            profit += prices[i] - prices[i - 1];
        }
    }
    
    return profit;
}`
    },
    {
      name: "Coin Change",
      companies: 29,
      timeComplexity: "O(amount * n)",
      spaceComplexity: "O(amount)",
      topics: ["Array", "Dynamic Programming", "Breadth-First Search"],
      solution: `
function coinChange(coins, amount) {
    const dp = Array(amount + 1).fill(Infinity);
    dp[0] = 0;
    
    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];
}`
    },
    {
      name: "Rotate Array",
      companies: 23,
      timeComplexity: "O(n)",
      spaceComplexity: "O(1)",
      topics: ["Array", "Math", "Two Pointers"],
      solution: `
function rotate(nums, k) {
    k = k % nums.length;
    
    function reverse(start, end) {
        while (start < end) {
            [nums[start], nums[end]] = [nums[end], nums[start]];
            start++;
            end--;
        }
    }
    
    reverse(0, nums.length - 1);
    reverse(0, k - 1);
    reverse(k, nums.length - 1);
}`
    },
    {
      name: "Simplify Path",
      companies: 21,
      timeComplexity: "O(n)",
      spaceComplexity: "O(n)",
      topics: ["String", "Stack"],
      solution: `
function simplifyPath(path) {
    const stack = [];
    const parts = path.split('/');
    
    for (let part of parts) {
        if (part === '..') {
            stack.pop();
        } else if (part && part !== '.') {
            stack.push(part);
        }
    }
    
    return '/' + stack.join('/');
}`
    },
    {
      name: "Find the Length of the Longest Common Prefix",
      companies: 7,
      timeComplexity: "O(n * m²)",
      spaceComplexity: "O(1)",
      topics: ["Array", "Hash Table", "String", "Trie"],
      solution: `
function longestCommonPrefix(arr1, arr2) {
    const set = new Set();
    
    // Add all prefixes of arr1 to set
    for (let num of arr1) {
        const str = num.toString();
        for (let i = 1; i <= str.length; i++) {
            set.add(str.substring(0, i));
        }
    }
    
    let maxLen = 0;
    
    // Check prefixes of arr2
    for (let num of arr2) {
        const str = num.toString();
        for (let i = 1; i <= str.length; i++) {
            if (set.has(str.substring(0, i))) {
                maxLen = Math.max(maxLen, i);
            }
        }
    }
    
    return maxLen;
}`
    },
    {
      name: "Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit",
      companies: 7,
      timeComplexity: "O(n)",
      spaceComplexity: "O(n)",
      topics: ["Array", "Queue", "Sliding Window", "Heap (Priority Queue)", "Ordered Set", "Monotonic Queue"],
      solution: `
function longestSubarray(nums, limit) {
    const maxDeque = [], minDeque = [];
    let left = 0, result = 0;
    
    for (let right = 0; right < nums.length; right++) {
        while (maxDeque.length && nums[maxDeque[maxDeque.length - 1]] <= nums[right]) {
            maxDeque.pop();
        }
        maxDeque.push(right);
        
        while (minDeque.length && nums[minDeque[minDeque.length - 1]] >= nums[right]) {
            minDeque.pop();
        }
        minDeque.push(right);
        
        while (nums[maxDeque[0]] - nums[minDeque[0]] > limit) {
            left++;
            if (maxDeque[0] < left) maxDeque.shift();
            if (minDeque[0] < left) minDeque.shift();
        }
        
        result = Math.max(result, right - left + 1);
    }
    
    return result;
}`
    },
    {
      name: "Non-overlapping Intervals",
      companies: 6,
      timeComplexity: "O(n log n)",
      spaceComplexity: "O(1)",
      topics: ["Array", "Dynamic Programming", "Greedy", "Sorting"],
      solution: `
function eraseOverlapIntervals(intervals) {
    if (!intervals.length) return 0;
    
    intervals.sort((a, b) => a[1] - b[1]);
    
    let count = 0;
    let prevEnd = intervals[0][1];
    
    for (let i = 1; i < intervals.length; i++) {
        if (intervals[i][0] < prevEnd) {
            count++;
        } else {
            prevEnd = intervals[i][1];
        }
    }
    
    return count;
}`
    },
    {
      name: "Simple Bank System",
      companies: 6,
      timeComplexity: "O(1) per operation",
      spaceComplexity: "O(n)",
      topics: ["Array", "Hash Table", "Design", "Simulation"],
      solution: `
class Bank {
    constructor(balance) {
        this.balance = balance;
        this.n = balance.length;
    }
    
    transfer(account1, account2, money) {
        if (!this.isValid(account1) || !this.isValid(account2)) return false;
        if (this.balance[account1 - 1] < money) return false;
        
        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;
    }
    
    isValid(account) {
        return account >= 1 && account <= this.n;
    }
}`
    },
    {
      name: "Candy Crush",
      companies: 5,
      timeComplexity: "O((m*n)²)",
      spaceComplexity: "O(m*n)",
      topics: ["Array", "Two Pointers", "Matrix", "Simulation"],
      solution: `
function candyCrush(board) {
    const m = board.length, n = board[0].length;
    let changed = true;
    
    while (changed) {
        changed = false;
        
        // Mark candies to crush
        for (let i = 0; i < m; i++) {
            for (let j = 0; j < n; j++) {
                const val = Math.abs(board[i][j]);
                if (val === 0) continue;
                
                // Check horizontal
                if (j + 2 < n && Math.abs(board[i][j + 1]) === val && 
                    Math.abs(board[i][j + 2]) === val) {
                    board[i][j] = board[i][j + 1] = board[i][j + 2] = -val;
                    changed = true;
                }
                
                // Check vertical
                if (i + 2 < m && Math.abs(board[i + 1][j]) === val && 
                    Math.abs(board[i + 2][j]) === val) {
                    board[i][j] = board[i + 1][j] = board[i + 2][j] = -val;
                    changed = true;
                }
            }
        }
        
        // Drop candies
        for (let j = 0; j < n; j++) {
            let writeRow = m - 1;
            for (let i = m - 1; i >= 0; i--) {
                if (board[i][j] > 0) {
                    board[writeRow--][j] = board[i][j];
                }
            }
            while (writeRow >= 0) {
                board[writeRow--][j] = 0;
            }
        }
    }
    
    return board;
}`
    },
    {
      name: "Design File System",
      companies: 5,
      timeComplexity: "O(n)",
      spaceComplexity: "O(n)",
      topics: ["Hash Table", "String", "Design", "Trie"],
      solution: `
class FileSystem {
    constructor() {
        this.paths = new Map();
    }
    
    createPath(path, value) {
        if (path === "" || path === "/" || this.paths.has(path)) {
            return false;
        }
        
        const lastSlash = path.lastIndexOf('/');
        const parent = path.substring(0, lastSlash);
        
        if (parent !== "" && !this.paths.has(parent)) {
            return false;
        }
        
        this.paths.set(path, value);
        return true;
    }
    
    get(path) {
        return this.paths.get(path) ?? -1;
    }
}`
    },
    {
      name: "Rotating the Box",
      companies: 5,
      timeComplexity: "O(m * n)",
      spaceComplexity: "O(m * n)",
      topics: ["Array", "Two Pointers", "Matrix"],
      solution: `
function rotateTheBox(box) {
    const m = box.length, n = box[0].length;
    
    // Apply gravity
    for (let i = 0; i < m; i++) {
        let writePos = n - 1;
        for (let j = n - 1; j >= 0; j--) {
            if (box[i][j] === '*') {
                writePos = j - 1;
            } else if (box[i][j] === '#') {
                box[i][j] = '.';
                box[i][writePos--] = '#';
            }
        }
    }
    
    // Rotate 90 degrees clockwise
    const result = Array(n).fill().map(() => Array(m).fill(0));
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            result[j][m - 1 - i] = box[i][j];
        }
    }
    
    return result;
}`
    },
    {
      name: "Minimum Operations to Write the Letter Y on a Grid",
      companies: 4,
      timeComplexity: "O(n²)",
      spaceComplexity: "O(1)",
      topics: ["Array", "Hash Table", "Matrix", "Counting"],
      solution: `
function minimumOperationsToWriteY(grid) {
    const n = grid.length;
    const mid = Math.floor(n / 2);
    
    // Count values in Y and not in Y
    const yCount = [0, 0, 0];
    const nonYCount = [0, 0, 0];
    
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            let isY = false;
            
            // Top-left diagonal
            if (i < mid && i === j) isY = true;
            // Top-right diagonal
            else if (i < mid && i + j === n - 1) isY = true;
            // Vertical line
            else if (i >= mid && j === mid) isY = true;
            
            if (isY) {
                yCount[grid[i][j]]++;
            } else {
                nonYCount[grid[i][j]]++;
            }
        }
    }
    
    let minOps = Infinity;
    
    // Try all combinations
    for (let yVal = 0; yVal <= 2; yVal++) {
        for (let nonYVal = 0; nonYVal <= 2; nonYVal++) {
            if (yVal === nonYVal) continue;
            
            const yOps = yCount[0] + yCount[1] + yCount[2] - yCount[yVal];
            const nonYOps = nonYCount[0] + nonYCount[1] + nonYCount[2] - nonYCount[nonYVal];
            
            minOps = Math.min(minOps, yOps + nonYOps);
        }
    }
    
    return minOps;
}`
    },
    {
      name: "Number of Black Blocks",
      companies: 4,
      timeComplexity: "O(n)",
      spaceComplexity: "O(n)",
      topics: ["Array", "Hash Table", "Enumeration"],
      solution: `
function countBlackBlocks(m, n, coordinates) {
    const result = [0, 0, 0, 0, 0];
    const blocks = new Map();
    
    for (let [x, y] of coordinates) {
        // Check all 2x2 blocks this cell belongs to
        for (let i = Math.max(0, x - 1); i <= Math.min(m - 2, x); i++) {
            for (let j = Math.max(0, y - 1); j <= Math.min(n - 2, y); j++) {
                const key = i * n + j;
                blocks.set(key, (blocks.get(key) || 0) + 1);
            }
        }
    }
    
    for (let count of blocks.values()) {
        result[count]++;
    }
    
    result[0] = (m - 1) * (n - 1) - blocks.size;
    
    return result;
}`
    },
    {
      name: "Get Biggest Three Rhombus Sums in a Grid",
      companies: 2,
      timeComplexity: "O(m * n * min(m, n))",
      spaceComplexity: "O(m * n)",
      topics: ["Array", "Math", "Sorting", "Heap (Priority Queue)", "Matrix", "Prefix Sum"],
      solution: `
function getBiggestThree(grid) {
    const m = grid.length, n = grid[0].length;
    const sums = new Set();
    
    // Add all single cells
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            sums.add(grid[i][j]);
        }
    }
    
    // Check all possible rhombi
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            for (let size = 1; i + 2 * size < m && j - size >= 0 && j + size < n; size++) {
                let sum = 0;
                
                // Top to right
                for (let k = 0; k <= size; k++) {
                    sum += grid[i + k][j + k];
                }
                
                // Right to bottom
                for (let k = 1; k <= size; k++) {
                    sum += grid[i + size + k][j + size - k];
                }
                
                // Bottom to left
                for (let k = 1; k <= size; k++) {
                    sum += grid[i + 2 * size - k][j - k];
                }
                
                // Left to top
                for (let k = 1; k < size; k++) {
                    sum += grid[i + size - k][j - size + k];
                }
                
                sums.add(sum);
            }
        }
    }
    
    const sorted = [...sums].sort((a, b) => b - a);
    return sorted.slice(0, 3);
}`
    },
    {
      name: "K-diff Pairs in an Array",
      companies: 2,
      timeComplexity: "O(n)",
      spaceComplexity: "O(n)",
      topics: ["Array", "Hash Table", "Two Pointers", "Binary Search", "Sorting"],
      solution: `
function findPairs(nums, k) {
    if (k < 0) return 0;
    
    const count = new Map();
    for (let num of nums) {
        count.set(num, (count.get(num) || 0) + 1);
    }
    
    let result = 0;
    
    for (let [num, freq] of count) {
        if (k === 0) {
            if (freq >= 2) result++;
        } else {
            if (count.has(num + k)) result++;
        }
    }
    
    return result;
}`
    },
    {
      name: "Count Alternating Subarrays",
      companies: 1,
      timeComplexity: "O(n)",
      spaceComplexity: "O(1)",
      topics: ["Array", "Math"],
      solution: `
function countAlternatingSubarrays(nums) {
    let count = 0;
    let length = 1;
    
    for (let i = 0; i < nums.length; i++) {
        if (i > 0 && nums[i] !== nums[i - 1]) {
            length++;
        } else {
            length = 1;
        }
        count += length;
    }
    
    return count;
}`
    },
    {
      name: "Four Divisors",
      companies: 1,
      timeComplexity: "O(n * √max)",
      spaceComplexity: "O(1)",
      topics: ["Array", "Math"],
      solution: `
function sumFourDivisors(nums) {
    let totalSum = 0;
    
    for (let num of nums) {
        const divisors = [];
        
        for (let i = 1; i * i <= num; i++) {
            if (num % i === 0) {
                divisors.push(i);
                if (i !== num / i) {
                    divisors.push(num / i);
                }
            }
            
            if (divisors.length > 4) break;
        }
        
        if (divisors.length === 4) {
            totalSum += divisors.reduce((a, b) => a + b, 0);
        }
    }
    
    return totalSum;
}`
    }
  ],

  hard: [
    {
      name: "Text Justification",
      companies: 33,
      timeComplexity: "O(n)",
      spaceComplexity: "O(n)",
      topics: ["Array", "String", "Simulation"],
      solution: `
function fullJustify(words, maxWidth) {
    const result = [];
    let i = 0;
    
    while (i < words.length) {
        let j = i + 1;
        let lineLength = words[i].length;
        
        while (j < words.length && lineLength + words[j].length + (j - i) <= maxWidth) {
            lineLength += words[j].length;
            j++;
        }
        
        const gaps = j - i - 1;
        let line = '';
        
        if (j === words.length || gaps === 0) {
            // Last line or single word line - left justify
            for (let k = i; k < j; k++) {
                line += words[k];
                if (k < j - 1) line += ' ';
            }
            while (line.length < maxWidth) line += ' ';
        } else {
            // Middle justified
            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) {
                    line += ' '.repeat(spacesPerGap + (k - i < extraSpaces ? 1 : 0));
                }
            }
        }
        
        result.push(line);
        i = j;
    }
    
    return result;
}`
    },
    {
      name: "Reverse Nodes in k-Group",
      companies: 29,
      timeComplexity: "O(n)",
      spaceComplexity: "O(1)",
      topics: ["Linked List", "Recursion"],
      solution: `
function reverseKGroup(head, k) {
    let count = 0;
    let node = head;
    
    // Check if there are at least k nodes
    while (node && count < k) {
        node = node.next;
        count++;
    }
    
    if (count === k) {
        // Reverse k nodes
        let current = head;
        let prev = null;
        let next = null;
        
        for (let i = 0; i < k; i++) {
            next = current.next;
            current.next = prev;
            prev = current;
            current = next;
        }
        
        // head is now the last node in the reversed group
        head.next = reverseKGroup(current, k);
        return prev;
    }
    
    return head;
}`
    },
    {
      name: "Largest Rectangle in Histogram",
      companies: 24,
      timeComplexity: "O(n)",
      spaceComplexity: "O(n)",
      topics: ["Array", "Stack", "Monotonic Stack"],
      solution: `
function largestRectangleArea(heights) {
    const stack = [];
    let maxArea = 0;
    heights.push(0);
    
    for (let i = 0; i < heights.length; i++) {
        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;
}`
    },
    {
      name: "Word Search II",
      companies: 16,
      timeComplexity: "O(m*n*4^L)",
      spaceComplexity: "O(total characters)",
      topics: ["Array", "String", "Backtracking", "Trie", "Matrix"],
      solution: `
function findWords(board, words) {
    class TrieNode {
        constructor() {
            this.children = {};
            this.word = null;
        }
    }
    
    // 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];
        if (!node.children[char]) return;
        
        node = node.children[char];
        if (node.word) {
            result.push(node.word);
            node.word = null; // Avoid duplicates
        }
        
        board[i][j] = '#';
        
        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);
        
        board[i][j] = char;
    }
    
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            dfs(i, j, root);
        }
    }
    
    return result;
}`
    },
    {
      name: "Block Placement Queries",
      companies: 6,
      timeComplexity: "O(q log n)",
      spaceComplexity: "O(n)",
      topics: ["Array", "Binary Search", "Binary Indexed Tree", "Segment Tree"],
      solution: `
function getResults(queries) {
    const obstacles = new Set([0]);
    const segments = new Map([[0, 0]]);
    const results = [];
    
    function updateSegments(x) {
        const sorted = [...obstacles].sort((a, b) => a - b);
        const idx = sorted.indexOf(x);
        
        if (idx > 0) {
            const prev = sorted[idx - 1];
            segments.set(prev, x - prev);
        }
        
        if (idx < sorted.length - 1) {
            const next = sorted[idx + 1];
            segments.set(x, next - x);
        }
    }
    
    for (let query of queries) {
        if (query[0] === 1) {
            const x = query[1];
            obstacles.add(x);
            updateSegments(x);
        } else {
            const x = query[1], sz = query[2];
            let canPlace = false;
            
            const sorted = [...obstacles].filter(obs => obs <= x).sort((a, b) => a - b);
            
            for (let i = 0; i < sorted.length; i++) {
                const start = sorted[i];
                const end = i === sorted.length - 1 ? x : Math.min(x, sorted[i + 1]);
                
                if (end - start >= sz) {
                    canPlace = true;
                    break;
                }
            }
            
            results.push(canPlace);
        }
    }
    
    return results;
}`
    },
    {
      name: "Find Servers That Handled Most Number of Requests",
      companies: 5,
      timeComplexity: "O(n log k)",
      spaceComplexity: "O(k)",
      topics: ["Array", "Greedy", "Heap (Priority Queue)", "Ordered Set"],
      solution: `
function busiestServers(k, arrival, load) {
    const available = new Set();
    for (let i = 0; i < k; i++) available.add(i);
    
    const busy = []; // Min heap by end time
    const requestCount = Array(k).fill(0);
    
    for (let i = 0; i < arrival.length; i++) {
        const time = arrival[i];
        
        // Free up servers
        while (busy.length && busy[0][0] <= time) {
            const [, server] = busy.shift();
            available.add(server);
        }
        
        if (available.size === 0) continue;
        
        // Find the next available server
        const target = i % k;
        let server = -1;
        
        for (let j = 0; j < k; j++) {
            const idx = (target + j) % k;
            if (available.has(idx)) {
                server = idx;
                break;
            }
        }
        
        if (server !== -1) {
            available.delete(server);
            busy.push([time + load[i], server]);
            busy.sort((a, b) => a[0] - b[0]);
            requestCount[server]++;
        }
    }
    
    const maxCount = Math.max(...requestCount);
    const result = [];
    
    for (let i = 0; i < k; i++) {
        if (requestCount[i] === maxCount) {
            result.push(i);
        }
    }
    
    return result;
}`
    },
    {
      name: "Number of Flowers in Full Bloom",
      companies: 5,
      timeComplexity: "O((n + m) log n)",
      spaceComplexity: "O(n)",
      topics: ["Array", "Hash Table", "Binary Search", "Sorting", "Prefix Sum", "Ordered Set"],
      solution: `
function fullBloomFlowers(flowers, people) {
    const starts = flowers.map(f => f[0]).sort((a, b) => a - b);
    const ends = flowers.map(f => f[1]).sort((a, b) => a - b);
    
    function bisectRight(arr, x) {
        let left = 0, right = arr.length;
        while (left < right) {
            const mid = Math.floor((left + right) / 2);
            if (arr[mid] <= x) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
    
    function bisectLeft(arr, x) {
        let left = 0, right = arr.length;
        while (left < right) {
            const mid = Math.floor((left + right) / 2);
            if (arr[mid] < x) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
    
    const result = [];
    
    for (let person of people) {
        const started = bisectRight(starts, person);
        const ended = bisectLeft(ends, person);
        result.push(started - ended);
    }
    
    return result;
}`
    },
    {
      name: "Split Message Based on Limit",
      companies: 5,
      timeComplexity: "O(n * k)",
      spaceComplexity: "O(n)",
      topics: ["String", "Binary Search", "Enumeration"],
      solution: `
function splitMessage(message, limit) {
    const n = message.length;
    
    function canSplit(parts) {
        let totalParts = parts;
        let messageIdx = 0;
        
        for (let i = 1; i <= parts; i++) {
            const suffix = \`<\${i}/\${parts}>\`;
            const available = limit - suffix.length;
            
            if (available <= 0) return false;
            
            messageIdx += available;
        }
        
        return messageIdx >= n;
    }
    
    // Try different number of parts
    for (let parts = 1; parts <= n; parts++) {
        if (canSplit(parts)) {
            const result = [];
            let messageIdx = 0;
            
            for (let i = 1; i <= parts; i++) {
                const suffix = \`<\${i}/\${parts}>\`;
                const available = limit - suffix.length;
                
                const chunk = message.substring(messageIdx, 
                    Math.min(messageIdx + available, n));
                result.push(chunk + suffix);
                messageIdx += available;
            }
            
            return result;
        }
    }
    
    return [];
}`
    },
    {
      name: "Count Prefix and Suffix Pairs II",
      companies: 3,
      timeComplexity: "O(n * m²)",
      spaceComplexity: "O(n * m)",
      topics: ["Array", "String", "Trie", "Rolling Hash", "String Matching", "Hash Function"],
      solution: `
function countPrefixSuffixPairs(words) {
    class TrieNode {
        constructor() {
            this.children = {};
            this.indices = [];
        }
    }
    
    const prefixTrie = new TrieNode();
    const suffixTrie = new TrieNode();
    
    // Build tries
    for (let idx = 0; idx < words.length; idx++) {
        const word = words[idx];
        
        // Add to prefix trie
        let node = prefixTrie;
        for (let char of word) {
            if (!node.children[char]) {
                node.children[char] = new TrieNode();
            }
            node = node.children[char];
            node.indices.push(idx);
        }
        
        // Add to suffix trie
        node = suffixTrie;
        for (let i = word.length - 1; i >= 0; i--) {
            const char = word[i];
            if (!node.children[char]) {
                node.children[char] = new TrieNode();
            }
            node = node.children[char];
            node.indices.push(idx);
        }
    }
    
    let count = 0;
    
    for (let i = 0; i < words.length; i++) {
        for (let j = i + 1; j < words.length; j++) {
            if (words[j].startsWith(words[i]) && words[j].endsWith(words[i])) {
                count++;
            }
        }
    }
    
    return count;
}`
    },
    {
      name: "Remove Boxes",
      companies: 3,
      timeComplexity: "O(n⁴)",
      spaceComplexity: "O(n³)",
      topics: ["Array", "Dynamic Programming", "Memoization"],
      solution: `
function removeBoxes(boxes) {
    const n = boxes.length;
    const memo = {};
    
    function dp(l, r, k) {
        if (l > r) return 0;
        
        const key = \`\${l},\${r},\${k}\`;
        if (key in memo) return memo[key];
        
        // Optimization: increase k while boxes[r] equals boxes[r-1]
        while (l < r && boxes[r] === boxes[r - 1]) {
            r--;
            k++;
        }
        
        // Option 1: Remove boxes[r] with k same-colored boxes
        let result = dp(l, r - 1, 0) + (k + 1) * (k + 1);
        
        // Option 2: Find same colored box and merge
        for (let i = l; i < r; i++) {
            if (boxes[i] === boxes[r]) {
                result = Math.max(result, 
                    dp(l, i, k + 1) + dp(i + 1, r - 1, 0));
            }
        }
        
        memo[key] = result;
        return result;
    }
    
    return dp(0, n - 1, 0);
}`
    }
  ]
};

// Print summary
console.log(\`Total Capital One Problems: \${
  capitalOneSolutions.easy.length + 
  capitalOneSolutions.medium.length + 
  capitalOneSolutions.hard.length
}\`);
console.log(\`Easy: \${capitalOneSolutions.easy.length}\`);
console.log(\`Medium: \${capitalOneSolutions.medium.length}\`);
console.log(\`Hard: \${capitalOneSolutions.hard.length}\`);

// Export for use
export default capitalOneSolutions;