Capacity To Ship Packages Within D Days LeetCode solution in Java

1
class Solution {
2
  public int shipWithinDays(int[] weights, int days) {
3
    int left = 0;
4
    int right = 0;
5
    //  left is the biggest element in the array. It's set as the lower boundary.
6
    //  right is the sum of the array, which is the upper limit.
7
    for (int weight : weights) {
8
      left = Math.max(weight, left);
9
      right += weight;
10
    }
11
    int res = 0;
12
    while (left <= right) {
13
      int mid = (left + right) / 2;
14
      // make sure mid is a possible value
15
      if (isPossible(weights, days, mid)) {
16
        res = mid;
17
        right = mid - 1;
18
      } else {
19
        left = mid + 1;
20
      }
21
    }
22
    return res;
23
  }
24

25
  public boolean isPossible(int[] weights, int days, int mid) {
26
    int totalDays = 1;
27
    int totalWeight = 0;
28
    for (int i = 0; i < weights.length; i++) {
29
      totalWeight += weights[i];
30
      // increase totalDays if totalWeight is larger than mid
31
      if (totalWeight > mid) {
32
        totalDays++;
33
        totalWeight = weights[i];
34
      }
35
      // the problem states all the packages have to ship within `days` days
36
      if (totalDays > days) {
37
        return false;
38
      }
39
    }
40
    return true;
41
  }
42
}