3824. Minimum K to Reduce Array Within Limit

MediumArrayBinary Search

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

You are given a positive integer array nums.

For a positive integer k, we define nonPositive(nums, k) as the minimum number of operations needed to make every element of nums non-positive (that is, less than or equal to 0).

In a single operation, you are allowed to:

Choose an index i, and
Reduce the value of nums[i] by k.

The key observation here is how many operations a single element nums[i] needs. Since each operation reduces it by k, the number of operations required to bring nums[i] down to non-positive is ⌈nums[i] / k⌉ (the ceiling of nums[i] divided by k). Summing this over all elements gives the total value of nonPositive(nums, k).

Your task is to return an integer denoting the minimum value of k such that the following condition holds:

nonPositive(nums, k) <= k²

In other words, you need to find the smallest positive k for which the total number of operations needed to make all elements non-positive does not exceed k².

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Binary Search?

This problem maps to Binary Search through a short path in the full flowchart.

The condition nonPositive(nums, k) <= k^2 is monotonic in k, so binary searching for the minimum valid k gives the answer efficiently.

Open in Flowchart

Intuition

Let's think about how the two sides of the condition nonPositive(nums, k) <= k² behave as k changes.

On the left side, nonPositive(nums, k) is the total number of operations, which equals the sum of ⌈nums[i] / k⌉ over all elements. As k gets larger, each operation removes more from an element, so fewer operations are needed. This means the left side decreases (or stays the same) as k grows.

On the right side, k² grows quickly as k increases. So the right side increases as k grows.

Putting these two facts together: when k is small, the left side is large and the right side is small, so the condition is likely false. As k increases, the left side shrinks while the right side expands, making the condition easier to satisfy. Once the condition becomes true for some k, it remains true for all larger values of k.

This gives us a clear monotonic pattern:

k:          1    2    3    ...   answer   ...
condition:  F    F    F    ...   T   T   T   T

Whenever a problem has this "false then true" structure, we can use binary search to efficiently find the boundary point — that is, the smallest k where the condition first becomes true. Instead of checking every value of k one by one, we repeatedly cut the search range in half, which is much faster.

So the approach is to binary search on the value of k. For each candidate mid, we check whether nonPositive(nums, mid) <= mid² holds, and adjust our search range accordingly until we narrow down to the minimum valid k.

Pattern Learn more about Binary Search patterns.

Solution Approach

We use Binary Search to find the minimum value of k.

As discussed, the condition exhibits monotonicity: as k increases, it becomes easier to satisfy nonPositive(nums, k) <= k². This allows us to binary search for the smallest valid k.

Step 1: Define the check function

We write a helper function check(k) that determines whether the condition holds for a given k:

We initialize a counter t = 0 to accumulate the total number of operations.
For each element x in nums, we add ⌈x / k⌉ to t. In the code, this ceiling division is computed as (x + k - 1) // k, which is a common trick to perform ceiling division using integer division.
Finally, we return whether t <= k * k, i.e. whether nonPositive(nums, k) <= k².

def check(k: int) -> bool:
    t = 0
    for x in nums:
        t += (x + k - 1) // k
    return t <= k * k

Step 2: Set up the binary search boundaries

We define the left boundary l = 1 and the right boundary r = 10^5. The left boundary starts at 1 because k must be a positive integer, and 10^5 is a safe upper bound that is guaranteed to satisfy the condition.

Step 3: Perform the binary search

In each iteration, we compute the middle value mid = (l + r) >> 1 (using a right shift to divide by 2):

If check(mid) returns True, the condition is satisfied at mid, so the answer could be mid or something smaller. We move the right boundary to r = mid.
Otherwise, the condition fails at mid, so we need a larger k. We move the left boundary to l = mid + 1.

We continue until l == r. At that point, l is the minimum k we are looking for, and we return it.

l, r = 1, 10**5
while l < r:
    mid = (l + r) >> 1
    if check(mid):
        r = mid
    else:
        l = mid + 1
return l

Complexity Analysis

Time complexity: O(n × log M), where n is the length of nums and M is the size of the search range (10^5). Each binary search step runs the check function in O(n), and the binary search itself takes O(log M) steps.
Space complexity: O(1), since we only use a constant amount of extra space.

Example Walkthrough

Let's trace through the solution with a small example: nums = [3, 2, 4].

We want to find the minimum k such that nonPositive(nums, k) <= k².

Setting up binary search: We start with l = 1 and r = 10^5. To keep this walkthrough readable, let's first manually understand what the condition looks like for the smallest few values of k, then see how binary search converges.

Manually evaluating the condition for small k:

For each k, we compute nonPositive(nums, k) = ⌈3/k⌉ + ⌈2/k⌉ + ⌈4/k⌉ and compare it to k².

