Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Make and follow sheets.Sign in

Minimum K to Reduce Array Within Limit solution and explanation

MediumArrayBinary Search4 min read41.1% acceptanceUpdated 24 Mar 2026
Asked atGoogle
Practise Minimum K to Reduce Array Within Limit
16:35
Minimum K to Reduce Array Within Limit 🔥 LeetCode 3824 | Biweekly Contest 175 | Binary Search + Math Study Placement · 16:35 · 264 viewsWatch on YouTube
9 more videos on this problem
  1. Minimum K to Reduce Array Within Limit 🔥 LeetCode 3824 | Biweekly Contest 175 | Binary Search + Math Study Placement · 16:35 · 264 views
  2. 3824. Minimum K to Reduce Array Within Limit | Biweekly Contest 175 | LeetcodeRapid Syntax · 20:55 · 245 views
  3. Biweekly Contest 175 - Leetcode 3824. Minimum K to Reduce Array Within LimitCode Maestro Rtj · 8:47 · 148 views
  4. Leetcode 3824 | Minimum K to Reduce Array Within LimitCodeWithMeGuys · 8:44 · 124 views
  5. 3824. Minimum K to Reduce Array Within Limit | Leetcode Biweekly Contest 175Let's Aim FAANG · 21:05 · 112 views
  6. LeetCode Problem 3824 | Minimum K to Reduce Array Within LimitRepovive TV · 10:38 · 68 views
  7. LeetCode 3823 & 3824 | Reverse Letters + Special Characters & Minimum K to Reduce ArrayProof2Code · 16:41 · 35 views
  8. LeetCode 3824 | Minimum K to Reduce Array Within Limit | Binary Search on Answer (Explained)Coding with U · 11:14 · 34 views
  9. LeetCode 3824 | Minimum K to Reduce Array Within Limit || Java | AC | Biweekly | GuideSolo Dev · 1:00 · 24 views
  10. 3824. Minimum K to Reduce Array Within Limit | Bi Weekly 175 | Leetcodecodemintt · 13:13 · 15 views

The problem

You are given a positive integer array nums.

For a positive integer k, define nonPositive(nums, k) as the minimum number of operations needed to make every element of nums non-positive. In one operation, you can choose an index i and reduce nums[i] by k.

Return an integer denoting the minimum value of k such that nonPositive(nums, k) <= k2.

Example 1:

Input: nums = [3,7,5]

Output: 3

Explanation:

When k = 3, nonPositive(nums, k) = 6 <= k2.

  • Reduce nums[0] = 3 one time. nums[0] becomes 3 - 3 = 0.
  • Reduce nums[1] = 7 three times. nums[1] becomes 7 - 3 - 3 - 3 = -2.
  • Reduce nums[2] = 5 two times. nums[2] becomes 5 - 3 - 3 = -1.

Example 2:

Input: nums = [1]

Output: 1

Explanation:

When k = 1, nonPositive(nums, k) = 1 <= k2.

  • Reduce nums[0] = 1 one time. nums[0] becomes 1 - 1 = 0.

Constraints:

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 105

Approach overview

Problem Overview: You are given an integer array and a limit on the number of operations allowed to reduce it. Each operation reduces an element by up to k. The goal is to find the minimum value of k such that the entire array can be reduced within the allowed limit of operations.

Approach 1: Linear Search on k (O(n * M) time, O(1) space)

Start from k = 1 and keep increasing it until the required number of operations becomes less than or equal to the allowed limit. For each candidate k, iterate through the array and compute how many operations each element requires using a ceiling-style division like ceil(nums[i] / k). Sum the operations and check if it stays within the limit. This method is easy to reason about but inefficient because k may need to be tested up to the maximum value in the array.

Approach 2: Binary Search on k (O(n log M) time, O(1) space)

The key observation is monotonic behavior: if a certain k allows the array to be reduced within the limit, any larger k will also work because each operation removes more value. This makes the answer searchable using Binary Search. Set the search range from 1 to max(nums). For each midpoint k, iterate through the array and calculate the total operations required using (num + k - 1) / k. If the total operations exceed the limit, increase k. Otherwise, try a smaller k to find the minimum valid value.

The feasibility check runs in O(n), and binary search performs log M iterations where M is the maximum element in the array. This produces an overall complexity of O(n log M) with constant extra space.

Recommended for interviews: The Binary Search approach. Interviewers expect you to recognize the monotonic relationship between k and the number of operations required. Demonstrating the brute-force reasoning first shows understanding of the constraint, while converting it into a binary search over the answer shows strong problem-solving skill.

Solution

We notice that as k increases, it becomes easier to satisfy the condition. This exhibits monotonicity, so we can use binary search to find the minimum k.

We define the left boundary of the binary search as l = 1 and the right boundary as r = 10^5. In each binary search iteration, we calculate the middle value mid = \lfloor (l + r) / 2 \rfloor and determine whether the condition nonPositive(nums, k) leq k^2 is satisfied when k = mid. If the condition is satisfied, we update the right boundary to r = mid; otherwise, we update the left boundary to l = mid + 1. When the binary search ends, the left boundary l is the minimum k we are looking for.

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

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

        l, r = 1, 10**5
        while l < r:
            mid = (l + r) >> 1
            if check(mid):
                r = mid
            else:
                l = mid + 1
        return l
class Solution {
    public int minimumK(int[] nums) {
        int l = 1, r = 100000;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (check(nums, mid)) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }

    private boolean check(int[] nums, int k) {
        long t = 0;
        for (int x : nums) {
            t += (x + k - 1) / k;
        }
        return t <= 1L * k * k;
    }
}
class Solution {
public:
    int minimumK(vector<int>& nums) {
        auto check = [&](int k) -> bool {
            long long t = 0;
            for (int x : nums) {
                t += (x + k - 1) / k;
            }
            return t <= 1LL * k * k;
        };

        int l = 1, r = 1e5;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (check(mid)) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }
};
function minimumK(nums: number[]): number {
    const check = (k: number): boolean => {
        let t = 0;
        for (const x of nums) {
            t += Math.floor((x + k - 1) / k);
        }
        return t <= k * k;
    };

    let l = 1,
        r = 100000;
    while (l < r) {
        const mid = (l + r) >> 1;
        if (check(mid)) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    return l;
}
func minimumK(nums []int) int {
	check := func(k int) bool {
		t := 0
		for _, x := range nums {
			t += (x + k - 1) / k
		}
		return t <= k*k
	}

	return sort.Search(100000, func(k int) bool {
		if k == 0 {
			return false
		}
		return check(k)
	})
}
Try this approach in the editor

Complexity analysis

ApproachTimeSpaceWhen to Use
Linear Search on kO(n * M)O(1)Useful for reasoning about the problem or when the maximum value in the array is very small
Binary Search on AnswerO(n log M)O(1)General case; optimal when k lies within a large numeric range

Frequently asked questions

Is Minimum K to Reduce Array Within Limit easy or hard?

The problem is typically considered Medium difficulty. The main challenge is recognizing that the answer space for k is monotonic and can be searched with binary search, reducing the complexity from a potentially large brute-force search to O(n log M).

Minimum K to Reduce Array Within Limit Python/Java solution

Implement binary search between 1 and the maximum element of the array. For each midpoint k, iterate through the array and accumulate required operations using ceiling division. If the operations exceed the limit, move the left boundary; otherwise store the result and shrink the right boundary.

How to solve Minimum K to Reduce Array Within Limit in O(n log M)?

Use binary search over the value of k. For each candidate k, iterate through the array and compute how many operations each element needs using ceiling division such as (num + k - 1) / k. If the total operations exceed the allowed limit, increase k; otherwise continue searching for a smaller valid k.

What is the best approach for Minimum K to Reduce Array Within Limit?

Binary search on the answer is the most efficient approach. The number of operations required decreases as k increases, which creates a monotonic search space. By checking feasibility for each candidate k and adjusting the search range, you find the minimum valid k in O(n log M) time where M is the maximum element in the array.

Is Minimum K to Reduce Array Within Limit asked at Google/Amazon/Meta?

Problems that use binary search on the answer are common in interviews at companies like Google, Amazon, and Meta. Variants appear frequently in coding interviews because they test recognition of monotonic conditions and efficient feasibility checks.

What data structure is used in Minimum K to Reduce Array Within Limit?

The solution mainly uses a simple array traversal combined with binary search on a numeric range. No complex data structures are required; the algorithm repeatedly scans the array to compute how many operations are needed for a given k.

What is the time complexity of Minimum K to Reduce Array Within Limit?

The optimal solution runs in O(n log M) time. Each binary search step checks the array once to compute the number of required operations, which costs O(n). The binary search itself runs for log M iterations where M is the maximum value in the array.

Comments

Now write it yourselfClose this page and solve Minimum K to Reduce Array Within Limit in the editor, without looking.
Practise Minimum K to Reduce Array Within Limit