Facebook Pixel

3422. Minimum Operations to Make Subarray Elements Equal 🔒

Medium
Leetcode Link

Problem Description

You are given an integer array nums and an integer k. You can perform the following operation any number of times:

  • Increase or decrease any element of nums by 1.

Return the minimum number of operations required to ensure that at least one subarray of size k in nums has all elements equal.

Intuition

To solve this problem, we need to transform a subarray of length k into one where all elements are identical, using the fewest operations possible. This can be achieved by considering that transforming a subarray into a single-value subarray is optimally done if all elements turn into the median of those k elements. This is because the median minimizes the sum of absolute deviations, meaning fewer operations to make all numbers in the subarray equal to the median.

Here’s the reasoning for the solution approach:

  1. Ordered Sets for Efficient Access: We use two ordered sets (l and r) to dynamically maintain the left and right parts of the k elements as we slide over the nums array. These sets help in efficiently finding and maintaining the median.

  2. Balancing Arrays: The set l holds the smaller half of the elements, while r holds the larger half. This setup ensures that the median is always easily accessible as the smallest element in r (since the number of elements in l is either the same or one less than in r).

  3. Sliding Window: By iterating over nums and maintaining a window of size k, we update our sets l and r to calculate the cost of making all elements equal to the median, choosing the minimal operations needed as we slide the window.

Using this ordered balancing technique efficiently calculates the minimum operations needed across different subarrays, providing an optimal solution.

Solution Approach

The solution utilizes a sliding window technique alongside ordered data structures to efficiently find the minimal operations required to create a subarray of equal elements of size k:

  1. Data Structures Used: Two SortedList data structures from the sortedcontainers Python library are used to maintain the order and allow fast insertion and deletion. These are l and r, which represent the smaller and larger halves of the current subarray of size k, respectively.

  2. Initialization: Two sums, s1 and s2, are maintained to keep track of the total values in l and r. Initially, both sums are zero, and the minimum number of operations, ans, is set to infinity (inf).

  3. Iterating Over the Array: We iterate over each element x in the nums array, using the index i.

    • For each element x, it is added to l. The sum s1 is updated.
    • The largest element is removed from l (using pop()) and added to r, updating s2.
    • If the balance of the sizes between l and r becomes skewed (more than 1 difference), the smallest element of r is moved back to l.

  4. Finding Minimum Operations: Once the window reaches size k, the minimum operations required to transform the current subarray into one with equal elements (all set to the median) are calculated with the formula:

    ans = min(ans, s2 - r[0] * len(r) + r[0] * len(l) - s1)

    This formula calculates the sum of absolute differences between current elements and the median.

  5. Sliding the Window: To slide the window to the right, after processing a complete subarray of k elements:

    • Determine the starting index j of the subarray (j = i - k + 1).
    • Remove nums[j] from either l or r and adjust the corresponding sum (s1 or s2).

This clever combination of choosing the median and maintaining a balance between two parts of the window allows the algorithm to efficiently address the problem within a sliding window context.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a simple example to illustrate the solution approach described above.

Suppose we have an array nums = [1, 3, 2, 6, 5] and k = 3. Our goal is to find the minimum number of operations required to ensure that at least one subarray of size k has all elements equal.

  1. Initialize Data Structures:

    • Use two SortedList structures, l and r.
    • Initialize s1 and s2 to 0, and set ans to infinity.

  2. Iterate Over the Array:

    • Start reading elements of the array while maintaining a sliding window of size k.

  3. First Subarray [1, 3, 2]:

    • Add 1 to l and update s1: l = [1], s1 = 1.
    • Add 3 to l and move 3 from l to r to balance: l = [1], r = [3], s1 = 1, s2 = 3.
    • Add 2 to l and move 2 from l to r: l = [1], r = [2, 3], s1 = 1, s2 = 5.

  4. Calculate Operations for [1, 3, 2]:

    • The size of the window is k. Compute operations to make this subarray equal using the formula: 
      median = 2 (smallest element in `r`)
operations = s2 - median * len(r) + median * len(l) - s1
          = 5 - 2*2 + 2*1 - 1
          = 4
    • Update ans = min(inf, 4) = 4.

  5. Slide the Window to the next subarray [3, 2, 6]:

    • Remove 1 from l: l = [], s1 = 0.
    • Add 6 to l and move 6 to r: l = [2], r = [3, 6], s1 = 2, s2 = 9.

  6. Calculate Operations for [3, 2, 6]:

    • Compute: 
      operations = 9 - 3*2 + 3*1 - 2
          = 4
    • Update ans = min(4, 4) = 4.

  7. Slide the Window to the final subarray [2, 6, 5]:

    • Remove 3 from r and adjust sums: r = [6], s2 = 6.
    • Add 5 to l and balance: l = [2], r = [5, 6], s1 = 2, s2 = 11.

  8. Calculate Operations for [2, 6, 5]:

    • Compute: 
      operations = 11 - 5*2 + 5*1 - 2
          = 4
    • Update ans = min(4, 4) = 4.

Thus, the minimum number of operations required to make at least one subarray of size k have all elements equal is 4.

Solution Implementation

1from typing import List
2from sortedcontainers import SortedList
3from math import inf
4
5class Solution:
6    def minOperations(self, nums: List[int], k: int) -> int:
7        left = SortedList()  # Create a sorted list to maintain the smallest k-1 elements
8        right = SortedList() # Create a sorted list to store the rest elements
9        sum_left = 0         # Sum of elements in 'left'
10        sum_right = 0        # Sum of elements in 'right'
11        min_ops = inf        # Initialize the minimum operations to infinity
12
13        for i, x in enumerate(nums):
14            left.add(x)          # Add current element to 'left'
15            sum_left += x        # Add value to the sum of 'left'
16            largest_in_left = left.pop()  # Remove the largest element in 'left'
17            sum_left -= largest_in_left   # Subtract the removed element from 'sum_left'
18            right.add(largest_in_left)    # Add the removed element to 'right'
19            sum_right += largest_in_left  # Add value to the sum of 'right'
20
21            # Rebalance if 'right' has more elements than necessary
22            if len(right) - len(left) > 1:
23                smallest_in_right = right.pop(0)  # Remove the smallest element from 'right'
24                sum_right -= smallest_in_right    # Subtract it from 'sum_right'
25                left.add(smallest_in_right)       # Add it to 'left'
26                sum_left += smallest_in_right     # Add it to 'sum_left'
27
28            # Once we've processed at least k elements, calculate potential answer
29            if i >= k - 1:
30                # Calculate the minimum operations required up to current window
31                current_ops = sum_right - right[0] * len(right) + right[0] * len(left) - sum_left
32                min_ops = min(min_ops, current_ops)
33
34                # Move the window by removing the leftmost element
35                j = i - k + 1
36                if nums[j] in right:
37                    right.remove(nums[j])
38                    sum_right -= nums[j]
39                else:
40                    left.remove(nums[j])
41                    sum_left -= nums[j]
42
43        return min_ops
44
1import java.util.TreeMap;
2
3class Solution {
4    public long minOperations(int[] nums, int k) {
5        // TreeMap to count occurrences of elements in the left partition
6        TreeMap<Integer, Integer> leftPart = new TreeMap<>();
7        // TreeMap to count occurrences of elements in the right partition
8        TreeMap<Integer, Integer> rightPart = new TreeMap<>();
9      
10        long sumLeft = 0; // Sum of elements in the left partition
11        long sumRight = 0; // Sum of elements in the right partition
12        int sizeLeft = 0; // Size of the left partition
13        int sizeRight = 0; // Size of the right partition
14        long result = Long.MAX_VALUE; // Variable to store the minimum operations
15      
16        for (int i = 0; i < nums.length; ++i) {
17            // Add element to left partition
18            leftPart.merge(nums[i], 1, Integer::sum);
19            sumLeft += nums[i];
20            ++sizeLeft;
21
22            // Move largest element from left to right partition
23            int maxInLeft = leftPart.lastKey();
24            if (leftPart.merge(maxInLeft, -1, Integer::sum) == 0) {
25                leftPart.remove(maxInLeft);
26            }
27            sumLeft -= maxInLeft;
28            --sizeLeft;
29            rightPart.merge(maxInLeft, 1, Integer::sum);
30            sumRight += maxInLeft;
31            ++sizeRight;
32
33            // Balance size difference between right and left partitions
34            if (sizeRight - sizeLeft > 1) {
35                int minInRight = rightPart.firstKey();
36                if (rightPart.merge(minInRight, -1, Integer::sum) == 0) {
37                    rightPart.remove(minInRight);
38                }
39                sumRight -= minInRight;
40                --sizeRight;
41                leftPart.merge(minInRight, 1, Integer::sum);
42                sumLeft += minInRight;
43                ++sizeLeft;
44            }
45
46            // Calculate result for each valid window of size k
47            if (i >= k - 1) {
48                int minInRight = rightPart.firstKey();
49                // Calculate minimum operations required
50                result = Math.min(result, sumRight - minInRight * sizeRight 
51                                               + minInRight * sizeLeft - sumLeft);
52                // Remove the element that slides out of the window
53                int j = i - k + 1;
54                // Adjust sums and sizes accordingly
55                if (rightPart.containsKey(nums[j])) {
56                    if (rightPart.merge(nums[j], -1, Integer::sum) == 0) {
57                        rightPart.remove(nums[j]);
58                    }
59                    sumRight -= nums[j];
60                    --sizeRight;
61                } else {
62                    if (leftPart.merge(nums[j], -1, Integer::sum) == 0) {
63                        leftPart.remove(nums[j]);
64                    }
65                    sumLeft -= nums[j];
66                    --sizeLeft;
67                }
68            }
69        }
70        return result;
71    }
72}
73
1#include <vector>
2#include <set>
3#include <algorithm>
4#include <climits>
5
6class Solution {
7public:
8    long long minOperations(std::vector<int>& nums, int k) {
9        std::multiset<int> leftSet, rightSet; // Two sets to maintain the elements
10        long long sumLeft = 0, sumRight = 0; // Sums of elements in the left and right sets
11        long long result = LLONG_MAX; // Start with the largest possible value for min comparison
12
13        for (int i = 0; i < nums.size(); ++i) {
14            // Add current number to the left set and update left sum
15            leftSet.insert(nums[i]);
16            sumLeft += nums[i];
17
18            // Balance the sets by transferring the largest element from left to right
19            int largestLeft = *leftSet.rbegin();
20            leftSet.erase(leftSet.find(largestLeft));
21            sumLeft -= largestLeft;
22
23            rightSet.insert(largestLeft);
24            sumRight += largestLeft;
25
26            // Ensure right set does not have more than one extra element compared to left
27            if (rightSet.size() - leftSet.size() > 1) {
28                int smallestRight = *rightSet.begin();
29                rightSet.erase(rightSet.find(smallestRight));
30                sumRight -= smallestRight;
31
32                leftSet.insert(smallestRight);
33                sumLeft += smallestRight;
34            }
35
36            // Once we have at least 'k' elements, we calculate the minimum operations
37            if (i >= k - 1) {
38                long long smallestRight = *rightSet.begin();
39                result = std::min(result, 
40                                  sumRight - smallestRight * static_cast<int>(rightSet.size()) 
41                                  + smallestRight * static_cast<int>(leftSet.size()) 
42                                  - sumLeft);
43
44                // Adjust the window, removing the element that is sliding out
45                int j = i - k + 1;
46                if (rightSet.find(nums[j]) != rightSet.end()) {
47                    rightSet.erase(rightSet.find(nums[j]));
48                    sumRight -= nums[j];
49                } else {
50                    leftSet.erase(leftSet.find(nums[j]));
51                    sumLeft -= nums[j];
52                }
53            }
54        }
55        return result; // Return the minimum operations calculated
56    }
57};
58
1// Importing necessary modules
2interface Multiset<T> {
3    add(value: T): void;
4    delete(value: T): boolean;
5    [Symbol.iterator](): IterableIterator<T>;
6    size: number;
7    values(): IterableIterator<T>;
8    clear(): void;
9}
10
11// A basic implementation of a multiset using a Map
12class Multiset<T> implements Multiset<T> {
13    private map: Map<T, number> = new Map();
14
15    add(value: T): void {
16        this.map.set(value, (this.map.get(value) || 0) + 1);
17    }
18
19    delete(value: T): boolean {
20        if (!this.map.has(value)) return false;
21        const count = this.map.get(value) || 0;
22        if (count > 1) {
23            this.map.set(value, count - 1);
24        } else {
25            this.map.delete(value);
26        }
27        return true;
28    }
29
30    get size(): number {
31        let size = 0;
32        for (const count of this.map.values()) {
33            size += count;
34        }
35        return size;
36    }
37
38    values(): IterableIterator<T> {
39        return this.map.keys();
40    }
41
42    clear(): void {
43        this.map.clear();
44    }
45
46    // Helper method to find the smallest or largest element based on a comparator
47    findExtreme(comparator: (a: T, b: T) => number): T {
48        let extreme: T;
49        let first = true;
50        for (const value of this.map.keys()) {
51            if (first || comparator(value, extreme!) < 0) {
52                extreme = value;
53                first = false;
54            }
55        }
56        return extreme!;
57    }
58}
59
60// Function to calculate minimum operations required
61function minOperations(nums: number[], k: number): number {
62    const leftSet = new Multiset<number>();
63    const rightSet = new Multiset<number>();
64
65    let sumLeft = 0;
66    let sumRight = 0;
67    let result = Number.MAX_SAFE_INTEGER; // Initial result set to maximum safe number
68
69    for (let i = 0; i < nums.length; ++i) {
70        // Add current number to the left set and update left sum
71        leftSet.add(nums[i]);
72        sumLeft += nums[i];
73
74        // Balance sets by transferring largest element from left to right
75        const largestLeft = leftSet.findExtreme((a, b) => b - a);
76        leftSet.delete(largestLeft);
77        sumLeft -= largestLeft;
78
79        rightSet.add(largestLeft);
80        sumRight += largestLeft;
81
82        // Ensure right set does not have more than one extra element compared to left
83        if (rightSet.size - leftSet.size > 1) {
84            const smallestRight = rightSet.findExtreme((a, b) => a - b);
85            rightSet.delete(smallestRight);
86            sumRight -= smallestRight;
87
88            leftSet.add(smallestRight);
89            sumLeft += smallestRight;
90        }
91
92        // Calculate minimum operations once we have at least 'k' elements
93        if (i >= k - 1) {
94            const smallestRight = rightSet.findExtreme((a, b) => a - b);
95            result = Math.min(result, 
96                              sumRight - smallestRight * rightSet.size 
97                              + smallestRight * leftSet.size 
98                              - sumLeft);
99
100            // Adjust the window, removing the element that is sliding out
101            const j = i - k + 1;
102            if (rightSet.delete(nums[j])) {
103                sumRight -= nums[j];
104            } else {
105                leftSet.delete(nums[j]);
106                sumLeft -= nums[j];
107            }
108        }
109    }
110    return result; // Return the minimum operations calculated
111}
112

Time and Space Complexity

The given code iterates over each element of the list nums, performing operations involving a SortedList data structure for each element. This SortedList supports sorted insertions, deletions, and lookups which generally require O(\log k) time complexity for each operation. Since these operations are performed for each element in nums, the overall time complexity of the algorithm becomes O(n \times \log k), where n is the length of the array nums.

For the space complexity, the code uses two SortedList instances that each have a size determined by the parameter k, meaning it consumes a space complexity of O(k).

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

Which technique can we use to find the middle of a linked list?

Recommended Readings

Coding Interview Patterns: The Smart, Data-Driven Way to Prepare for Tech Interviews

Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Runtime to Algo Cheat Sheet

Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More