Binary Search to Find Next Greater Element II

Very similar problem as solved in a different blog post, the only caveat here is that if the result of the Binary Search does not yield a greater value than the target, return the smallest one (this is the difference that I'm referring to). Code is down below, cheers, ACC.

Maximize Greatness of an Array - LeetCode

2592. Maximize Greatness of an Array

Medium

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 <= 105
• 0 <= nums[i] <= 109

Accepted

12,887

Submissions

23,143

public int MaximizeGreatness(int[] nums)
{
    int[] clone = (int[])nums.Clone();
    Array.Sort(nums);
    List sortedList = nums.ToList();
    int retVal = 0;

    for (int i = 0; i < clone.Length; i++)
    {
        int index = NextMaxBinarySearch(clone[i], sortedList);
        retVal = (sortedList[index] > clone[i]) ? retVal + 1 : retVal;
        sortedList.RemoveAt(index);
    }

    return retVal;
}

private int NextMaxBinarySearch(int val,
                                List sortedNums)
{
    int left = 0;
    int right = sortedNums.Count - 1;
    while (left < right)
    {
        int mid = (left + right) / 2;
        if (sortedNums[mid] > val)
        {
            right = mid;
        }
        else
        {
            left = mid + 1;
        }
    }

    if (sortedNums[left] > val) return left;
    return 0;
}