#3065

Easy

auto_awesomeArray-driven solution strategy

LeetCode Problem Workspace

Minimum Operations to Exceed Threshold Value I

Count how many numbers are below k, because each such value must be removed in Minimum Operations to Exceed Threshold Value I.

array

Problem Statement

You get a 0-indexed integer array nums and an integer k. One move lets you delete one occurrence of the current smallest value in the array. Your goal is to find the fewest moves required until every remaining element is at least k.

Because each operation always targets the smallest element, the process keeps stripping away values that are still below the threshold. For nums = [2,11,10,1,3] and k = 10, the values 1, 2, and 3 are the only blockers, so the answer is 3. If every value already meets the threshold, like k = 1 for [1,1,2,4,9], the answer is 0.

Examples

Example 1

Input: nums = [2,11,10,1,3], k = 10

Output: 3

After one operation, nums becomes equal to [2, 11, 10, 3]. After two operations, nums becomes equal to [11, 10, 3]. After three operations, nums becomes equal to [11, 10]. At this stage, all the elements of nums are greater than or equal to 10 so we can stop. It can be shown that 3 is the minimum number of operations needed so that all elements of the array are greater than or equal to 10.

Example 2

Input: nums = [1,1,2,4,9], k = 1

Output: 0

All elements of the array are greater than or equal to 1 so we do not need to apply any operations on nums.

Example 3

Input: nums = [1,1,2,4,9], k = 9

Output: 4

only a single element of nums is greater than or equal to 9 so we need to apply the operations 4 times on nums.

Constraints

1 <= nums.length <= 50
1 <= nums[i] <= 109
1 <= k <= 109
The input is generated such that there is at least one index i such that nums[i] >= k.

Solution Approach

Reduce the operation rule to a counting rule

The smallest element is always removed first, so any value below k will eventually be deleted before the array can satisfy the condition. Values already greater than or equal to k never need to be touched. That means the minimum operations equal the number of elements less than k.

Scan the array once

Iterate through nums and keep a counter for elements where num < k. This matches the exact failure mode in this problem: a value below the threshold keeps the array invalid until it is removed. No sorting, heap, or repeated deletion simulation is required.

Return the counter

After the scan, the counter is the answer. On nums = [2,11,10,1,3] with k = 10, the values below k are 2, 1, and 3, so the result is 3. On nums = [1,1,2,4,9] with k = 9, four values are below 9, so four removals are necessary.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The array is visited once, so the time complexity is O(n). The algorithm uses only a single counter besides the input, so the space complexity is O(1). This is better than simulating repeated smallest removals because the operation order does not change the fact that every value below k must be removed.

What Interviewers Usually Probe

Notice that the operation always removes the current minimum, so ask whether simulation is actually necessary.
A strong solution explains why counting num < k is equivalent to counting required deletions.
The key insight is proving that elements already at least k never block the answer for this problem.

Common Pitfalls or Variants

Common pitfalls

Sorting the array first adds extra work even though the answer depends only on how many values are below k.
Using <= k instead of < k is wrong because values equal to k already satisfy the threshold.
Simulating removals can hide the simple invariant that every below-threshold element must be deleted exactly once.

Follow-up variants

What changes if the operation can remove any element, not just the smallest, before all values reach k?
How would the approach differ in Minimum Operations to Exceed Threshold Value II, where elements are combined instead of simply removed?
What if you had to return the actual removed values in order rather than only the minimum count?

FAQ

What is the main pattern in Minimum Operations to Exceed Threshold Value I?

The pattern is a direct array count. Since each move removes the smallest value, the answer is simply the number of elements in nums that are less than k.

Why does counting values below k give the minimum number of operations?

Any value below k keeps the array invalid, and the allowed operation eventually removes it because smaller values are always deleted first. Each such value must disappear once, so the count is both necessary and sufficient.

Do I need sorting or a min-heap for LeetCode 3065?

No. Sorting or heap operations simulate the removal order, but this problem only asks for the minimum count. The order does not change how many below-threshold elements must be removed.

What happens when k is already small enough for every element?

Then the answer is 0. During the scan, no element satisfies num < k, so no operation is needed.

What is the exact time and space complexity for this solution?

The solution runs in O(n) time because it scans the array once, and it uses O(1) extra space because it only stores a counter.

terminal

Solution

Solution 1: Traversal and Counting

We only need to traverse the array once, counting the number of elements less than $k$.

1

2

3

class Solution:
    def minOperations(self, nums: List[int], k: int) -> int:
        return sum(x < k for x in nums)

Continue Practicing

#3066 minimum operations to exceed threshold value ii #3067 count pairs of connectable servers in a weighted tree network #3068 find the maximum sum of node values