2779. Maximum Beauty of an Array After Applying Operation


Problem Description

You are provided with an array nums which is 0-indexed. This means the first element of the array is at position 0, the next element is at position 1, and so on. A non-negative integer k is also given to you.

There is a set of operations you can perform on nums to potentially increase its beauty. An array's beauty is defined as the length of the longest subsequence where all elements are equal. A subsequence is any subset of the array that is not necessarily contiguous but maintains the original order of elements.

Each operation follows two steps:

  1. Choose an index i from the array which has not been chosen before.
  2. Replace the element at nums[i] with any number within the range [nums[i] - k, nums[i] + k].

Your goal is to execute these operations as many times as you see fit to maximize the beauty of the array, but you can only choose each index once. The question asks for the maximum beauty that can be achieved through such operations.

Intuition

The problem is, in essence, about finding the largest group of numbers in the nums array that can be made equal through the allowed operations. If we can increase or decrease each number by up to k, we can think of each number as having a "reach" of 2k + 1 (from nums[i] - k to nums[i] + k), where all numbers in this reach can be made equal to nums[i].

One approach to solving this problem is to use a difference array, which is an efficient method for applying updates over a range of indices in an array. The general idea is to build an augmented array, d, where each element represents the difference between successive elements in the nums array. This array d is then used to accumulate the total possible count of each value in the original array after applying all possible operations.

The array d is initialized with zeros and should have enough capacity to accommodate the largest number after an operation (which is max(nums) + 2 * k + 1) plus an additional element. For each element in nums, we can perform the following in the array d:

  1. Increment the value at index x (the original number) because you can always choose not to change the number, contributing to its count.
  2. Decrement the value at index x + 2 * k + 1, which is beyond the reach of the operations from nums[i], thus ending the impact of this specific number.

Once the difference array d is fully populated, we iterate over it, accumulating the counts and keeping track of the maximum value found, which corresponds to the maximum beauty of the array.

Here, the variable ans is used to track the maximum beauty, and s is the running sum while iterating through the augmented array d. In each step, s is incremented by the current value in d, and ans is updated if s is greater than the current ans.

Overall, this approach effectively allows assessing the impact of all operations in a cumulative fashion, facilitating the computation of the maximum beauty in a time-efficient manner.

Learn more about Binary Search, Sorting and Sliding Window patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece:

Depth first search is equivalent to which of the tree traversal order?

Solution Approach

The provided solution uses a difference array as a key data structure. A difference array is an array that allows updates over intervals in the original array in O(1) time and querying in O(n) time, where n is the number of elements. This turns out to be very efficient for certain types of problems — such as this one, where we repeatedly perform a fixed change to a range of elements.

Here's a step-by-step breakdown of the maximumBeauty function's implementation:

  1. Calculate the size m for the difference array by taking the maximum element in nums, adding twice k, and then adding 2. This guarantees the difference array can cover all the values after all the operations. The actual value is m = max(nums) + k * 2 + 2.

  2. Initialize a difference array d with size m filled with zeros. This array will track the potential increases and decreases over the ranges from all nums[i].

  3. Loop through each number x in nums and:

    • Increment the count at d[x] to indicate the potential start point of numbers in the range [x-k, x+k] to be adjusted to x.
    • Decrement the count at d[x + k * 2 + 1] to indicate the end point of the range.
  4. Initialize ans, which will store the maximum beauty of the array, and s, which will be used as the running sum to apply the effect of the difference array when traversing it.

  5. Traverse the difference array d, accumulating the total effect in s at each step, and update ans if the new sum s is greater than the current ans. This traversal allows us to collect the effective total count for each number as though all operations have been applied.

  6. Finally, return ans, which is now the longest length of a subsequence that can be created through the allowed modifications — the maximum beauty of the array nums.

To sum up, this solution is based on the insight that we can use a difference array to efficiently simulate all the operations and directly compute the result instead of performing each operation individually.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Given an array of 1,000,000 integers that is almost sorted, except for 2 pairs of integers. Which algorithm is fastest for sorting the array?

Example Walkthrough

