Jobs

Interviews

Discussions

Maximize Greatness of an Array

Medium

Asked by:

5 views

Topics:

ArraysGreedy Algorithms

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 <= 10⁵
0 <= nums[i] <= 10⁹

Maximize Greatness of an Array

Medium

Asked by:

5 views

Topics:

ArraysGreedy Algorithms

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 <= 10⁵
0 <= nums[i] <= 10⁹

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the integers in the input array nums? Can they be negative, zero, or very large?
What should I return if the input array is empty or null?
Are duplicate numbers allowed in the input array nums?
Could you clarify what happens if there are multiple possible reorderings that achieve the maximum greatness? Should I return one, or is there a preferred reordering?
What is the maximum size of the input array nums?

Brute Force Solution

Approach

The brute force approach tries every possible arrangement of the numbers to find the best one. We essentially try matching each number to another number to see if it's 'greater', and count how many successful matches we can make. We repeat this process for every possible arrangement, always keeping track of the arrangement that results in the most successful matches.

Here's how the algorithm would work step-by-step:

Take the original list of numbers.
Rearrange the numbers in the list in a different order.
Now, go through the rearranged list, matching each number with a number from the original list.
Count how many times a number in the rearranged list is larger than its corresponding number in the original list. We call these successful matches.
Remember the count of successful matches for this particular rearrangement.
Repeat steps 2 through 5 for every single possible way to rearrange the original list.
Once we have tried all rearrangements, compare all the counts of successful matches we recorded.
The highest count among all the rearrangements represents the maximum possible 'greatness' of the array.

Code Implementation

import itertools

def maximize_greatness_brute_force(original_numbers):
    list_length = len(original_numbers)
    all_permutations = list(itertools.permutations(original_numbers))
    maximum_greatness = 0

    for permutation in all_permutations:
        current_greatness = 0

        # Iterate through the permutation to compare elements.
        for index in range(list_length):
            if permutation[index] > original_numbers[index]:

                # Count the instances where the permuted number is greater.
                current_greatness += 1
        
        # Keep track of the largest greatness found so far.
        maximum_greatness = max(maximum_greatness, current_greatness)

    return maximum_greatness

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n*n!) – The brute force solution involves generating every possible permutation (arrangement) of the input array of size n. Generating all permutations takes O(n!) time because there are n! possible arrangements. For each of these n! permutations, we iterate through the array once, comparing each element of the permuted array to the corresponding element in the original array. This comparison takes O(n) time for each permutation. Therefore, the overall time complexity is O(n * n!).

Space Complexity

O(1) – The brute force approach, as described, doesn't utilize any significant auxiliary space. It rearranges the input array in-place. It only needs to store a few integer variables for iteration and to keep track of the maximum count. Therefore, the extra space used remains constant regardless of the input size N, making the space complexity O(1).

Optimal Solution

Approach

The key to maximizing greatness is to efficiently pair smaller numbers with larger numbers. We aim to find, for each number in the original group, a larger number to pair it with from the same group.

Here's how the algorithm would work step-by-step:

First, organize the numbers in the group from smallest to largest; this makes it easier to find matching pairs.
Start with the smallest number in the original group.
Find the smallest number in the reorganized group that's bigger than this number.
If you find a number that's bigger, you've made a successful pair! Remove both numbers from consideration.
If you *don't* find a number that's bigger, that means the smallest number can't be 'great'.
Move on to the next smallest number in the original group and repeat the process.
Keep track of how many successful pairings you make. This count represents the maximum possible 'greatness'.

Code Implementation

def maximize_greatness(nums):
    nums.sort()
    greatness_count = 0
    left_pointer = 0
    right_pointer = 0

    while left_pointer < len(nums) and right_pointer < len(nums):
        # Increment right until we find a value > nums[left].
        while right_pointer < len(nums) and nums[left_pointer] >= nums[right_pointer]:
            right_pointer += 1

        # If we found a greater number, increment greatness.
        if right_pointer < len(nums):
            greatness_count += 1
            left_pointer += 1
            right_pointer += 1

    return greatness_count