`k`	`⌈3/k⌉`	`⌈2/k⌉`	`⌈4/k⌉`	Total ops	`k²`	`Total <= k²`?
1	3	2	4	9	1	F (9 > 1)
2	2	1	2	5	4	F (5 > 4)
3	1	1	2	4	9	T (4 <= 9)
4	1	1	1	3	16	T (3 <= 16)

Notice the monotonic "false then true" pattern: F, F, T, T, .... The answer is the first T, which occurs at k = 3.

Now let's see how binary search finds this efficiently:

We track the boundaries [l, r] as they shrink. (The range starts at [1, 100000], but the interesting action happens near the boundary, so we focus on the final steps once the range narrows.)

Eventually the search range narrows to l = 1, r = 3 (after several iterations halving the large initial range, all of which push l upward since small k fail).
Iteration: mid = (1 + 3) >> 1 = 2.
- check(2): total ops = 5, k² = 4. Since 5 <= 4 is False, we move l = mid + 1 = 3.
Now l = 3, r = 3, so l == r and the loop ends.

Result: We return l = 3. ✅

This matches our manual analysis. Binary search avoided checking every single value up to 10^5 by repeatedly halving the range, and zeroed in on the boundary where the condition flips from false to true.

Solution Implementation

1from typing import List
2from math import ceil
3
4
5class Solution:
6    def minimumK(self, nums: List[int]) -> int:
7        # Check whether a given value `k` satisfies the condition:
8        # the sum of ceil(x / k) for all x in nums must not exceed k * k.
9        def check(k: int) -> bool:
10            total = 0
11            for num in nums:
12                # ceil(num / k); using integer arithmetic to avoid float errors
13                total += (num + k - 1) // k
14            return total <= k * k
15
16        # Binary search for the smallest k that makes check(k) return True.
17        # The predicate is monotonic: once it becomes True, it stays True
18        # for all larger k, so we can binary search the boundary.
19        left, right = 1, 10**5
20        while left < right:
21            mid = (left + right) >> 1
22            if check(mid):
23                # `mid` works, so the answer is at most `mid`.
24                right = mid
25            else:
26                # `mid` is too small, search the right half.
27                left = mid + 1
28
29        # `left` now points to the minimal valid k.
30        return left
31

1class Solution {
2    public int minimumK(int[] nums) {
3        // Binary search range for the candidate value k.
4        int left = 1, right = 100000;
5        // Lower-bound binary search: find the smallest k that satisfies check().
6        while (left < right) {
7            int mid = (left + right) >> 1;
8            if (check(nums, mid)) {
9                // mid is valid; it may still be reducible, keep it in range.
10                right = mid;
11            } else {
12                // mid is too small; search the upper half.
13                left = mid + 1;
14            }
15        }
16        return left;
17    }
18
19    // Returns true if the sum of ceil(x / k) over all elements does not exceed k * k.
20    private boolean check(int[] nums, int k) {
21        long total = 0;
22        for (int x : nums) {
23            // Ceiling division of x by k.
24            total += (x + k - 1) / k;
25        }
26        // Use long multiplication to prevent int overflow on k * k.
27        return total <= 1L * k * k;
28    }
29}
30

1class Solution {
2public:
3    int minimumK(vector<int>& nums) {
4        // Predicate: returns true if the candidate value `k` satisfies the
5        // constraint. For a given k, sum up ceil(x / k) over all elements and
6        // check whether this total does not exceed k * k.
7        auto isFeasible = [&](int k) -> bool {
8            long long total = 0;
9            for (int value : nums) {
10                // Compute ceil(value / k) using integer arithmetic.
11                total += (value + k - 1) / k;
12            }
13            // Use 1LL to promote the multiplication to long long and avoid overflow.
14            return total <= 1LL * k * k;
15        };
16
17        // Binary search for the smallest k in [left, right] that is feasible.
18        int left = 1, right = 1e5;
19        while (left < right) {
20            // Avoid potential overflow when computing the midpoint.
21            int mid = left + (right - left) / 2;
22            if (isFeasible(mid)) {
23                // mid works, so the answer could be mid or smaller.
24                right = mid;
25            } else {
26                // mid is too small, search in the upper half.
27                left = mid + 1;
28            }
29        }
30        // left == right now holds the minimum feasible value.
31        return left;
32    }
33};
34