Let's consider a small example to illustrate the solution approach.

Suppose we have an array nums = [1, 3, 4] and k = 1.

First, we follow these steps to maximize the beauty of the array:

  1. Calculate the size for the difference array. With a max(nums) of 4, k * 2 is 2, so m is 4 + 2 + 2 which gives us 8.

  2. Initialize the difference array d to be size 8, filled with zeros: d = [0, 0, 0, 0, 0, 0, 0, 0].

  3. Loop through each number in nums and update the difference array:

    • For x = 1, increment d[1] and decrement d[1 + 1 * 2 + 1], so d becomes [0, 1, 0, -1, 0, 0, 0, 0].
    • For x = 3, increment d[3] and decrement d[3 + 1 * 2 + 1], so d becomes [0, 1, 0, 0, 0, -1, 0, 0].
    • For x = 4, increment d[4] and decrement d[4 + 1 * 2 + 1], so d becomes [0, 1, 0, 0, 1, -1, 0, -1].
  4. Initialize ans to 0 and s to 0.

  5. Traverse the difference array d, updating ans as we accumulate s:

    • s = 0d[0] = 0, ans remains 0.
    • s = 0 + 1d[1] = 1, update ans to 1.
    • s = 1 + 0d[2] = 0, ans remains 1.
    • s = 1 + 0d[3] = 0, ans remains 1.
    • s = 1 + 1d[4] = 1, update ans to 2.
    • s = 2 - 1d[5] = -1, ans remains 2.
    • s = 1 + 0d[6] = 0, ans remains 2.
    • s = 1 - 1d[7] = -1, ans remains 2.
  6. Finally, return ans which is 2. This means the largest length of a subsequence where all elements are equal after the operations is 2.

From the walkthrough, we can see with nums = [1, 3, 4] and k = 1, the maximum beauty that can be achieved is 2, since we can transform the array to [3, 3, 3] by incrementing the first element 1 by 2 (which is within the range [1 - 1, 1 + 1]) and decrementing the last element 4 by 1 (which is within the range [4 - 1, 4 + 1]), resulting in two 3s which creates the longest subsequence of equal numbers.

Solution Implementation

