Minimum Operations to Exceed Threshold Value I

Minimum Operations to Exceed Threshold Value I - Problem

Array Easy

You are given a 0-indexed integer array nums and an integer k.

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

Return the minimum number of operations needed so that all elements of the array are greater than or equal to k.

Input & Output

Example 1 — Basic Case

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

› Output: 3

💡 Note: Elements less than 10 are [2,1,3]. We need to remove all 3 of them, so answer is 3.

Example 2 — All Elements Valid

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

› Output: 0

💡 Note: All elements are already ≥ 1, so no operations needed.

Example 3 — Remove All Elements

$ Input: nums = [2,4,6,8], k = 10

› Output: 4

💡 Note: All elements are less than 10, so we need to remove all 4 elements.

Constraints

1 ≤ nums.length ≤ 50
1 ≤ nums[i] ≤ 10⁹
1 ≤ k ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

Array [2,11,10,1,3] with threshold k=10

Identify

Find elements < k: [2,1,3]

Count

3 operations needed

Key Takeaway

🎯 Key Insight: Count elements below threshold - that's exactly how many operations we need

Asked in

a Amazon 15 G Google 12

The key insight is that we don't need to simulate the removal process. Since we always remove the smallest element, the answer is simply the count of elements less than k. Best approach counts elements in O(n) time with O(1) space.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Simulate Removals	O(n²)	O(1)	Repeatedly find and remove the smallest element until all remaining elements are ≥ k
Optimized - Count Elements Below Threshold	O(n)	O(1)	Simply count how many elements are less than k - that's the answer

Brute Force - Simulate Removals — Algorithm Steps

Step 1: Find the minimum element in current array
Step 2: If min < k, remove it and increment operations
Step 3: Repeat until all elements ≥ k

Visualization

Tap to expand

Step-by-Step Walkthrough

Find Min

Scan array to find smallest element

Check & Remove

If min < k, remove it and count operation

Repeat

Continue until all elements ≥ k

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int solution(int* nums, int size, int k) {
    int operations = 0;
    
    while (size > 0) {
        int minVal = INT_MAX;
        int minIndex = -1;
        
        for (int i = 0; i < size; i++) {
            if (nums[i] < minVal) {
                minVal = nums[i];
                minIndex = i;
            }
        }
        
        if (minVal >= k) break;
        
        // Remove element by shifting
        for (int i = minIndex; i < size - 1; i++) {
            nums[i] = nums[i + 1];
        }
        size--;
        operations++;
    }
    
    return operations;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int nums[1000];
    int size = 0;
    char* token = strtok(line, "[],\n");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != ' ') {
            nums[size++] = atoi(token);
        }
        token = strtok(NULL, "[],\n");
    }
    
    int k;
    scanf("%d", &k);
    
    int result = solution(nums, size, k);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

For each of potentially n removals, we scan the entire array to find minimum

⚠ Quadratic Growth

Space Complexity

O(1)

Only using a few variables, modifying array in-place

✓ Linear Space

12.0K Views

Medium Frequency

~5 min Avg. Time

450 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Simulate Removals — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler