2070. Most Beautiful Item for Each Query
Approach
Sort items; build prefix max beauty array; binary search per query for affordable max beauty.
Key Techniques
Array problems involve manipulating elements stored in a contiguous block of memory. Key techniques include two-pointer traversal, prefix sums, sliding windows, and in-place partitioning. In C#, arrays are zero-indexed and fixed in size — use List<T> when you need dynamic resizing.
Binary search reduces search space by half each step, giving O(log n) time. Beyond sorted arrays, apply it on the answer space ("binary search on result") when you can define a monotonic predicate — e.g., "can we achieve X with k resources?"
Sorting is often a preprocessing step that enables binary search, two-pointer sweeps, or greedy algorithms. C#'s Array.Sort() uses an introspective sort (O(n log n)). Custom comparisons use the Comparison<T> delegate or IComparer<T>. Consider counting sort or bucket sort for bounded integer inputs.
// Approach: Sort items; build prefix max beauty array; binary search per query for affordable max beauty.
// Time: O((n + q) log n) Space: O(n)
public class Solution
{
public int[] MaximumBeauty(int[][] items, int[] queries)
{
int[] ans = new int[queries.Length];
int[] maxBeautySoFar = new int[items.Length + 1];
Array.Sort(items, (a, b) => a[0].CompareTo(b[0]));
for (int i = 0; i < items.Length; ++i)
maxBeautySoFar[i + 1] = Math.Max(maxBeautySoFar[i], items[i][1]);
for (int i = 0; i < queries.Length; ++i)
{
int index = FirstGreater(items, queries[i]);
ans[i] = maxBeautySoFar[index];
}
return ans;
}
private int FirstGreater(int[][] items, int q)
{
int l = 0;
int r = items.Length;
while (l < r)
{
int m = (l + r) / 2;
if (items[m][0] > q)
r = m;
else
l = m + 1;
}
return l;
}
}