Skip to main content
Talentd

Minimum Operations to Exceed Threshold Value I - Solution & Explanation

EasyArray10 min readAsked at: TCS
Practice this problem

Problem Statement

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.

 

Example 1:

Input: nums = [2,11,10,1,3], k = 10
Output: 3
Explanation: 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
Explanation: 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
Explanation: 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.

Approach Overview

Problem Overview: You are given an integer array nums and a threshold value k. One operation removes the smallest element from the array. The goal is to find the minimum number of operations required so that every remaining element in the array is at least k.

Approach 1: Sort and Count (O(n log n) time, O(1) extra space)

This approach sorts the array first, which places the smallest elements at the beginning. After sorting, iterate from the start of the array and count how many values are strictly less than k. Each such element must be removed because it can never satisfy the threshold condition. The moment you encounter a value >= k, you stop counting since all remaining elements will also meet the requirement. Sorting costs O(n log n), and the scan is O(n). This approach is straightforward and works well when modifying the array order is acceptable.

Approach 2: Use a Min-Heap (O(n log n) time, O(n) space)

A min-heap keeps the smallest element accessible at all times. Insert all elements of nums into a heap, then repeatedly check the top element using peek(). If the smallest value is less than k, remove it using poll() and increment the operation count. Continue until the smallest value in the heap becomes >= k or the heap becomes empty. Heap construction takes O(n), while each removal costs O(log n). In the worst case you remove many elements, giving O(n log n) time and O(n) space.

Both approaches rely on identifying values below the threshold. The difference lies in how the smallest element is accessed. Sorting gives a static order and a single linear scan. A heap maintains dynamic ordering and repeatedly exposes the minimum element.

Conceptually, the task is a simple filtering problem over an array. The heap solution introduces a heap data structure, while the first solution relies on sorting to organize elements before counting.

Recommended for interviews: The core insight is that every element smaller than k must be removed. Many candidates immediately sort and count, which clearly demonstrates the idea and runs in O(n log n). Stronger candidates often notice that you can simply iterate once and count elements less than k, achieving O(n) time and O(1) space. Interviewers mainly look for recognition that operations correspond directly to elements below the threshold.

Approach 1: Sort and Count Approach

Sort the array first. Start from the smallest element and keep a count of numbers less than k. Remove these elements until all remaining numbers are >= k, counting the number of operations.

This C solution sorts the array and iterates through it, counting how many elements are less than k. The operation count is the number of elements we need to "remove" to satisfy the condition for all elements >= k.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) if considering in-place sorting; otherwise, it's the space required for the sorting algorithm.

Try this approach in the editor →

Approach 2: Use a Min-Heap

Utilize a min-heap (priority queue) to repeatedly remove the smallest element from the array as long as it is below k. Increment a counter for each removal. This approach can be more efficient for larger datasets, although here n is small.

This Java solution uses a priority queue (min-heap) to efficiently remove the smallest elements. It checks if the top of the queue satisfies the condition, ensuring optimal element removal.

Code

JavaPython

Java

Python

Complexity

Time Complexity: O(n log n) due to heap operations.
Space Complexity: O(n) for storing elements in the heap.

Try this approach in the editor →

Approach 3: Traversal and Counting

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

The time complexity is O(n), where n is the length of the array. The space complexity is O(1).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Sort and Count Approach

Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) if considering in-place sorting; otherwise, it's the space required for the sorting algorithm.

Use a Min-Heap

Time Complexity: O(n log n) due to heap operations.
Space Complexity: O(n) for storing elements in the heap.

Traversal and Counting—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Sort and CountO(n log n)O(1)Simple implementation when modifying array order is fine
Min-HeapO(n log n)O(n)Useful when repeatedly accessing the smallest element dynamically
Linear Scan (Optimal Insight)O(n)O(1)Best when you only need to count values less than k

Video Solution

3065 Minimum Operations to Exceed Threshold Value I || Sorting ✅ || C++ || Java || Python • Ayush Rao • 322 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Minimum Operations to Exceed Threshold Value I easy or hard?
Minimum Operations to Exceed Threshold Value I is classified as an Easy problem. The main skill tested is recognizing that every element below the threshold must be removed, which reduces the task to a straightforward counting operation.
Minimum Operations to Exceed Threshold Value I Python/Java solution
In Python or Java, the simplest implementation loops through the array and increments a counter whenever nums[i] < k. Heap-based versions can use Python's heapq or Java's PriorityQueue to repeatedly remove the smallest element while it remains below k.
How to solve Minimum Operations to Exceed Threshold Value I in O(n)?
Iterate through the array and maintain a counter for values less than k. Every element below the threshold must be removed, so the count directly equals the minimum number of operations. This approach avoids sorting or heap structures and uses constant extra space.
What is the best approach for Minimum Operations to Exceed Threshold Value I?
The most efficient approach is a simple linear scan of the array. Count how many elements are less than k because each such element must be removed. This solution runs in O(n) time and O(1) space and directly reflects the problem requirement.
Is Minimum Operations to Exceed Threshold Value I asked at Google/Amazon/Meta?
Problems involving threshold filtering, counting invalid elements, and basic array scanning are common in interviews at companies like Amazon and Google. While this exact problem may not always appear, the pattern of identifying and removing elements that violate a constraint frequently shows up in coding interviews.
What data structure is used in Minimum Operations to Exceed Threshold Value I?
The problem primarily uses arrays. Some implementations also use a min-heap (priority queue) to repeatedly access the smallest element and remove it until the threshold condition is satisfied.
What is the time complexity of Minimum Operations to Exceed Threshold Value I?
The optimal solution runs in O(n) time by iterating through the array once and counting elements smaller than k. Sorting-based approaches take O(n log n), and heap-based approaches also take O(n log n) due to repeated heap operations.

Ready to solve this problem?

Practice Minimum Operations to Exceed Threshold Value I with our built-in code editor and test cases.

Practice on FleetCode
Previous

Majority Element

Next

Number of Employees Who Met the Target