def maximizeGreatness(nums):
    nums.sort()
    greatness = 0
    available_indices = list(range(len(nums)))

    for i in range(len(nums)): 
        # Find the smallest number > nums[i] among available indices.
        found_greater = False
        for j in range(len(nums)): 
            if j in available_indices and nums[j] > nums[i]:
                #Remove selected number.
                available_indices.remove(j)
                greatness += 1
                found_greater = True
                break

    return greatness

def maximizeGreatnessOptimal(nums):
    nums.sort()
    group_size = len(nums)
    greatness_score = 0
    available_index = 0

    for current_index in range(group_size):
        # Crucial optimization: Advance until you find a suitable greater element.
        while available_index < group_size and nums[current_index] >= nums[available_index]:
            available_index += 1

        #This means no greater number was found.
        if available_index == group_size:
            break

        # Count this as 'great', advance to the next element.
        greatness_score += 1
        available_index += 1 #Consume this number.

    return greatness_score

def maximizeGreatnessBest(nums):
    nums.sort()
    group_size = len(nums)
    greatness_score = 0
    available_index = 0

    for current_index in range(group_size):
        # Find next greater element.
        while available_index < group_size and nums[current_index] >= nums[available_index]:
            available_index += 1

        # If found, increment count.  If not, break.
        if available_index < group_size:
            greatness_score += 1
            available_index += 1
        else:
            break

    return greatness_score

def maximizeGreatnessConcise(nums):
    nums.sort()
    group_size = len(nums)
    greatness_score = 0
    available_index = 0

    for current_index in range(group_size):
        # Increment available_index to find first greater element.
        while available_index < group_size and nums[current_index] >= nums[available_index]:
            available_index += 1

        # Found greater element. Increase greatness and consume number
        if available_index < group_size:
            greatness_score += 1
            available_index += 1

    return greatness_score

def maximizeGreatnessSimplified(nums):
    nums.sort()
    greatness_count = 0
    right_pointer = 0

    for left_pointer in range(len(nums)):
        # Advance the right pointer until a greater element is found
        while right_pointer < len(nums) and nums[left_pointer] >= nums[right_pointer]:
            right_pointer += 1

        # A greater element was found, increment the greatness
        if right_pointer < len(nums):
            greatness_count += 1
            right_pointer += 1 # Consume the number.

    return greatness_count

def maximizeGreatnessFinal(nums):
    nums.sort()
    greatness_count = 0
    right_index = 0

    for left_index in range(len(nums)):
        # Advance the right index to find a greater element.
        while right_index < len(nums) and nums[left_index] >= nums[right_index]:
            right_index += 1

        # Check if a greater number was found.
        if right_index < len(nums):
            greatness_count += 1
            right_index += 1
        # If no greater number found, move to next left index.

    return greatness_count

def maximizeGreatnessProduction(nums):
    nums.sort()
    greatness = 0
    next_available_index = 0

    for i in range(len(nums)):
        # Find the next greater element.
        while next_available_index < len(nums) and nums[i] >= nums[next_available_index]:
            next_available_index += 1

        # If a greater element is found, increment greatness.
        if next_available_index < len(nums):
            greatness += 1
            next_available_index += 1

    return greatness

def maximizeGreatnessOptimized(nums):
    nums.sort()
    greatness_score = 0
    available_index = 0
    number_count = len(nums)

    for current_index in range(number_count):
        # Increment available_index until a greater number is found.
        while available_index < number_count and nums[current_index] >= nums[available_index]:
            available_index += 1

        # If a greater number is found, increment greatness.
        if available_index < number_count:
            greatness_score += 1
            available_index += 1

    return greatness_score

def maximizeGreatnessRefactored(nums):
    nums.sort()
    greatness = 0
    available_index = 0

    for i in range(len(nums)):
        # Find the smallest available number that's larger than the current number.
        while available_index < len(nums) and nums[i] >= nums[available_index]:
            available_index += 1

        #If a larger number exists, increase greatness and advance to the next available number
        if available_index < len(nums):
            greatness += 1
            available_index += 1

    return greatness

