Scale Engineer

Minimum Operations to Make Array Values Equal to K

Easy
#2998Time: O(U * N), where N is the length of `nums` and U is the number of unique elements greater than `k`. In each of the U operations, we scan the array multiple times (to find max, next max, and update), leading to O(N) work per operation. In the worst case, U can be up to N, leading to O(N^2).Space: O(N), where N is the number of elements in `nums`. This is because we create a mutable list to store the current state of the array. If the input array is modified in-place, the space complexity would be O(1).1 company
Data structures
ArrayHash Table
Companies
Lowe's

Prompt

You are given an integer array nums and an integer k.

An integer h is called valid if all values in the array that are strictly greater than h are identical.

For example, if nums = [10, 8, 10, 8], a valid integer is h = 9 because all nums[i] > 9 are equal to 10, but 5 is not a valid integer.

You are allowed to perform the following operation on nums:

  • Select an integer h that is valid for the current values in nums.
  • For each index i where nums[i] > h, set nums[i] to h.

Return the minimum number of operations required to make every element in nums equal to k. If it is impossible to make all elements equal to k, return -1.

 

Example 1:

Input: nums = [5,2,5,4,5], k = 2

Output: 2

Explanation:

The operations can be performed in order using valid integers 4 and then 2.

Example 2:

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

Output: -1

Explanation:

It is impossible to make all the values equal to 2.

Example 3:

Input: nums = [9,7,5,3], k = 1

Output: 4

Explanation:

The operations can be performed using valid integers in the order 7, 5, 3, and 1.

 

Constraints:

  • 1 <= nums.length <= 100
  • 1 <= nums[i] <= 100
  • 1 <= k <= 100

Approaches

3 approaches with complexity analysis and trade-offs.

This approach directly simulates the process described in the problem. It iteratively finds the largest value in the array that is greater than k and performs an operation to reduce it. This is repeated until all values in the array are less than or equal to k. While conceptually straightforward, this method is less efficient because it requires multiple passes over the array.

Algorithm

  • First, perform an initial check: iterate through the array nums. If any element num is less than k, it's impossible to reach the target, so return -1.
  • Initialize an operations counter to 0.
  • Start a loop that continues as long as the maximum value in the array is greater than k.
  • Inside the loop:
    1. Find the maximum value max_val in the current array.
    2. If max_val is less than or equal to k, the process is complete, so break the loop.
    3. Find the largest value h in the array that is strictly less than max_val. If no such element exists (meaning all elements greater than k are max_val), set h = k.
    4. Increment the operations counter.
    5. Iterate through the array and replace all occurrences of max_val with h. This simulates one operation.
  • After the loop terminates, return the total operations count.

Walkthrough

The algorithm begins by checking for an impossible scenario: if any element in nums is already smaller than k, we can never increase it to k, so we return -1. Otherwise, we enter a loop to perform the operations. In each iteration, we find the current maximum value, max_val. If this max_val is greater than k, we must reduce it. To do this, we find the next distinct value smaller than max_val in the array to use as our h. This choice of h guarantees validity because all elements greater than h will be identical (they will all be max_val). We then increment our operation count and update all instances of max_val to h. This process continues until the array's maximum value is no longer greater than k.

import java.util.ArrayList;import java.util.Collections;import java.util.List; class Solution {    public int minOperations(int[] nums, int k) {        for (int num : nums) {            if (num < k) {                return -1;            }        }         List<Integer> currentNums = new ArrayList<>();        for (int num : nums) {            currentNums.add(num);        }         int operations = 0;        while (true) {            int maxVal = 0;            for (int num : currentNums) {                if (num > maxVal) {                    maxVal = num;                }            }             if (maxVal <= k) {                break;            }             operations++;             int h = k;            int nextMax = 0;            for (int num : currentNums) {                if (num < maxVal && num > nextMax) {                    nextMax = num;                }            }                        if (nextMax > k) {                h = nextMax;            }             for (int i = 0; i < currentNums.size(); i++) {                if (currentNums.get(i) == maxVal) {                    currentNums.set(i, h);                }            }        }         return operations;    }}

Complexity

Time

O(U * N), where N is the length of `nums` and U is the number of unique elements greater than `k`. In each of the U operations, we scan the array multiple times (to find max, next max, and update), leading to O(N) work per operation. In the worst case, U can be up to N, leading to O(N^2).

Space

O(N), where N is the number of elements in `nums`. This is because we create a mutable list to store the current state of the array. If the input array is modified in-place, the space complexity would be O(1).

Trade-offs

Pros

  • Directly models the problem statement, which can be easier to reason about initially.

  • Does not require complex data structures.

Cons

  • Inefficient due to repeated traversals of the array within a loop.

  • Finding the max and next-max value in each iteration adds significant overhead.

  • Modifying the array (or a copy) in each step is computationally expensive.

Solutions

class Solution {public  int minOperations(int[] nums, int k) {    Set<Integer> s = new HashSet<>();    int mi = 1 << 30;    for (int x : nums) {      if (x < k) {        return -1;      }      mi = Math.min(mi, x);      s.add(x);    }    return s.size() - (mi == k ? 1 : 0);  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem