You are given an integer array ribbons, where ribbons[i] represents the length of the ith ribbon, and an integer k. You may cut any of the ribbons into any number of segments of positive integer lengths, or perform no cuts at all.
4, you can:
4,3 and one ribbon of length 1,2,2 and two ribbons of length 1, or1.Your task is to determine the maximum length of ribbon, x, that allows you to cut at least k ribbons, each of length x. You can discard any leftover ribbon from the cuts. If it is impossible to cut k ribbons of the same length, return 0.
Example 1:
Input: ribbons = [9,7,5], k = 3 Output: 5 Explanation: - Cut the first ribbon to two ribbons, one of length 5 and one of length 4. - Cut the second ribbon to two ribbons, one of length 5 and one of length 2. - Keep the third ribbon as it is. Now you have 3 ribbons of length 5.
Example 2:
Input: ribbons = [7,5,9], k = 4 Output: 4 Explanation: - Cut the first ribbon to two ribbons, one of length 4 and one of length 3. - Cut the second ribbon to two ribbons, one of length 4 and one of length 1. - Cut the third ribbon to three ribbons, two of length 4 and one of length 1. Now you have 4 ribbons of length 4.
Example 3:
Input: ribbons = [5,7,9], k = 22 Output: 0 Explanation: You cannot obtain k ribbons of the same positive integer length.
Constraints:
1 <= ribbons.length <= 1051 <= ribbons[i] <= 1051 <= k <= 109Problem Overview: You are given an array where each value represents the length of a ribbon. The task is to cut these ribbons into smaller pieces so that you obtain at least k ribbons of equal length. The goal is to maximize that length.
Approach 1: Brute Force Length Enumeration (Time: O(n * m), Space: O(1))
The simplest idea is to try every possible ribbon length from 1 up to the maximum ribbon length m. For each candidate length L, iterate through the array and count how many pieces you can produce using ribbon // L. If the total count is at least k, the length is feasible. Track the largest valid length during the scan. This works because cutting is independent for each ribbon, so the number of pieces is just integer division. The downside is performance: when the maximum ribbon length is large, iterating through all possible lengths makes the algorithm O(n * m), which becomes too slow for large inputs.
Approach 2: Binary Search on Ribbon Length (Time: O(n log m), Space: O(1))
The key observation: if a length L works (you can make at least k pieces), then every length smaller than L will also work. If L does not work, any larger length will also fail. This monotonic property allows a binary search over the answer space.
Search between 1 and max(ribbons). For a midpoint length mid, compute how many pieces can be formed by summing ribbon // mid for every element in the array. If the count is at least k, the length is feasible, so move the search to the right half to try a larger piece. Otherwise move left because the length is too large. The check itself is a linear scan, making each binary search step O(n). Since the search range halves each time, the overall complexity becomes O(n log m), where m is the maximum ribbon length.
This technique is often called binary search on the answer. Instead of searching indices, you search the space of possible results and validate each candidate using a greedy counting step.
Recommended for interviews: The expected solution is binary search on the ribbon length. Interviewers want to see that you recognize the monotonic feasibility condition and convert the optimization problem into a search problem. Mentioning the brute force approach first shows understanding of the problem space, but implementing the binary search optimization demonstrates stronger algorithmic thinking and reduces the complexity from O(n * m) to O(n log m).
We observe that if we can obtain k ropes of length x, then we can also obtain k ropes of length x-1. This implies that there is a monotonicity property, and we can use binary search to find the maximum length x such that we can obtain k ropes of length x.
We define the left boundary of the binary search as left=0, the right boundary as right=max(ribbons), and the middle value as mid=(left+right+1)/2. We then calculate the number of ropes we can obtain with length mid, denoted as cnt. If cnt geq k, it means we can obtain k ropes of length mid, so we update left to mid. Otherwise, we update right to mid-1.
Finally, we return left as the maximum length of the ropes we can obtain.
The time complexity is O(n times log M), where n and M are the number of ropes and the maximum length of the ropes, respectively. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
Rust
JavaScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Length Enumeration | O(n * m) | O(1) | Small ribbon lengths or when explaining baseline logic before optimization |
| Binary Search on Answer | O(n log m) | O(1) | General case and interview solution when ribbon lengths can be large |
CUTTING RIBBONS | PYTHON | LEETCODE # 1891 • Cracking FAANG • 9,160 views views
Watch 5 more video solutions →Practice Cutting Ribbons with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor