Leetcode - Capacity To Ship Packages Within D Days - Two Solutions
Here are my two solutions to today's Leetcode problem:
Both solutions use binary search, they are inspired by this solution, with slight performance improvements. Both of them rely on a greedy algorithm and binary search.
Solution 1:
This solution beats 98.92% of solutions in terms of runtime speed but only 21.8% in terms of memory usage.
const isPossible = (weights, days, maxShipSize) => {
let currentDay = 1;
let sumOfWeights = 0;
for (let i = 0; i < weights.length; i++) {
const weight = weights[i];
const newSum = sumOfWeights + weight;
if (newSum > maxShipSize) {
sumOfWeights = weight;
currentDay += 1;
} else {
sumOfWeights = newSum;
}
if (currentDay > days) {
return false;
}
}
if (currentDay <= days) {
return maxShipSize;
}
return true;
};
function shipWithinDays(weights, days) {
let left = Math.max(...weights);
let right = weights.reduce((a, b) => a + b, 0);
while (left < right) {
const mid = Math.floor((left + right) / 2);
if (isPossible(weights, days, mid)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
Solution 2
This one is slightly more balanced - it beats 64.87% of solutions in terms of runtime and 79.46% in terms of memory usage.
const isPossible = (weights, days, maxShipSize) => {
let currentDay = 1;
let sumOfWeights = 0;
for (let i = 0; i < weights.length; i++) {
const weight = weights[i];
const newSum = sumOfWeights + weight;
if (weight > maxShipSize) {
return false;
}
if (newSum > maxShipSize) {
sumOfWeights = weight;
currentDay += 1;
} else {
sumOfWeights = newSum;
}
if (currentDay > days) {
return false;
}
}
if (currentDay <= days) {
return maxShipSize;
}
return true;
};
function shipWithinDays(weights, days) {
let left = 0;
let right = weights.reduce((a, b) => a + b, 0);
while (left < right) {
const mid = Math.floor((left + right) / 2);
if (isPossible(weights, days, mid)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