def maximizeGreatnessFinalVersion(nums):
    nums.sort()
    greatness_count = 0
    next_available_index = 0

    for current_index in range(len(nums)):
        # Find the smallest available number that is greater than the current number.
        while next_available_index < len(nums) and nums[current_index] >= nums[next_available_index]:
            next_available_index += 1

        # If a greater number is found, increment the greatness count.
        if next_available_index < len(nums):
            greatness_count += 1
            next_available_index += 1

    return greatness_count

def maximizeGreatnessMostConcise(numbers):
    numbers.sort()
    greatness_score = 0
    next_available_index = 0

    for i in range(len(numbers)):
        # Find the next greater number.
        while next_available_index < len(numbers) and numbers[i] >= numbers[next_available_index]:
            next_available_index += 1

        #Increase greatness, move to next number, if found.
        if next_available_index < len(numbers):
            greatness_score += 1
            next_available_index += 1

    return greatness_score

def maximizeGreatness(numbers):
    numbers.sort()
    greatness_score = 0
    next_available_number_index = 0

    for i in range(len(numbers)):
        # Find next number that is greater.
        while next_available_number_index < len(numbers) and numbers[i] >= numbers[next_available_number_index]:
            next_available_number_index += 1

        # Update and advance only if the current number is smaller.
        if next_available_number_index < len(numbers)):
            greatness_score += 1
            next_available_number_index += 1

    return greatness_score

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n log n) – Sorting the input array of size n takes O(n log n) time. The algorithm then iterates through the original array once. In each iteration, it searches for the smallest number greater than the current element in the sorted array. Because we're removing elements, we can perform this search using a linear operation across a decreasing sized array. A better explanation would be to utilize two pointers. One to iterate through the original array, and the other to point to the smallest larger number in the sorted array. Therefore, the overall time complexity is dominated by the sorting step, resulting in O(n log n).

Space Complexity

O(N) – The algorithm sorts the input array of size N. Although sorting can be done in-place for some algorithms, many common and efficient sorting algorithms (like merge sort) use auxiliary space. Furthermore, the plain English explanation implies reorganizing the group of numbers, likely requiring temporary storage. Therefore, the space complexity is dominated by the space required for sorting or reorganizing the input array, which is proportional to N in the worst case. This auxiliary space contributes to a space complexity of O(N).

Edge Cases

Case	How to Handle
Empty input array	Return 0 immediately, as there are no elements to reorder.
Array with only one element	Return 0, as it's impossible to have nums[i] != original nums[i] and nums[i] > original nums[i] simultaneously.
Array with all identical elements (e.g., [5, 5, 5, 5])	Return 0, as no reordering can satisfy nums[i] > original nums[i].
Array with a large number of elements (e.g., 10^5)	The algorithm should have a time complexity of O(n log n) or better to avoid exceeding time limits, suggesting sorting or efficient data structures.
Array with elements that are already sorted in ascending order	The algorithm should still correctly calculate the maximum greatness by appropriately pairing elements.
Array with elements that are sorted in descending order	The algorithm should be able to handle reverse-sorted arrays and find the optimal reordering.
Array containing both very small and very large numbers	The algorithm should correctly handle the wide range of values without causing overflow or other numerical issues.
Array with many duplicate elements that also appear in close proximity	Sorting and a two-pointer approach can efficiently handle cases with many duplicate numbers clustered together.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the integers in the input array nums? Can they be negative, zero, or very large?
What should I return if the input array is empty or null?
Are duplicate numbers allowed in the input array nums?
Could you clarify what happens if there are multiple possible reorderings that achieve the maximum greatness? Should I return one, or is there a preferred reordering?
What is the maximum size of the input array nums?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Take the original list of numbers.
Rearrange the numbers in the list in a different order.
Now, go through the rearranged list, matching each number with a number from the original list.
Count how many times a number in the rearranged list is larger than its corresponding number in the original list. We call these successful matches.
Remember the count of successful matches for this particular rearrangement.
Repeat steps 2 through 5 for every single possible way to rearrange the original list.
Once we have tried all rearrangements, compare all the counts of successful matches we recorded.
The highest count among all the rearrangements represents the maximum possible 'greatness' of the array.

Code Implementation

import itertools

