Calculating Dice Roll Combinations
Given d identical dice, each with f faces labeled from 1 to f, the objective is to determine the number of ways to achieve a specific sum target when rolling all dice. The result should be returned modulo 10^9 + 7.
A recursive approach with memoization efficiently solves this by breaking the problem down into smaller subproblems. For each die, we iterate through possible face values. If the remaining target minus the current face value is valid, we recursively calculate the ways to achieve that sum with the remaining dice.
function getRollCombinations(d, f, target) {
const MOD = 10 ** 9 + 7;
const memo = new Map();
function solve(diceLeft, currentTarget) {
const key = `${diceLeft},${currentTarget}`;
if (memo.has(key)) return memo.get(key);
if (diceLeft === 0) {
return currentTarget === 0 ? 1 : 0;
}
let totalWays = 0;
for (let face = 1; face <= f; face++) {
if (currentTarget - face >= 0) {
totalWays += solve(diceLeft - 1, currentTarget - face);
}
}
memo.set(key, totalWays % MOD);
return memo.get(key);
}
return solve(d, target);
}Counting Equivalent Domino Pairs
We need to find the number of pairs (i, j) such that i < j and the domino at i is equivalent to the domino at j. Two dominoes [a, b] and [c, d] are equivalent if (a === c && b === d) or (a === d && b === c).
Using a hash map allows us to count occurrences of specific domino patterns efficiently. By sorting the values within a domino, we ensure that [1, 2] and [2, 1] generate the same key.
function countDominoPairs(dominoes) {
const frequency = {};
let pairCount = 0;
for (const [a, b] of dominoes) {
// Create a canonical key by sorting the two numbers
const minVal = Math.min(a, b);
const maxVal = Math.max(a, b);
const key = `${minVal}|${maxVal}`;
if (frequency[key]) {
pairCount += frequency[key];
}
frequency[key] = (frequency[key] || 0) + 1;
}
return pairCount;
}Lowest Common Ancestor of Deepest Leaves
The task is to find the lowest common ancestor (LCA) of all leaf nodes that have the maximum depth in a binary tree.
This can be achieved by traversing the tree and tracking the depth of each node. If a node has both left and right subtrees containing leaves of the maximum depth, that node is a potential LCA. If only one subtree contains the deepest leaves, the LCA must be within that subtree.
function findLCA(root) {
let lcaNode = null;
let maxDepth = 0;
function traverse(node, depth) {
if (!node) return depth;
const leftDepth = traverse(node.left, depth + 1);
const rightDepth = traverse(node.right, depth + 1);
maxDepth = Math.max(maxDepth, leftDepth, rightDepth);
// If current depth matches max depth, it's a leaf
if (leftDepth === maxDepth && rightDepth === maxDepth) {
lcaNode = node;
} else if (leftDepth === maxDepth || rightDepth === maxDepth) {
// If only one side reaches max depth, propagate the ancestor up
// Logic handled implicitly by checking max depths at higher levels
if (depth === leftDepth || depth === rightDepth) {
// logic to handle leaf node case if necessary, but recursion handles it
}
}
// This specific logic identifies the split point
if (leftDepth === maxDepth && rightDepth === maxDepth) {
return depth; // This node becomes the new reference point
}
return Math.max(leftDepth, rightDepth);
}
// Alternative simplified approach often used:
function helper(node) {
if (!node) return null;
const left = helper(node.left);
const right = helper(node.right);
let leftDepth = left ? left.depth : 0;
let rightDepth = right ? right.depth : 0;
if (leftDepth > rightDepth) return { node: left.node, depth: leftDepth + 1 };
if (leftDepth < rightDepth) return { node: right.node, depth: rightDepth + 1 };
return { node: node, depth: leftDepth + 1 };
}
return helper(root).node;
}Car Pooling Capacity Check
We are given a list of trips where trips[i] = [numPassengers, from, to]. The vehicle moves only forward. We must determine if the vehicle, with a given capacity, can pick up and drop off all passengers without exceeding capacity at any point.
A timeline array can track the number of passengers at every location. By iterating through each trip and incrementing the passenger count for the duration of that trip, we can check if the capacity is ever exceeded.
function canCarPool(trips, capacity) {
const locationStops = new Array(1001).fill(0);
for (const [passengers, start, end] of trips) {
for (let i = start; i < end; i++) {
locationStops[i] += passengers;
if (locationStops[i] > capacity) {
return false;
}
}
}
return true;
}Corporate Flight Bookings
Given n flights and a list of bookings where bookings[i] = [first, last, seats], we need to return an array representing the total number of seats booked for each flight.
An efficient approach initializes an array of zeros. For each booking range, we add the number of seats to the corresponding indices in the array. This directly accumulates the counts for each flight.
function getFlightBookings(bookings, n) {
const result = new Array(n).fill(0);
bookings.forEach(([start, end, seats]) => {
for (let i = start - 1; i < end; i++) {
result[i] += seats;
}
});
return result;
}Longest Well-Performing Interval
An array hours represents daily working hours. A day is "tiring" if hours > 8. We need to find the length of the longest contiguous interval where the number of tiring days is strictly greater than the number of non-tiring days.
We can transform the array by mapping tiring days to 1 and non-tiring days to -1. The problem then reduces to finding the longest subarray with a positive sum.
function longestWellPerformingInterval(hours) {
const n = hours.length;
let maxLength = 0;
for (let i = 0; i < n; i++) {
let currentSum = 0;
for (let j = i; j < n; j++) {
currentSum += hours[j] > 8 ? 1 : -1;
if (currentSum > 0) {
maxLength = Math.max(maxLength, j - i + 1);
}
}
}
return maxLength;
}Maximizing Array Sum After K Negations
Given an integer array A, we can negate an element A[i] exactly K times. We can choose the same index multiple times. The goal is to maximize the sum of the array.
The optimal strategy is to negate the K smallest numbers. If there are more negations available than negative numbers, we might have to negate a zero or a positive number. If we negate a positive number (because K is odd and we have no zeros), we should choose the smallest absolute value element to minimize the reduction in total sum.
function maximizeSumAfterKNegations(A, K) {
A.sort((a, b) => a - b);
let i = 0;
while (i < A.length && A[i] < 0 && K > 0) {
A[i] = -A[i];
K--;
i++;
}
// If K is remaining, find the smallest element to negate
if (K > 0) {
A.sort((a, b) => a - b);
// If K is odd, negate the smallest element once
if (K % 2 !== 0) {
A[0] = -A[0];
}
}
return A.reduce((sum, val) => sum + val, 0);
}Rotting Oranges
In a grid, cells can be empty (0), fresh orange (1), or rotten orange (2). Every minute, any fresh orange adjacent (4-directionally) to a rotten orange becomes rotten. We must return the minimum time until no fresh oranges remain, or -1 if impossible.
This is a classic Breadth-First Search (BFS) problem. We start by enqueuing all initially rotten oranges. Then, we process the queue level by level (each level represents a minute), rotting adjacent fresh oranges and adding them to the queue for the next minute. We track the count of fresh oranges to determine if any remain unreachable.
function timeToRot(grid) {
const rows = grid.length;
const cols = grid[0].length;
const queue = [];
let freshCount = 0;
let minutes = 0;
const directions = [[1, 0], [-1, 0], [0, 1], [0, -1]];
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
if (grid[r][c] === 2) {
queue.push([r, c]);
} else if (grid[r][c] === 1) {
freshCount++;
}
}
}
if (freshCount === 0) return 0;
while (queue.length > 0) {
const levelSize = queue.length;
let hasRot = false;
for (let i = 0; i < levelSize; i++) {
const [r, c] = queue.shift();
for (const [dr, dc] of directions) {
const nr = r + dr;
const nc = c + dc;
if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] === 1) {
grid[nr][nc] = 2;
freshCount--;
queue.push([nr, nc]);
hasRot = true;
}
}
}
if (hasRot) minutes++;
}
return freshCount === 0 ? minutes : -1;
}Finding Common Characters
Given an array of strings A containing only lowercase letters, return a list of all characters that show up in all strings (including duplicates). For example, if a character appears 3 times in all strings but not 4 times, it should be included 3 times.
Since the array length can vary, we can take the first string as a reference. For each character in the reference string, we check if it exists in all other strings. If it does, we remove it from those strings (to handle duplicates correctly) and add it to the result.
function findCommonChars(A) {
const result = [];
const splitArrays = A.map(str => str.split(''));
const reference = splitArrays[0];
for (const char of reference) {
let isCommon = true;
for (let i = 1; i < splitArrays.length; i++) {
const index = splitArrays[i].indexOf(char);
if (index === -1) {
isCommon = false;
break;
} else {
// Remove the char to ensure we don't count it twice for the same word
splitArrays[i].splice(index, 1);
}
}
if (isCommon) {
result.push(char);
}
}
return result;
}Alphabet Board Path
We start at position (0, 0) on a board. The goal is to generate a sequence of moves ('U', 'D', 'L', 'R') to spell out a target string, minimizing moves. The character '!' selects the character at the current position.
We first map each character to its coordinates. Then, for each consecutive character in the target, we calculate the delta in rows and columns. We must be careful with the character 'z' because it is isolated; moving to or from 'z' requires vertical movement before horizontal movement to avoid going out of bounds.
function getBoardPath(target) {
const charMap = {};
for (let i = 0; i < 26; i++) {
charMap[String.fromCharCode(97 + i)] = [Math.floor(i / 5), i % 5];
}
let result = '';
let currentPos = [0, 0]; // Start at 'a'
for (const char of target) {
const targetPos = charMap[char];
const [rowDiff, colDiff] = [targetPos[0] - currentPos[0], targetPos[1] - currentPos[1]];
// Special handling for 'z' and moving away from 'z'
if (currentPos[0] === 5 && currentPos[1] === 0) {
// Currently at 'z', must move Up first
result += 'U'.repeat(-rowDiff);
result += 'R'.repeat(colDiff);
} else if (targetPos[0] === 5 && targetPos[1] === 0) {
// Moving to 'z', must move Left first
result += 'L'.repeat(-colDiff);
result += 'D'.repeat(rowDiff);
} else {
// Normal movement
result += 'U'.repeat(-Math.min(0, rowDiff));
result += 'D'.repeat(Math.max(0, rowDiff));
result += 'L'.repeat(-Math.min(0, colDiff));
result += 'R'.repeat(Math.max(0, colDiff));
}
result += '!';
currentPos = targetPos;
}
return result;
}Maximum Subarray Sum with One Deletion
Given an array of integers, return the maximum sum of a non-empty subarray, where we are allowed to delete at most one element from that subarray.
Dynamic programming is suitable here. We maintain two arrays: one for the maximum subarray sum ending at the current index without deletion, and another for the maximum sum ending at the current index with exactly one deletion.
function maximumSumWithDeletion(arr) {
const n = arr.length;
// dp0: max sum ending at i with 0 deletions
// dp1: max sum ending at i with 1 deletion
let dp0 = arr[0];
let dp1 = 0;
let maxSum = arr[0];
for (let i = 1; i < n; i++) {
// For dp1, we either delete current element (take dp0) or take current element (take previous dp1)
// dp1 logic: max(dp0 (delete arr[i]), dp1 + arr[i] (delete previous))
// Wait, standard interpretation:
// dp1[i] = max(dp1[i-1] + arr[i], dp0[i-1]) -> we delete arr[i] or we already deleted something else
const prevDp0 = dp0;
const prevDp1 = dp1;
dp0 = Math.max(arr[i], prevDp0 + arr[i]);
dp1 = Math.max(prevDp1 + arr[i], prevDp0); // delete current (prevDp0) or keep current (prevDp1 + arr[i])
maxSum = Math.max(maxSum, dp0, dp1);
}
return maxSum;
}Maximum Subarray Sum After K Concatenations
We need to find the maximum subarray sum of an array formed by concatenating the original array arr k times.
The logic depends on the sum of the original array (totalSum).
- If
totalSum > 0: The max sum will likely span across the concatenations. It will be the max sum ofarr + arrplus(k - 2) * totalSum. - If
totalSum <= 0: The max sum is contained withinarrorarr + arr, as adding more copies decreases the potential sum.
function maxSubArraySumKConcat(arr, k) {
const MOD = 10**9 + 7;
function kadane(array) {
let maxCurrent = array[0];
let maxGlobal = array[0];
for (let i = 1; i < array.length; i++) {
maxCurrent = Math.max(array[i], maxCurrent + array[i]);
if (maxCurrent > maxGlobal) {
maxGlobal = maxCurrent;
}
}
return Math.max(0, maxGlobal);
}
if (k === 1) return kadane(arr);
const totalSum = arr.reduce((a, b) => a + b, 0);
if (totalSum > 0) {
const maxDouble = kadane([...arr, ...arr]);
const sumExtra = (k - 2) * totalSum;
return (maxDouble + sumExtra) % MOD;
} else {
return kadane([...arr, ...arr]);
}
}