Minimum Operations to Exceed Threshold Value I

Easy
986.

Minimum Operations to Exceed Threshold Value I

Minimum Operations to Exceed Threshold Value I is an easy coding problem on arrays, asked in Amazon, Google and HCL interviews.

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.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var minOperations = function(nums, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimum Operations to Exceed Threshold Value I — Solution

Minimum Operations to Exceed Threshold Value I solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Minimum Operations to Exceed Threshold Value I is an easy coding problem on arrays, asked in Amazon, Google and HCL interviews.

  • 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.

Hints for Minimum Operations to Exceed Threshold Value I

  1. Hint 1

    Removing the smallest repeatedly removes exactly the elements below k.

  2. Hint 2

    Their order does not matter.

  3. Hint 3

    So the answer is simply how many elements are below 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)

Java

public static int minOperations(int[] nums, int k) {
    int count = 0;
    for (int v : nums) if (v < k) count++;
    return count;
}

C++

int minOperations(vector<int>& nums, int k) {
    int count = 0;
    for (int v : nums) if (v < k) count++;
    return count;
}

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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays