1011. Capacity To Ship Packages...

This page provides solutions for the leetcode problem 1011. Capacity To Ship Packages Within D Days.

Problem Explanation

The problem is asking us to calculate the least weight capacity of the ship that will allow all the packages on the conveyor belt to be shipped within a $\text{d}$ days.

Solution

This problem can be solved using the Binary Search technique. More such questions can be found here.

Java

class Solution {
    public int shipWithinDays(int[] weights, int days) {
        int lo = Integer.MIN_VALUE;
        int hi = 0;
        for(int i = 0; i < weights.length; i++) {
            lo = Math.max(lo, weights[i]);
            hi += weights[i];
        }

        while(lo < hi) {
            int mid = lo + (hi - lo) / 2;
            boolean isMoreDays = daysRequired(weights, mid, days);
            if(isMoreDays) lo = mid + 1;
            else hi = mid;
        }
        return lo;
    }

    private boolean daysRequired(int[] weights, int capacity, int days) {
        int required = 0, index = 0, sum = 0, requiredDays = 1;
        while(index < weights.length) {
            sum += weights[index];
            if(sum > capacity) {
                sum = weights[index];
                requiredDays++;
            }
            index++;
            if(requiredDays > days) return true;
        }
        return false;
    }
}

Complexity

Let's say there are $\text{N}$ elements in an array, and total sum of all elements in an array is $\text{S}$.

Time Complexity

The time complexity is $\text{O}(\log \text{S})$ for searching the optimal solution using binary search, and $\text{O}(\text{N})$ for checking if the array can be split into $\text{K}$ subarrays, so total time complexity will be:

$$\text{O}(\text{N} \log \text{S})$$

Space Complexity

The solution uses constant space for storing binary search variables, so space complexity will be:

$$\text{O}(1)$$