Minimum Operations to Make Array Values Equal to K

Easy
1823.

Minimum Operations to Make Array Values Equal to K

Minimum Operations to Make Array Values Equal to K is an easy coding problem on arrays and hash table, asked in Amazon and Google interviews.

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

Call an integer h valid if every element of nums that is strictly greater than h has the same value. (For nums = [10,8,10,8], h = 9 is valid because every element above 9 is 10, but h = 5 is not.)

In one operation you choose a valid h and set every element greater than h to h.

Return the minimum number of operations needed to make every element equal to k, or -1 if it cannot be done.

Example 1

Input
nums = [6,3,6,4], k = 3
Output
2
Explanation
Lower the `6`s to `4` (h = 4 is valid), then lower the `4`s to `3`.

Example 2

Input
nums = [4,1,4], k = 2
Output
-1
Explanation
Operations only lower values, so the `1` can never become `2`.

Example 3

Input
nums = [7,7,7], k = 7
Output
0

Constraints

  • 1 <= nums.length <= 100
  • 1 <= nums[i] <= 100
  • 1 <= k <= 100
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 Make Array Values Equal to K Solution

Minimum Operations to Make Array Values Equal to K solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Minimum Operations to Make Array Values Equal to K is an easy coding problem on arrays and hash table, asked in Amazon and Google interviews.

  • Difficulty: Easy
  • Topics: Arrays, Hash Table
  • Asked at: Amazon, Google
  • 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

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

Call an integer h valid if every element of nums that is strictly greater than h has the same value. (For nums = [10,8,10,8], h = 9 is valid because every element above 9 is 10, but h = 5 is not.)

In one operation you choose a valid h and set every element greater than h to h.

Return the minimum number of operations needed to make every element equal to k, or -1 if it cannot be done.

Example 1

Input: nums = [6,3,6,4], k = 3
Output: 2
Explanation: Lower the `6`s to `4` (h = 4 is valid), then lower the `4`s to `3`.

Example 2

Input: nums = [4,1,4], k = 2
Output: -1
Explanation: Operations only lower values, so the `1` can never become `2`.

Example 3

Input: nums = [7,7,7], k = 7
Output: 0

Constraints

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

Hints for Minimum Operations to Make Array Values Equal to K

  1. Hint 1

    An operation can only decrease values. What does that say about an element already below k?

  2. Hint 2

    A valid h can only touch the elements equal to the current maximum, and the best it can do is bring them down to the next distinct value (or to k).

  3. Hint 3

    So every distinct value above k costs exactly one operation.

How to solve Minimum Operations to Make Array Values Equal to K

Since h is valid only when everything above it is one value, each operation can flatten just the current maximum level. Each distinct value greater than k therefore needs its own operation, and lowering to the next distinct value achieves exactly that count.

Approach

  1. If any element is smaller than k, return -1 — nothing can raise it.
  2. Otherwise collect the distinct values strictly greater than k in a set.
  3. Return the size of that set.

Why it works

Each operation merges the top level into a lower one, reducing the number of distinct values above k by at most one — any lower h would have two different values above it and be invalid. Choosing h as the next distinct value (or k for the last level) achieves a reduction of exactly one each time, so the count of distinct values above k is both a lower bound and achievable.

Complexity

  • Time — O(n)
  • Space — O(V) with V = 100 possible values

Pitfalls

  • Count distinct values above k, not elements.
  • Values equal to k need no operation; values below k make the task impossible.

Reference solution

Python

from typing import List

def minOperations(nums: List[int], k: int) -> int:
    if min(nums) < k:
        return -1
    return len({v for v in nums if v > k})

Java

public static int minOperations(int[] nums, int k) {
    boolean[] seen = new boolean[101];
    int distinct = 0;
    for (int v : nums) {
        if (v < k) return -1;
        if (v > k && !seen[v]) {
            seen[v] = true;
            distinct++;
        }
    }
    return distinct;
}

C++

int minOperations(vector<int>& nums, int k) {
    vector<bool> seen(101, false);
    int distinct = 0;
    for (int v : nums) {
        if (v < k) return -1;
        if (v > k && !seen[v]) {
            seen[v] = true;
            distinct++;
        }
    }
    return distinct;
}

JavaScript

var minOperations = function(nums, k) {
    var seen = {};
    var distinct = 0;
    for (var i = 0; i < nums.length; i++) {
        var v = nums[i];
        if (v < k) return -1;
        if (v > k && !seen[v]) {
            seen[v] = true;
            distinct++;
        }
    }
    return distinct;
};

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 · Hashing: Hash Maps and Hash Sets