The power and simplicity of IComparer

This problem requires a fast sorting implementation (QuickSort). Luckily we no longer have to memorize how that wonderful implementation works (for more fun historical information about QuickSort, take a look at my interview with its creator, right here My Quickshort interview with Sir Tony Hoare, the inventor of Quicksort (anothercasualcoder.blogspot.com)). Instead, we can make use of the Array.Sort and the IComparer interface. Implementing IComparer is very simple, you can even make use of the .Compare() implementation for each type too.

Back to this problem, it can be solved in NLogN:

1/ Sort the items (using IComparer): NLogN

2/ For each item determine the max beauty: N

3/ For each query perform a binary search: NLogN

Code is down below, cheers, ACC.

Most Beautiful Item for Each Query - LeetCode

2070. Most Beautiful Item for Each Query

Medium

You are given a 2D integer array items where items[i] = [pricei, beautyi] denotes the price and beauty of an item respectively.

You are also given a 0-indexed integer array queries. For each queries[j], you want to determine the maximum beauty of an item whose price is less than or equal to queries[j]. If no such item exists, then the answer to this query is 0.

Return an array answer of the same length as queries where answer[j] is the answer to the jth query.

 

Example 1:

Input: items = [[1,2],[3,2],[2,4],[5,6],[3,5]], queries = [1,2,3,4,5,6]
Output: [2,4,5,5,6,6]
Explanation:
- For queries[0]=1, [1,2] is the only item which has price <= 1. Hence, the answer for this query is 2.
- For queries[1]=2, the items which can be considered are [1,2] and [2,4]. 
  The maximum beauty among them is 4.
- For queries[2]=3 and queries[3]=4, the items which can be considered are [1,2], [3,2], [2,4], and [3,5].
  The maximum beauty among them is 5.
- For queries[4]=5 and queries[5]=6, all items can be considered.
  Hence, the answer for them is the maximum beauty of all items, i.e., 6.

Example 2:

Input: items = [[1,2],[1,2],[1,3],[1,4]], queries = [1]
Output: [4]
Explanation: 
The price of every item is equal to 1, so we choose the item with the maximum beauty 4. 
Note that multiple items can have the same price and/or beauty.  

Example 3:

Input: items = [[10,1000]], queries = [5]
Output: [0]
Explanation:
No item has a price less than or equal to 5, so no item can be chosen.
Hence, the answer to the query is 0.

 

Constraints:

• 1 <= items.length, queries.length <= 105
• items[i].length == 2
• 1 <= pricei, beautyi, queries[j] <= 109

public class Solution {
    public class MyComparer : IComparer
    {
        public int Compare(Object x, Object y)
        {
            return ((int[])x)[0].CompareTo(((int[])y)[0]);
        }
    }

    public int[] MaximumBeauty(int[][] items, int[] queries)
    {
        Array.Sort(items, new MyComparer());

        for (int i = 1; i < items.Length; i++)
        {
            items[i][1] = Math.Max(items[i][1], items[i - 1][1]);
        }

        int[] retVal = new int[queries.Length];
        for (int i = 0; i < queries.Length; i++)
        {
            retVal[i] = BinarySearch(items, queries[i]);
        }

        return retVal;
    }

    public int BinarySearch(int[][] items, int maxPrice)
    {
        int left = 0;
        int right = items.Length - 1;

        while (left < right)
        {
            int mid = (left + right) / 2;
            if (items[mid][0] <= maxPrice) left = mid + 1;
            else right = mid;
        }

        if (items[left][0] <= maxPrice) return items[left][1];
        if (left - 1 >= 0) return items[left - 1][1];
        return 0;
    }
}