2592. Maximize Greatness of an Array

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.

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:

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

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 illustrate the solution approach with a small example.

Suppose we have the following integer array nums:

nums = [4, 3, 2, 1]

Here are the steps we would follow:

Sort the array: The first step is to sort nums in ascending order.

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

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

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.

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

Question 1 out of 10

Is the following code DFS or BFS?

void search(Node root) {
  if (!root) return;
  visit(root);
  root.visited = true;
  for (Node node in root.adjacent) {
    if (!node.visited) {
      search(node);
    }
  }
}

Depth First Search

Breadth First Search

I don’t know