1/**
2 * Finds the minimum value of k such that, when each element of nums is
3 * distributed into groups of size k, the total number of groups needed
4 * does not exceed k * k.
5 *
6 * Uses binary search on the answer k, leveraging the monotonic property
7 * of the feasibility check.
8 *
9 * @param nums - The input array of positive integers.
10 * @returns The smallest valid k.
11 */
12function minimumK(nums: number[]): boolean | number {
13    /**
14     * Checks whether a given candidate k satisfies the constraint.
15     *
16     * For each number x, ceil(x / k) groups of size k are required.
17     * The candidate is valid if the sum of all required groups is at
18     * most k * k.
19     *
20     * @param k - The candidate value to validate.
21     * @returns True if k satisfies the constraint, otherwise false.
22     */
23    const check = (k: number): boolean => {
24        let total = 0;
25        for (const x of nums) {
26            // Equivalent to Math.ceil(x / k), the number of groups for x.
27            total += Math.floor((x + k - 1) / k);
28        }
29        return total <= k * k;
30    };
31
32    // Binary search bounds for the smallest feasible k.
33    let left = 1;
34    let right = 100000;
35    while (left < right) {
36        // Midpoint, using a right shift to avoid potential overflow.
37        const mid = (left + right) >> 1;
38        if (check(mid)) {
39            // mid works, so search the lower half (inclusive of mid).
40            right = mid;
41        } else {
42            // mid is too small, search the upper half.
43            left = mid + 1;
44        }
45    }
46    return left;
47}
48

Time and Space Complexity

The time complexity is O(n × log M), and the space complexity is O(1). Here, n and M are the length of the array nums and the maximum range of the binary search respectively.

The algorithm uses binary search over the range [1, 10^5], which takes O(log M) iterations. In each iteration, the check function traverses the entire array nums once, costing O(n). Therefore, the total time complexity is O(n × log M).

The space complexity is O(1) since only a constant amount of extra space is used for variables such as l, r, mid, and t.

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Setting the upper bound `r` too low

The most dangerous mistake is choosing an upper bound for binary search that is too small. While 10**5 works for typical constraints, the validity of this bound depends entirely on the maximum possible value of nums[i] and the length of the array. If the inputs are large enough, the true answer could exceed 10**5, and the binary search would silently return a wrong (too-small) value because it never explores beyond r.

Why it happens: The condition is sum(ceil(x / k)) <= k². In the worst case, every element contributes at least 1 operation, so the left side is at least n (the array length). For the condition to hold, you minimally need k² >= n, i.e. k >= sqrt(n). But more importantly, a single large element x contributes ceil(x / k) operations, so you need k² to dominate roughly n * max(nums) / k, giving k³ >= n * max(nums) as a rough threshold.

Solution: Derive a provably safe upper bound from the input rather than hard-coding a magic number.

class Solution:
    def minimumK(self, nums: List[int]) -> int:
        def check(k: int) -> bool:
            total = 0
            for num in nums:
                total += (num + k - 1) // k
            return total <= k * k

        n = len(nums)
        mx = max(nums)

        # Safe upper bound: we always need at least k operations summed,
        # and each element adds at most ceil(mx / k). A bound that
        # guarantees feasibility is where k*k >= n * ceil(mx / k),
        # so k around (n * mx) ** (1/3) plus a margin. Using max(mx, n)+1
        # as a conservative bound also works since ceil(x/k)=1 once k>=mx.
        right = max(mx, n) + 1
        left = 1

        while left < right:
            mid = (left + right) >> 1
            if check(mid):
                right = mid
            else:
                left = mid + 1
        return left

When k >= mx, every ceil(num / k) equals 1, so the sum is exactly n, and the condition becomes n <= k². Since right = max(mx, n) + 1, both n <= k² and mx <= k are guaranteed satisfied at the boundary, making it a provably valid upper bound.

Pitfall 2: Using floating-point ceiling division

A tempting but error-prone approach is computing the ceiling with math.ceil(num / k) or int(num / k) + ... using floating-point arithmetic.

Why it happens: Floating-point division introduces rounding errors. For large integers, num / k may not be represented exactly, causing math.ceil to return a value off by one (e.g., a perfect division like 10**16 / 10**8 might yield 99999999.9999 and round incorrectly).

Solution: Always use the integer trick (num + k - 1) // k, which is exact for all positive integers and avoids any floating-point representation issues. The provided solution already does this correctly—just resist the urge to "simplify" it with math.ceil.

Pitfall 3: Misreading the predicate's monotonicity direction

Binary search relies on the predicate switching from False to True exactly once as k grows. A common error is assuming check is monotonic without verifying it, or flipping the boundary update logic (left = mid vs right = mid).

Why it happens: As k increases, the left side sum(ceil(x / k)) is non-increasing (fewer operations per element), while the right side k² is strictly increasing. So once the condition holds, it continues to hold—the predicate is monotonic in the False → True direction. Confusing this leads to updating the wrong boundary.

Solution: Keep the template consistent: when check(mid) is True, shrink toward smaller k with right = mid; otherwise left = mid + 1. Verify monotonicity explicitly before trusting binary search, and confirm that right is large enough that check(right) is True (guaranteed by Pitfall 1's fix), otherwise the loop returns an invalid left.

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?

dp[i] = dp[i] + 1

dp[i] = dp[i] + dp[i - 1]

dp[i] = (dp[i] + dp[j] + 1) for j in 0 to i

dp[i] = max(dp[i], dp[j] + 1) for j in 0 to i

I don't know

Core Learning

LLD/OOP Interview

Additional Resources

AI Engineering