We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximize Greatness of an Array

Number: 2664

Difficulty: Medium

Paid? No

Companies: Nvidia, Twilio, Oracle, Salesforce, BlackRock

Problem Description

Given an integer array nums, you can permute it into any new array perm. The greatness of an array is defined as the count of indices i such that perm[i] > nums[i]. Your task is to maximize the greatness by choosing an optimal permutation of nums.

Key Insights

  • Sorting the array allows us to view the elements in a natural order.
  • Use a two-pointer greedy approach to pair each original element with the smallest available element from the sorted list that is strictly greater.
  • The optimal pairing strategy is similar to maximizing wins in a matching game.
  • Greedily increment the pair count when a valid pairing (perm[i] > nums[i]) is found.

Space and Time Complexity

Time Complexity: O(n log n), primarily due to sorting. Space Complexity: O(n), for storing the sorted array and additional pointers.

Solution

  1. Sort the given array nums, which gives a clear ordering of the numbers.
  2. Use two pointers: one (i) for iterating over the sorted original array, and another (j) for selecting a candidate from the sorted array that might be placed in the perm array.
  3. If the candidate value (at pointer j) is strictly greater than the current original value (at pointer i), it is a valid match; increment the count and move both pointers.
  4. If the candidate is not larger, move the candidate pointer j alone.
  5. Continue until all potential matches are exhausted. The count represents the maximum possible greatness.

Code Solutions

# Python code with detailed comments
def maximizeGreatness(nums):
    # Sort the array to get natural order of elements.
    sorted_nums = sorted(nums)
    n = len(sorted_nums)
    
    # Initialize two pointers and a counter for valid pairings (greatness).
    i, j, count = 0, 0, 0
    
    # Use two-pointer technique: pointer i for the base (original sorted order)
    # and pointer j for candidate from the sorted array.
    while i < n and j < n:
        # We want sorted_nums[j] (candidate) to be greater than sorted_nums[i] (base).
        if sorted_nums[j] > sorted_nums[i]:
            count += 1  # valid pairing found
            i += 1    # move to next base element
            j += 1    # use the current candidate
        else:
            # Current candidate cannot beat sorted_nums[i], try next candidate.
            j += 1
    return count

# Example usage:
nums = [1, 3, 5, 2, 1, 3, 1]
print(maximizeGreatness(nums))  # Expected output: 4
← Back to All Questions