2592. Maximize Greatness of an Array

MediumGreedyArrayTwo PointersSorting
Leetcode Link

Problem Description

The problem provides an integer array nums, numerically indexed starting at 0. You are given the ability to rearrange the order of the elements in nums to form a new array perm. The greatness of an array is determined by the count of indices i (where 0 <= i < nums.length) that satisfy the condition perm[i] > nums[i]. Your task is to figure out the arrangement of nums that results in the highest possible greatness value, and then return that maximum greatness value.

In simpler terms, you need to permute the original array in such a way that as many elements as possible in the new array are greater than the corresponding elements in the original array at the same indices.

Intuition

The intuitive approach to achieve maximum greatness after permuting the elements in the array is by using a greedy strategy. Greedy strategies typically involve making the best or optimal choice available at each step with the hope of finding the global optimum at the end.

First, we sort the original array nums. Sorting is a frequently used first step in many algorithms because it brings order to the elements, thereby making it easier to compare and organize them to meet a certain conditionโ€”in this case, to maximize greatness.

Once sorted, the strategy is to have a pointer i traverse the array nums. For each element x encountered during the traversal, one compares it with the element at the current index i of the sorted nums. If x is greater than nums[i], it means this element contributes to the greatness and the pointer i is incremented to reflect this. The incremented i represents the tally of how many elements have so far contributed to the greatness.

The choice at each step is clear: take the smallest element still available (since the array is sorted) and compare it with the current element. If it qualifies, it gets counted towards greatness, and we move on to the next element.

In a way, each step is both isolated (involving a comparison between two specific elements) and cumulative (contributing to the overall count of greatness). This isolation allows each decision to be made independently. The cumulative nature of the count ensures that the count is reflective of the sum total of all right decisions made thus far.

By the end of the traversal, the pointer i reflects the maximum greatness, since it denotes the number of times we've successfully found an element in nums that can be placed at an index to satisfy the greatness condition perm[i] > nums[i]. We then return the value of the pointer i as the result.

Learn more about Greedy, Two Pointers and Sorting patterns.

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

Which data structure is used to implement recursion?

Solution Approach

The solution adopts a rather straightforward approach that can be broken down into two main steps: sorting and then greedily counting the elements that can increase the array's greatness.

Here's the algorithm in greater detail:

  1. First, the input array nums is sorted in ascending order. Sorting allows us to go through the elements in increasing order, which constructs the best scenario to increase greatness. After sorting, we can start from the smallest element in nums and try to satisfy the condition perm[i] > nums[i] incrementally as we proceed.

  2. The next important step is to initialize a counter i to zero. This counter i will be used to traverse the sorted array nums and keep track of the count for the greatness.

  3. We then iterate over the sorted array nums, at each step comparing the current element x against the element at index i of the sorted nums. If the condition x > nums[i] is true, it means placing x at index i in the permuted array perm would increase the greatness by 1, thus we increment the counter i by 1. Incrementing i effectively moves our 'checkpoint' forward in the array, to the next element that needs to be satisfied for increasing greatness.

  4. The incrementing of i is dependent on the condition x > nums[i], which is checked through i += x > nums[i]. This is a Pythonic way to increment i if x is greater than nums[i], otherwise, i remains the same.

  5. After the complete traversal of the array, counter i represents the maximum number of indices for which the condition perm[i] > nums[i] holds true. This maximum count is the desired maximum greatness, and the value of i is returned as the final result.

The reference solution approach clearly depends on the sorted nature of the array and the greedy strategy to increment the count only when the current element can contribute to the greatness. This one-pass solution is efficient as it makes a single comparison for each element in the array, yielding a time complexity of O(nlogn) due to sorting, and a space complexity of O(1) as it requires only a constant amount of additional memory space.

In summary, the solution makes use of:

  • Sorting (nums.sort()): To order the elements which is the precondition for our greedy strategy.
  • Greedy Iteration: To compare and count the elements satisfying the greatness condition in a single forward pass through the sorted array.
  • Pointer Incrementing (i += x > nums[i]): To count the elements that are contributing towards the greatness.
Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

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

Example Walkthrough

Let's illustrate the solution approach with a small example.

Suppose we have the following integer array nums:

1nums = [4, 3, 2, 1]

Here are the steps we would follow:

  1. Sort the array: The first step is to sort nums in ascending order.
1Sorted nums = [1, 2, 3, 4]

  1. Initialize the counter: We set up a counter i to keep track of the number of times we can achieve perm[i] > nums[i]. Initially, i = 0.

  2. Greedy iteration and comparison:

    • We compare nums[0] = 1 with x = nums[i = 0] (since i = 0 initially). Since 1 is not greater than itself, i remains unchanged.

    • Moving to the next element, we compare nums[1] = 2 to x = nums[i = 0] = 1. Here, 2 > 1, so this arrangement contributes to the greatness. Therefore, we increment i to 1.

    • We then compare nums[2] = 3 to x = nums[i = 1] = 2. Since 3 > 2, we can increment i again to 2.

    • Finally, we compare nums[3] = 4 to x = nums[i = 2] = 3. 4 > 3 holds, so we increment i once more to 3.

  3. Result: At the end of this process, the counter i now equals 3. That is the highest greatness we can achieve by rearranging the array.

In summary, we managed to find an arrangement of nums where three elements in the permutation array are greater than the corresponding elements in the original array. The maximum greatness of this example is hence 3. This result is achieved through an ordered greedy approach that ensures an optimal arrangement leveraging Python's clean syntax for conciseness and efficiency.

Solution Implementation

1from typing import List
2
3class Solution:
4    def maximizeGreatness(self, numbers: List[int]) -> int:
5        # Sort the numbers in non-decreasing order.
6        numbers.sort()
7      
8        # Initialize the greatness counter to zero.
9        greatness_counter = 0
10      
11        # Loop through each number in the sorted list.
12        for number in numbers:
13            # If the current number is greater than the number at the index
14            # represented by the greatness_counter, increment the counter.
15            # This implies we can increase our 'greatness' score.
16            if number > numbers[greatness_counter]:
17                greatness_counter += 1
18      
19        # Return the total greatness we can achieve.
20        return greatness_counter
21
1class Solution {
2
3    // Method to determine the maximum level of greatness that can be achieved
4    public int maximizeGreatness(int[] nums) {
5        // Sort the array in non-decreasing order
6        Arrays.sort(nums);
7
8        // Initialize the count of greatness to 0
9        int greatnessCount = 0;
10
11        // Iterate over the sorted array
12        for (int num : nums) {
13            // If the current element is greater than the element at the current greatness count index
14            if (num > nums[greatnessCount]) {
15                // Increment the greatness count
16                greatnessCount++;
17            }
18        }
19
20        // Return the total count of greatness achieved
21        return greatnessCount;
22    }
23}
24
1#include <vector>
2#include <algorithm>
3
4class Solution {
5public:
6    // Function to find the number of times the current element is greater than the smallest element seen so far.
7    int maximizeGreatness(vector<int>& nums) {
8        // Sort the input vector in non-decreasing order.
9        sort(nums.begin(), nums.end());
10      
11        // Variable to keep track of the current smallest element's index.
12        int smallestIndex = 0;
13
14        // Loop through the sorted vector to compute the result.
15        for (int num : nums) {
16            // Increase count if the current number is greater than the number at smallestIndex.
17            smallestIndex += num > nums[smallestIndex];
18        }
19      
20        // The result is the number of elements that were greater than their preceding elements.
21        return smallestIndex;
22    }
23};
24
1function maximizeGreatness(nums: number[]): number {
2    // Sort the array in non-decreasing order.
3    nums.sort((a, b) => a - b);
4  
5    // Initialize the count of numbers that can contribute to 'greatness'
6    let greatnessCount = 0;
7  
8    // Iterate through the sorted array.
9    for (const currentNumber of nums) {
10        // If the current number is greater than the smallest number in the set of 'greatness' numbers,
11        // it can contribute, so we increment the count.
12        if (currentNumber > nums[greatnessCount]) {
13            greatnessCount += 1;
14        }
15    }
16  
17    // Return the final count of numbers that contribute to 'greatness'.
18    return greatnessCount;
19}
20
Not Sure What to Study? Take the 2-min Quiz๏ผš

Which of the following is a min heap?

Time and Space Complexity

Time Complexity

The time complexity of the given function maximizeGreatness is primarily dominated by the nums.sort() operation. Sorting an array is typically done using the Timsort algorithm in Python, which has a time complexity of O(n log n), where n is the length of the array nums. The for-loop that follows the sort operation has a time complexity of O(n) since it iterates over each element in the sorted list exactly once.

Therefore, when combining these two operations, the total time complexity remains O(n log n) as the sorting operation is the most significant factor.

Space Complexity

The space complexity of the sort operation in Python is O(n), but this uses the internal buffer for sorting which does not count towards the additional space required by the algorithm. However, due to the recursive stack calls made during sorting, the worst-case space complexity is O(log n). No additional data structures that are dependent on the size of the input array are used in the function, keeping the space complexity to O(log n) for this function.

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

Fast Track Your Learning with Our Quick Skills Quiz:

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?

Recommended Readings

Greedy Introduction

Greedy Introduction iframe width 560 height 315 src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you

Tech Interview Pattern | Two Pointers Introduction

Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers iframe width 560 height 315 src https www youtube com embed xZ4AfXHQ1VQ title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture allowfullscreen iframe Two pointers is a common interview technique

Sorting Summary

Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced

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 ๐Ÿ‘จโ€๐Ÿซ