1from typing import List
2
3class Solution:
4    def maximumBeauty(self, flowers: List[int], steps: int) -> int:
5        # Calculate the maximum constant for adjusting the range
6        max_flower = max(flowers) + steps * 2 + 2
7      
8        # Initialize a difference array with the same range
9        diff_array = [0] * max_flower
10      
11        # Construct the difference array to perform range updates
12        for flower_count in flowers:
13            diff_array[flower_count] += 1
14            diff_array[flower_count + steps * 2 + 1] -= 1
15      
16        # Initialize the variables for tracking the maximum beauty and the running sum
17        max_beauty = running_sum = 0
18      
19        # Apply the difference array technique to find the total at each point
20        for count_diff in diff_array:
21            running_sum += count_diff
22            max_beauty = max(max_beauty, running_sum)
23      
24        # Return the maximum beauty value found
25        return max_beauty
26
1import java.util.Arrays;
2
3public class Solution {
4  
5    public int maximumBeauty(int[] flowers, int additions) {
6        // Calculate the maximum value after all possible additions.
7        // We add extra space for fluctuations in the count within the k range.
8        int maxValue = Arrays.stream(flowers).max().getAsInt() + additions * 2 + 2;
9        int[] delta = new int[maxValue];
10      
11        // Build the difference array using the number of additions possible adding and subtracting at the range ends.
12        for (int flower : flowers) {
13            delta[flower]++;
14            delta[flower + additions * 2 + 1]--;
15        }
16      
17        int maxBeauty = 0; // This will hold the maximum beauty calculated so far.
18        int runningSum = 0; // This will be used to compute the running sum from the difference array.
19      
20        // Compute the running sum and find the maximum value.
21        for (int value : delta) {
22            runningSum += value;
23            maxBeauty = Math.max(maxBeauty, runningSum);
24        }
25      
26        // Return the computed maximum beauty of the bouquet.
27        return maxBeauty;
28    }
29}
30
1class Solution {
2public:
3    int maximumBeauty(vector<int>& flowers, int k) {
4        // Calculate the maximum value in the vector and set the range accordingly,
5        // considering the range needs to be large enough to account for adding k to both sides.
6        int maxValue = *max_element(flowers.begin(), flowers.end()) + k * 2 + 2;
7      
8        // Create a differential array with the size based on calculated range.
9        vector<int> diffArray(maxValue, 0);
10      
11        // Iterate over the original array and update the differential array accordingly.
12        for (int flower : flowers) {
13            // Increase the count at the start of the window (flower's position).
14            diffArray[flower]++;
15            // Decrease the count at the end of the window.
16            diffArray[flower + k * 2 + 1]--;
17        }
18      
19        // Initialize variables to track the sum and the maximum beauty so far.
20        int currentSum = 0, maxBeauty = 0;
21      
22        // Iterate over the differential array and calculate the prefix sum,
23        // which gives us the running count of flowers.
24        for (int count : diffArray) {
25            // Update the running sum with the current count.
26            currentSum += count;
27            // Calculate the maximum beauty seen so far by taking the maximum of the
28            // current running sum and the previous maxBeauty.
29            maxBeauty = max(maxBeauty, currentSum);
30        }
31      
32        // Return the maximum beauty that can be achieved.
33        return maxBeauty;
34    }
35};
36
1function maximumBeauty(nums: number[], operationsAllowed: number): number {
2    // Calculate a maximum boundary to create an array that is big enough to hold all possible values after operations.
3    const maxBoundary = Math.max(...nums) + operationsAllowed * 2 + 2;
4    // Initialize difference array to hold the frequency of numbers up to the maximum boundary.
5    const differenceArray: number[] = new Array(maxBoundary).fill(0);
6
7    // Iterate over the input array and update the difference array based on the allowed operations.
8    for (const num of nums) {
9        // For each number, increment the count at the number's index in the difference array.
10        differenceArray[num]++;
11        // Decrement the count at the index that is 'operationsAllowed' doubled and one past the current number.
12        differenceArray[num + operationsAllowed * 2 + 1]--;
13    }
14
15    let maxBeauty = 0;  // Store the maximum beauty value found.
16    let sum = 0;        // Accumulator to store the running sum while iterating over the difference array.
17
18    // Iterate over the difference array to find the maximum accumulated frequency (beauty).
19    for (const frequency of differenceArray) {
20        // Update the running sum by adding the current frequency.
21        sum += frequency;
22        // Update the maximum beauty value if the current running sum is greater than the previous maximum.
23        maxBeauty = Math.max(maxBeauty, sum);
24    }
25
26    // Return the maximum beauty value found.
27    return maxBeauty;
28}
29
Not Sure What to Study? Take the 2-min Quiz:

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

Time and Space Complexity

The provided code implements a function to determine the maximum beauty of an array after performing certain operations. The key operations to analyze are the loops and the creation of the list d.

Time Complexity:

  • The first part of the analysis involves the line m = max(nums) + k * 2 + 2. This operation is O(n) where n is the number of elements in nums, as it requires a pass through the entire list to determine the maximum value.
  • The creation of the list d with a length of m is O(m). This accounts for the space required to store the frequency differences.
  • The loop that populates the list d iterates over each element in nums, so this part is O(n).
  • Inside this loop, there are constant-time operations O(1) (incrementing and decrementing the values).
  • The final loop iterates through the list d which has a length of m. This loop has a time complexity of O(m) as it needs to visit each element in d to accumulate the sum and compute the maximum.

Combining these complexities, we get O(n) + O(m) + O(n) + O(m) which simplifies to O(n + m), with m being proportional to max(nums) + 2 * k.

Space Complexity:

  • The list d with length m is the most significant factor in space complexity, making it O(m), as it depends on the value of k and the maximum value in nums.
  • The variables ans and s are of constant space O(1).

Hence, the final time complexity is O(n + m) and the space complexity is O(m), taking into account the size of the input nums and the range of values derived from it combined with k.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8
1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12
1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

Recommended Readings


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