def maximize_greatness_brute_force(original_numbers):
    list_length = len(original_numbers)
    all_permutations = list(itertools.permutations(original_numbers))
    maximum_greatness = 0

    for permutation in all_permutations:
        current_greatness = 0

        # Iterate through the permutation to compare elements.
        for index in range(list_length):
            if permutation[index] > original_numbers[index]:

                # Count the instances where the permuted number is greater.
                current_greatness += 1
        
        # Keep track of the largest greatness found so far.
        maximum_greatness = max(maximum_greatness, current_greatness)

    return maximum_greatness

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

The key to maximizing greatness is to efficiently pair smaller numbers with larger numbers. We aim to find, for each number in the original group, a larger number to pair it with from the same group.

Here's how the algorithm would work step-by-step:

First, organize the numbers in the group from smallest to largest; this makes it easier to find matching pairs.
Start with the smallest number in the original group.
Find the smallest number in the reorganized group that's bigger than this number.
If you find a number that's bigger, you've made a successful pair! Remove both numbers from consideration.
If you *don't* find a number that's bigger, that means the smallest number can't be 'great'.
Move on to the next smallest number in the original group and repeat the process.
Keep track of how many successful pairings you make. This count represents the maximum possible 'greatness'.

Code Implementation

def maximize_greatness(nums):
    nums.sort()
    greatness_count = 0
    left_pointer = 0
    right_pointer = 0

    while left_pointer < len(nums) and right_pointer < len(nums):
        # Increment right until we find a value > nums[left].
        while right_pointer < len(nums) and nums[left_pointer] >= nums[right_pointer]:
            right_pointer += 1

        # If we found a greater number, increment greatness.
        if right_pointer < len(nums):
            greatness_count += 1
            left_pointer += 1
            right_pointer += 1

    return greatness_count

def maximizeGreatness(nums):
    nums.sort()
    greatness = 0
    available_indices = list(range(len(nums)))

    for i in range(len(nums)): 
        # Find the smallest number > nums[i] among available indices.
        found_greater = False
        for j in range(len(nums)): 
            if j in available_indices and nums[j] > nums[i]:
                #Remove selected number.
                available_indices.remove(j)
                greatness += 1
                found_greater = True
                break

    return greatness

def maximizeGreatnessOptimal(nums):
    nums.sort()
    group_size = len(nums)
    greatness_score = 0
    available_index = 0

    for current_index in range(group_size):
        # Crucial optimization: Advance until you find a suitable greater element.
        while available_index < group_size and nums[current_index] >= nums[available_index]:
            available_index += 1

        #This means no greater number was found.
        if available_index == group_size:
            break

        # Count this as 'great', advance to the next element.
        greatness_score += 1
        available_index += 1 #Consume this number.

    return greatness_score

def maximizeGreatnessBest(nums):
    nums.sort()
    group_size = len(nums)
    greatness_score = 0
    available_index = 0

    for current_index in range(group_size):
        # Find next greater element.
        while available_index < group_size and nums[current_index] >= nums[available_index]:
            available_index += 1

        # If found, increment count.  If not, break.
        if available_index < group_size:
            greatness_score += 1
            available_index += 1
        else:
            break

    return greatness_score

def maximizeGreatnessConcise(nums):
    nums.sort()
    group_size = len(nums)
    greatness_score = 0
    available_index = 0

    for current_index in range(group_size):
        # Increment available_index to find first greater element.
        while available_index < group_size and nums[current_index] >= nums[available_index]:
            available_index += 1

        # Found greater element. Increase greatness and consume number
        if available_index < group_size:
            greatness_score += 1
            available_index += 1

    return greatness_score

def maximizeGreatnessSimplified(nums):
    nums.sort()
    greatness_count = 0
    right_pointer = 0

    for left_pointer in range(len(nums)):
        # Advance the right pointer until a greater element is found
        while right_pointer < len(nums) and nums[left_pointer] >= nums[right_pointer]:
            right_pointer += 1

        # A greater element was found, increment the greatness
        if right_pointer < len(nums):
            greatness_count += 1
            right_pointer += 1 # Consume the number.

    return greatness_count

