Minimum Operations to Make Array Values Equal to K

Minimum Operations to Make Array Values Equal to K - Problem

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] = 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.

Input & Output

Example 1 — Basic Case

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

› Output: 1

💡 Note: Initially nums = [2,1,2]. Since 1 < 2, this should return -1. Let me fix: nums = [5,2,5,4], k = 2. Unique values: [5,4,2]. Need to reduce 5→4, then 4→2. Answer: 2 operations.

Example 2 — Already Equal

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

› Output: 0

💡 Note: All elements already equal k=2, so no operations needed.

Example 3 — Impossible Case

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

› Output: -1

💡 Note: Some elements (1,2,3) are less than k=4, so impossible to achieve.

Constraints

1 ≤ nums.length ≤ 10³
1 ≤ nums[i], k ≤ 10³

Visualization

Tap to expand

Asked in

G Google 15 M Microsoft 12

The key insight is that we need to count unique values above k. Each unique value greater than k requires exactly one operation to reduce. The greedy approach works optimally by processing values from largest to smallest. Time: O(n log n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Greedy Approach	O(n log n)	O(n)	Process unique values from largest to smallest, counting necessary operations
Brute Force Simulation	O(2^n)	O(n)	Simulate all possible operations by trying different valid h values

Greedy Approach — Algorithm Steps

Check if k is achievable
Get unique values and sort descending
Count operations needed to reduce each level
Return total operations

Visualization

Tap to expand

Step-by-Step Walkthrough

Sort Unique

Get unique values sorted in descending order

Count Steps

Each unique value > k requires one operation

Result

Total operations needed

Code -

solution.c — C

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

int compare(const void *a, const void *b) {
    return (*(int*)b - *(int*)a);  // Descending order
}

int solution(int* nums, int len, int k) {
    // If any element is less than k, impossible
    for (int i = 0; i < len; i++) {
        if (nums[i] < k) return -1;
    }
    
    // Get unique values
    int unique[1000];
    int uniqueCount = 0;
    
    for (int i = 0; i < len; i++) {
        int found = 0;
        for (int j = 0; j < uniqueCount; j++) {
            if (unique[j] == nums[i]) {
                found = 1;
                break;
            }
        }
        if (!found) {
            unique[uniqueCount++] = nums[i];
        }
    }
    
    // Sort in descending order
    qsort(unique, uniqueCount, sizeof(int), compare);
    
    // If all elements are already k
    if (uniqueCount == 1 && unique[0] == k) {
        return 0;
    }
    
    int operations = 0;
    
    // Process from largest to smallest
    for (int i = 0; i < uniqueCount - 1; i++) {
        int current = unique[i];
        
        if (current > k) {
            operations++;
        }
    }
    
    return operations;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000];
    int len = 0;
    char* ptr = line + 1; // Skip '['
    while (*ptr && *ptr != ']') {
        nums[len++] = atoi(ptr);
        while (*ptr && *ptr != ',' && *ptr != ']') ptr++;
        if (*ptr == ',') ptr++;
    }
    
    int k;
    scanf("%d", &k);
    
    int result = solution(nums, len, k);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

Sorting unique values dominates the time complexity

⚡ Linearithmic

Space Complexity

O(n)

Set to store unique values requires O(n) space

⚡ Linearithmic Space

12.0K Views

Medium Frequency

~15 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

Greedy Approach — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler