1891. Cutting Ribbons

This page provides solutions for the leetcode problem 1891. Cutting Ribbons.

Problem Explanation

The problem is asking us to cut the ribbons into one or more parts, such that each of the $\text{K}$ parts will have an equal maximum length. We are also allowed to discard any extra parts of the ribbons if required.

Solution

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

Java

class Solution {
  public int maxLength(int[] ribbons, int k) {
    int lo = 0;
    int hi = Integer.MIN_VALUE;
    for(int i = 0; i < ribbons.length; i++) hi = Math.max(ribbons[i], hi);
    while(lo < hi) {
      int mid = (lo + hi + 1) / 2;
      int partitions = getPartitions(ribbons, mid);
      if(partitions >= k) lo = mid;
      else hi = mid - 1;
    }
    return lo;
  }

  private int getPartitions(int[] ribbons, int required) {
    int partitions = 0;
    for(int i = 0; i < ribbons.length; i++) partitions += ribbons[i] / required;
    return partitions;
  }
}

Complexity

Let's say there are $\text{N}$ elements in an array, and $\text{S}$ is the length of the longest ribbon.

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 total space time complexity will be:

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