def maximizeGreatnessFinal(nums):
    nums.sort()
    greatness_count = 0
    right_index = 0

    for left_index in range(len(nums)):
        # Advance the right index to find a greater element.
        while right_index < len(nums) and nums[left_index] >= nums[right_index]:
            right_index += 1

        # Check if a greater number was found.
        if right_index < len(nums):
            greatness_count += 1
            right_index += 1
        # If no greater number found, move to next left index.

    return greatness_count

def maximizeGreatnessProduction(nums):
    nums.sort()
    greatness = 0
    next_available_index = 0

    for i in range(len(nums)):
        # Find the next greater element.
        while next_available_index < len(nums) and nums[i] >= nums[next_available_index]:
            next_available_index += 1

        # If a greater element is found, increment greatness.
        if next_available_index < len(nums):
            greatness += 1
            next_available_index += 1

    return greatness

def maximizeGreatnessOptimized(nums):
    nums.sort()
    greatness_score = 0
    available_index = 0
    number_count = len(nums)

    for current_index in range(number_count):
        # Increment available_index until a greater number is found.
        while available_index < number_count and nums[current_index] >= nums[available_index]:
            available_index += 1

        # If a greater number is found, increment greatness.
        if available_index < number_count:
            greatness_score += 1
            available_index += 1

    return greatness_score

def maximizeGreatnessRefactored(nums):
    nums.sort()
    greatness = 0
    available_index = 0

    for i in range(len(nums)):
        # Find the smallest available number that's larger than the current number.
        while available_index < len(nums) and nums[i] >= nums[available_index]:
            available_index += 1

        #If a larger number exists, increase greatness and advance to the next available number
        if available_index < len(nums):
            greatness += 1
            available_index += 1

    return greatness

def maximizeGreatnessFinalVersion(nums):
    nums.sort()
    greatness_count = 0
    next_available_index = 0

    for current_index in range(len(nums)):
        # Find the smallest available number that is greater than the current number.
        while next_available_index < len(nums) and nums[current_index] >= nums[next_available_index]:
            next_available_index += 1

        # If a greater number is found, increment the greatness count.
        if next_available_index < len(nums):
            greatness_count += 1
            next_available_index += 1

    return greatness_count

def maximizeGreatnessMostConcise(numbers):
    numbers.sort()
    greatness_score = 0
    next_available_index = 0

    for i in range(len(numbers)):
        # Find the next greater number.
        while next_available_index < len(numbers) and numbers[i] >= numbers[next_available_index]:
            next_available_index += 1

        #Increase greatness, move to next number, if found.
        if next_available_index < len(numbers):
            greatness_score += 1
            next_available_index += 1

    return greatness_score

def maximizeGreatness(numbers):
    numbers.sort()
    greatness_score = 0
    next_available_number_index = 0

    for i in range(len(numbers)):
        # Find next number that is greater.
        while next_available_number_index < len(numbers) and numbers[i] >= numbers[next_available_number_index]:
            next_available_number_index += 1

        # Update and advance only if the current number is smaller.
        if next_available_number_index < len(numbers)):
            greatness_score += 1
            next_available_number_index += 1

    return greatness_score

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input array	Return 0 immediately, as there are no elements to reorder.
Array with only one element	Return 0, as it's impossible to have nums[i] != original nums[i] and nums[i] > original nums[i] simultaneously.
Array with all identical elements (e.g., [5, 5, 5, 5])	Return 0, as no reordering can satisfy nums[i] > original nums[i].
Array with a large number of elements (e.g., 10^5)	The algorithm should have a time complexity of O(n log n) or better to avoid exceeding time limits, suggesting sorting or efficient data structures.
Array with elements that are already sorted in ascending order	The algorithm should still correctly calculate the maximum greatness by appropriately pairing elements.
Array with elements that are sorted in descending order	The algorithm should be able to handle reverse-sorted arrays and find the optimal reordering.
Array containing both very small and very large numbers	The algorithm should correctly handle the wide range of values without causing overflow or other numerical issues.
Array with many duplicate elements that also appear in close proximity	Sorting and a two-pointer approach can efficiently handle cases with many duplicate numbers clustered together.