Get started

Minimum Operations to Exceed Threshold Value I — Easy Problem & Solution

In one operation you remove one occurrence of the smallest element of nums.

  • Difficulty: Easy
  • Topics: Arrays
  • Asked at: Amazon, Google, HCL
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

In one operation you remove one occurrence of the smallest element of nums.

Return the minimum number of operations after which every remaining element is greater than or equal to k.

Example 1

Input: nums = [2,11,10,1,3], k = 10
Output: 3
Explanation: Remove 1, 2 and 3.

Example 2

Input: nums = [1,1,2,4,9], k = 1
Output: 0
Explanation: Everything already reaches 1.

Example 3

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

Constraints

  • 1 <= nums.length <= 50
  • 1 <= nums[i] <= 10^9
  • 1 <= k <= 10^9
  • The input is generated so that there is at least one element >= k.

How to solve Minimum Operations to Exceed Threshold Value I

Every element below k must go, and every element at or above k may stay. Since the operation always removes a smallest element, the ones below k are removed first — so the count of them is the answer.

Approach

  1. Count the elements strictly below k.
  2. Return that count.

Why it works

The rule "remove the smallest" never forces the removal of an element at or above k while anything smaller remains, so no operation is ever wasted. That is why no sorting or simulation is needed — the count alone is exact.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • The threshold is >= k, so elements exactly equal to k stay.
  • Sorting and simulating gives the same answer but does more work.
  • The order of removals is irrelevant to the count.

Reference solution

Python

from typing import List

def minOperations(nums: List[int], k: int) -> int:
    return sum(1 for v in nums if v < k)

JavaScript

var minOperations = function(nums, k) {
    var count = 0;
    for (var i = 0; i < nums.length; i++) if (nums[i] < k) count++;
    return count;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue