Maximize Greatness of an Array - Practice Coding Problems

Maximize Greatness of an Array - Problem

You are given a 0-indexed integer array nums. You are allowed to permute nums into a new array perm of your choosing.

We define the greatness of nums to be the number of indices 0 <= i < nums.length for which perm[i] > nums[i].

Return the maximum possible greatness you can achieve after permuting nums.

Input & Output

Example 1 — Basic Case

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

› Output: 3

💡 Note: Optimal permutation is [2,4,5,3,1]. Comparing with original [1,3,5,2,4]: positions 0 (2>1), 1 (4>3), and 3 (3>2) satisfy perm[i] > nums[i], giving greatness = 3.

Example 2 — All Same Elements

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

› Output: 0

💡 Note: All elements are identical, so no matter how we permute, perm[i] can never be greater than nums[i]. Maximum greatness = 0.

Example 3 — Ascending Order

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

› Output: 4

💡 Note: Optimal permutation is [2,3,4,5,1]. This gives us 4 positions where perm[i] > nums[i]: 2>1, 3>2, 4>3, 5>4.

Constraints

1 ≤ nums.length ≤ 10⁵
0 ≤ nums[i] ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

Given array [1,3,5,2,4]

Process

Find optimal permutation using greedy matching

Output

Maximum greatness count = 3

Key Takeaway

🎯 Key Insight: Sort the array and greedily match each element with the smallest available larger element to maximize greatness count.

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is to use a greedy approach after sorting. Sort the array and use two pointers to match each element with the smallest available larger element. This maximizes the number of positions where perm[i] > nums[i]. Best approach uses two pointers on sorted array with Time: O(n log n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Permutations	O(n! × n)	O(n)	Generate all possible permutations and count greatness for each
Sort and Greedy Match	O(n log n)	O(n)	Sort array and greedily match each element with smallest possible larger element
Optimized Two Pointers	O(n log n)	O(1)	Single sorted array with two pointers for optimal space efficiency

Brute Force - Try All Permutations — Algorithm Steps

Generate all n! permutations of the array
For each permutation, count positions where perm[i] > nums[i]
Return the maximum count found

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Permutations

Create all possible arrangements of the array

Count Greatness

For each permutation, count positions where perm[i] > nums[i]

Find Maximum

Return the highest count found

Code -

solution.c — C

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

void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

int permute(int* arr, int* original, int n, int start) {
    if (start == n) {
        int greatness = 0;
        for (int i = 0; i < n; i++) {
            if (arr[i] > original[i]) greatness++;
        }
        return greatness;
    }
    
    int maxGreatness = 0;
    for (int i = start; i < n; i++) {
        swap(&arr[start], &arr[i]);
        int g = permute(arr, original, n, start + 1);
        if (g > maxGreatness) maxGreatness = g;
        swap(&arr[start], &arr[i]);
    }
    return maxGreatness;
}

int solution(int* nums, int n) {
    int* arr = (int*)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) arr[i] = nums[i];
    int result = permute(arr, nums, n, 0);
    free(arr);
    return result;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    int nums[100], n = 0;
    char* token = strtok(line + 1, ",]");
    while (token) {
        nums[n++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    printf("%d\n", solution(nums, n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n! × n)

Generate n! permutations, each taking O(n) time to evaluate

⚠ Quadratic Growth

Space Complexity

O(n)

Space to store current permutation and recursion stack

⚡ Linearithmic Space

23.4K Views

Medium Frequency

~15 min Avg. Time

847 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

Brute Force - Try All Permutations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler