Maximize Greatness of an Array solution and explanation
9 more videos on this problem
Maximize Greatness of an Array || 2-Pointer & Sorting || Leetcode-2592Aryan Mittal · 8:34 · 2K views
Maximize Greatness of an Array || leetcode Biweekly 100 || Leetcode MediumBinaryMagic · 10:00 · 1K views
Leetcode 2592: Maximize Greatness of an ArrayAlgorithms Casts · 14:16 · 1K views
2592. Maximize Greatness of an Array (Leetcode Medium)Programming Live with Larry · 7:07 · 503 views
2592. Maximize Greatness of an Array - JAVA (Biweekly Contest 100)Sourin Majumdar · 5:17 · 431 views
Leetcode 2592 Maximize Greatness of an ArrayAlgorithmicIQ · 21:26 · 222 views
Maximize Greatness of an Array| Leetcode 2592 | Two Pointers | C++ | BiWeekly 100Tech Courses · 8:06 · 184 views
2592 Maximize Greatness of an Array |Leetcode Biweekly Contest 100 |Maximize Greatness of an ArrayAshutosh sharma · 6:02 · 175 views
2592. Maximize Greatness of an ArrayLet's Do It · 6:57 · 137 views
Leetcode BiWeekly contest 100 - Medium - Maximize Greatness of an ArrayPrakhar Agrawal · 4:15 · 134 views
The 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 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.
Example 1:
Input: nums = [1,3,5,2,1,3,1] Output: 4 Explanation: One of the optimal rearrangements is perm = [2,5,1,3,3,1,1]. At indices = 0, 1, 3, and 4, perm[i] > nums[i]. Hence, we return 4.
Example 2:
Input: nums = [1,2,3,4] Output: 3 Explanation: We can prove the optimal perm is [2,3,4,1]. At indices = 0, 1, and 2, perm[i] > nums[i]. Hence, we return 3.
Constraints:
1 <= nums.length <= 1050 <= nums[i] <= 109
Approach overview
Problem Overview: You are given an integer array nums. You can rearrange its elements to create a permutation perm. The goal is to maximize the number of indices i where perm[i] > nums[i]. In other words, you want as many elements as possible in the new arrangement to strictly beat the value at the same index in the original array.
Approach 1: Sorting + Two Pointers (Greedy) (Time: O(n log n), Space: O(1) or O(n) depending on sort)
This is the clean greedy solution and the one most interviewers expect. Start by sorting nums. Use two pointers: one pointer i tracks the smallest element that still needs to be beaten, and another pointer j scans for a larger element that can beat it. If nums[j] > nums[i], you form a valid pair and increase the greatness count, then move both pointers forward. If not, move j forward until you find a larger value. Sorting exposes the smallest possible targets first, which ensures you use the minimal winning number each time and preserve larger numbers for future matches. This greedy matching pattern appears frequently in greedy and two pointers problems. The algorithm scans the sorted array once after sorting, producing an overall time complexity of O(n log n) and constant extra space if sorting in place.
Approach 2: Hash Map Frequency Matching (Time: O(n), Space: O(n))
You can also think of the problem as matching each number with the smallest strictly greater number available. Build a frequency map of all values using a hash map. Iterate through the numbers in increasing order and try to assign a larger value from the frequency table. Each time you find a candidate x, search for the next value > x that still has remaining frequency and decrement it. Every successful assignment increases the greatness score. This approach avoids explicitly storing a sorted permutation but still relies on ordered processing of values. It works well when you already maintain counts or when the value range is small. Hash lookups and frequency updates take O(1) on average, giving an overall complexity near O(n) with O(n) additional space. The strategy relies on counting techniques common in array and frequency-map problems.
Recommended for interviews: The sorting + two-pointer greedy solution is the most common interview answer. It demonstrates understanding of ordering, greedy pairing, and pointer techniques in a compact implementation. A brute-force comparison of permutations would be factorial time and impractical, so recognizing that sorted greedy pairing maximizes wins shows strong problem-solving intuition.
Approach 1: Approach 1: Use Sorting and Two-Pointers
The simplest approach is to sort the array and then use the two-pointer technique to find pairs that sum up to the target.
Steps:
- Sort the array.
- Initialize two pointers, one at the start and the other at the end of the array.
- Iterate through the array, adjust the pointers based on the sum of values at the pointers.
def find_pairs(arr, target):
arr.sort()
left, right = 0, len(arr) - 1
while left < right:
current_sum = arr[left] + arr[right]
if current_sum == target:
print(f"Pair found: ({arr[left]}, {arr[right]})")
left += 1
right -= 1
elif current_sum < target:
left += 1
else:
right -= 1
arr = [1, 5, 7, -1, 5]
target = 6
find_pairs(arr, target)import java.util.Arrays;
public class TwoPointerPairs {
public static void findPairs(int[] arr, int target) {
Arrays.sort(arr);
int left = 0, right = arr.length - 1;
while (left < right) {
int sum = arr[left] + arr[right];
if (sum == target) {
System.out.println("Pair found: (" + arr[left] + ", " + arr[right] + ")");
left++;
right--;
} else if (sum < target) {
left++;
} else {
right--;
}
}
}
public static void main(String[] args) {
int[] arr = {1, 5, 7, -1, 5};
int target = 6;
findPairs(arr, target);
}
}#include <iostream>
#include <vector>
#include <algorithm>
void findPairs(std::vector<int>& arr, int target) {
std::sort(arr.begin(), arr.end());
int left = 0, right = arr.size() - 1;
while (left < right) {
int sum = arr[left] + arr[right];
if (sum == target) {
std::cout << "Pair found: (" << arr[left] << ", " << arr[right] << ")\n";
left++;
right--;
} else if (sum < target) {
left++;
} else {
right--;
}
}
}
int main() {
std::vector<int> arr = {1, 5, 7, -1, 5};
int target = 6;
findPairs(arr, target);
return 0;
}function findPairs(arr, target) {
arr.sort((a, b) => a - b);
let left = 0, right = arr.length - 1;
while (left < right) {
const sum = arr[left] + arr[right];
if (sum === target) {
console.log(`Pair found: (${arr[left]}, ${arr[right]})`);
left++;
right--;
} else if (sum < target) {
left++;
} else {
right--;
}
}
}
const arr = [1, 5, 7, -1, 5];
const target = 6;
findPairs(arr, target);#include <stdio.h>
#include <stdlib.h>
int compare(const void* a, const void* b) {
return (*(int*)a - *(int*)b);
}
void findPairs(int arr[], int n, int target) {
qsort(arr, n, sizeof(int), compare);
int left = 0, right = n - 1;
while (left < right) {
int sum = arr[left] + arr[right];
if (sum == target) {
printf("Pair found: (%d, %d)\n", arr[left], arr[right]);
left++;
right--;
} else if (sum < target) {
left++;
} else {
right--;
}
}
}
int main() {
int arr[] = {1, 5, 7, -1, 5};
int n = sizeof(arr) / sizeof(arr[0]);
int target = 6;
findPairs(arr, n, target);
return 0;
}using System;
class TwoPointerPairs {
public static void FindPairs(int[] arr, int target) {
Array.Sort(arr);
int left = 0, right = arr.Length - 1;
while (left < right) {
int sum = arr[left] + arr[right];
if (sum == target) {
Console.WriteLine("Pair found: ({0}, {1})", arr[left], arr[right]);
left++;
right--;
} else if (sum < target) {
left++;
} else {
right--;
}
}
}
static void Main(string[] args) {
int[] arr = {1, 5, 7, -1, 5};
int target = 6;
FindPairs(arr, target);
}
}This Python solution sorts the array then utilizes the two-pointer technique to identify pairs whose sums match the target. The pointers logically navigate through the array to find all possible pairs.
Time Complexity: O(n log n), because of sorting the array.
Space Complexity: O(1), as we are not using any additional space aside from variables.
Approach 2: Approach 2: Use Hash Map
This approach aims to find pairs by utilizing a hash map for achieving faster lookup times. This allows checking the complement for each number in the array.
Steps:
- Iterate over each element in the array.
- Check if the complement of the current element (target - current number) exists in the hash map.
- If it exists, a pair has been found; otherwise, store the current number in the hash map.
def find_pairs(arr, target):
hash_map = {}
for num in arr:
complement = target - num
if complement in hash_map:
print(f"Pair found: ({complement}, {num})")
hash_map[num] = True
arr = [1, 5, 7, -1, 5]
target = 6
find_pairs(arr, target)import java.util.HashMap;
public class HashMapPairs {
public static void findPairs(int[] arr, int target) {
HashMap<Integer, Boolean> hashMap = new HashMap<>();
for (int num : arr) {
int complement = target - num;
if (hashMap.containsKey(complement)) {
System.out.println("Pair found: (" + complement + ", " + num + ")");
}
hashMap.put(num, true);
}
}
public static void main(String[] args) {
int[] arr = {1, 5, 7, -1, 5};
int target = 6;
findPairs(arr, target);
}
}#include <iostream>
#include <unordered_map>
#include <vector>
void findPairs(const std::vector<int>& arr, int target) {
std::unordered_map<int, bool> hash;
for (int num : arr) {
int complement = target - num;
if (hash.find(complement) != hash.end()) {
std::cout << "Pair found: (" << complement << ", " << num << ")\n";
}
hash[num] = true;
}
}
int main() {
std::vector<int> arr = {1, 5, 7, -1, 5};
int target = 6;
findPairs(arr, target);
return 0;
}function findPairs(arr, target) {
const hashMap = {};
for (let num of arr) {
const complement = target - num;
if (complement in hashMap) {
console.log(`Pair found: (${complement}, ${num})`);
}
hashMap[num] = true;
}
}
const arr = [1, 5, 7, -1, 5];
const target = 6;
findPairs(arr, target);#include <stdio.h>
#include <stdlib.h>
#define MAX 100000
int hash[MAX] = {0};
void findPairs(int arr[], int n, int target) {
for (int i = 0; i < n; i++) {
int complement = target - arr[i];
if (hash[complement]) {
printf("Pair found: (%d, %d)\n", complement, arr[i]);
}
hash[arr[i]] = 1;
}
}
int main() {
int arr[] = {1, 5, 7, -1, 5};
int n = sizeof(arr) / sizeof(arr[0]);
int target = 6;
findPairs(arr, n, target);
return 0;
}using System;
using System.Collections.Generic;
class HashMapPairs {
public static void FindPairs(int[] arr, int target) {
Dictionary<int, bool> hashMap = new Dictionary<int, bool>();
foreach (var num in arr) {
int complement = target - num;
if (hashMap.ContainsKey(complement)) {
Console.WriteLine("Pair found: ({0}, {1})", complement, num);
}
hashMap[num] = true;
}
}
static void Main() {
int[] arr = {1, 5, 7, -1, 5};
int target = 6;
FindPairs(arr, target);
}
}This Python solution employs a dictionary to determine if the complementary value of each number (required to make the target sum) exists. If so, it prints the pair, otherwise, it stores the current number in the dictionary.
Time Complexity: O(n), since dictionary lookups and inserts are average constant time.
Space Complexity: O(n), required for dictionary storage.
Approach 3: Greedy
We can sort the array nums first.
Then we define a pointer i pointing to the first element of the array nums. We traverse the array nums, and for each element x we encounter, if x is greater than nums[i], then we move the pointer i to the right.
Finally, we return the value of the pointer i.
The time complexity is O(n times log n), and the space complexity is O(log n), where n is the length of the array nums.
function maximizeGreatness(nums: number[]): number {
nums.sort((a, b) => a - b);
let i = 0;
for (const x of nums) {
if (x > nums[i]) {
i += 1;
}
}
return i;
}func maximizeGreatness(nums []int) int {
sort.Ints(nums)
i := 0
for _, x := range nums {
if x > nums[i] {
i++
}
}
return i
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Use Sorting and Two-Pointers | Time Complexity: O(n log n), because of sorting the array. Space Complexity: O(1), as we are not using any additional space aside from variables. |
| Approach 2: Use Hash Map | Time Complexity: O(n), since dictionary lookups and inserts are average constant time. Space Complexity: O(n), required for dictionary storage. |
| Greedy | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting + Two Pointers (Greedy) | O(n log n) | O(1) extra (in-place sort) | Best general solution. Clean greedy logic and easy to implement in interviews. |
| Hash Map Frequency Matching | O(n) | O(n) | Useful when working with value frequencies or constrained ranges. |
Frequently asked questions
Is Maximize Greatness of an Array easy or hard?
The problem is rated Medium because the greedy insight is not immediately obvious. Once you recognize that pairing the smallest numbers with the smallest possible larger numbers maximizes wins, the implementation becomes straightforward. The core difficulty lies in spotting the sorting-based greedy strategy.
Maximize Greatness of an Array Python/Java solution
Most implementations follow the same idea: sort the array and use two pointers to count how many elements can beat earlier elements. This logic translates directly to Python, Java, C++, C#, and JavaScript with minimal differences. The implementation typically fits within 10–15 lines of code.
How to solve Maximize Greatness of an Array in O(n)?
A near O(n) strategy can be implemented using a hash map or frequency table to track counts of values. Iterate through numbers and greedily match each value with the smallest strictly larger value still available. Hash lookups and updates are O(1) on average, giving overall linear behavior with O(n) additional space.
What is the best approach for Maximize Greatness of an Array?
The most common solution uses sorting and a greedy two-pointer technique. After sorting the array, one pointer tracks the smallest element that needs to be beaten while another searches for the next larger value. Each successful match increases the greatness score. This approach runs in O(n log n) time due to sorting and uses O(1) extra space.
Is Maximize Greatness of an Array asked at Google/Amazon/Meta?
This problem follows a classic greedy pairing pattern that appears in interviews at companies like Amazon, Google, and Meta. Variants involving rearranging arrays, advantage matching, or maximizing wins are common in technical interviews. Understanding sorting-based greedy matching is the key takeaway.
What data structure is used in Maximize Greatness of an Array?
The primary structures are arrays combined with sorting and two pointers for the greedy approach. An alternative solution uses a hash map or frequency table to track how many times each number appears. Both methods rely on efficiently finding a larger element to pair against the current value.
What is the time complexity of Maximize Greatness of an Array?
The optimal practical solution runs in O(n log n) time because the array must be sorted first. After sorting, a single linear scan with two pointers computes the maximum greatness in O(n). Space complexity can be O(1) if the sort is in place.