1011. Capacity To Ship Packages Within D Days

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)$$