#3375

Easy

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Minimum Operations to Make Array Values Equal to K

Find the minimum operations to convert an array to all values equal k using array scanning and hash lookup efficiently.

Problem Statement

You are given an integer array nums and an integer k. In each operation, you can choose a valid integer h such that all numbers strictly greater than h are identical, then reduce all those numbers to h.

Return the minimum number of operations needed to make all elements in nums equal to k. If it is impossible to reach k due to elements less than k or conflicting values, return -1.

Examples

Example 1

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

Output: 2

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

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

Example 3

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

Output: 4

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

Solution Approach

Scan the Array and Count Frequencies

Iterate through nums and record the frequency of each value using a hash table. This allows quick lookup to identify which integers are valid for reduction in each operation, matching the pattern of array scanning plus hash lookup.

Identify Valid Integers for Each Step

From the maximum value down to k, select the highest integer h where all numbers above h are equal. Reduce these numbers in one operation and increment the operation count. Repeat this until all numbers equal k or return -1 if impossible.

Check for Impossibility

At any step, if a number less than k exists in nums or a conflict prevents choosing a valid integer, immediately return -1. This failure mode is common when array values cannot be aligned using the allowed reductions.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(n)

Time complexity is O(n) because each element is scanned once and hash lookups are O(1). Space complexity is O(n) to store frequency counts for each unique number in nums.

What Interviewers Usually Probe

Are you correctly identifying the valid integer h at each step?
Can you explain why some sequences cannot reach k and must return -1?
How do you optimize the scanning to avoid redundant checks for already reduced numbers?

Common Pitfalls or Variants

Common pitfalls

Ignoring elements less than k which make the task impossible.
Failing to update frequencies correctly after each reduction.
Confusing the order of operations when multiple valid integers exist.

Follow-up variants

Find minimum operations when multiple arrays are given and each needs to reach its own target k.
Modify the problem to allow decreasing numbers to any smaller integer instead of only valid integers.
Calculate maximum operations instead of minimum using the same pattern of array scanning and hash lookup.

FAQ

What is the minimum operations approach for this array scanning plus hash lookup problem?

Scan the array to count frequencies, identify the highest valid integer at each step, reduce numbers, and repeat until all values reach k or return -1 if impossible.

Why do we return -1 in some cases?

If nums contains values less than k or elements cannot be aligned using valid reductions, the operations cannot succeed, so -1 signals impossibility.

How do hash tables help in this problem?

Hash tables efficiently track frequencies of numbers, allowing quick identification of valid integers for each reduction step.

Can we perform operations in any order?

No, operations must reduce numbers from the highest valid integer down to k to ensure the minimum number of steps.

Does this method work for arrays of any size up to the constraint?

Yes, the approach scales linearly with n and handles arrays up to length 100, matching the problem constraints.

terminal

Solution

Solution 1: Hash Table

According to the problem description, we can choose the second largest value in the current array as the valid integer $h$ each time, and change all numbers greater than $h$ to $h$. This minimizes the number of operations. Additionally, since the operation reduces the numbers, if there are numbers in the current array smaller than $k$, we cannot make all numbers equal to $k$, so we directly return -1.

1

2

3

4

5

6

7

8

9

10

class Solution:
    def minOperations(self, nums: List[int], k: int) -> int:
        s = set()
        mi = inf
        for x in nums:
            if x < k:
                return -1
            mi = min(mi, x)
            s.add(x)
        return len(s) - int(k == mi)

Continue Practicing

#3378 count connected components in lcm graph #3371 identify the largest outlier in an array #3381 maximum subarray sum with length divisible by k