Most Beautiful Item for Each Query - Practice Coding Problems

Most Beautiful Item for Each Query - Problem

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.

Input & Output

Example 1 — Basic Case

$ Input: items = [[1,2],[3,2],[2,4]], queries = [1,2,3]

› Output: [2,4,4]

💡 Note: Query 1: Only item [1,2] is affordable, beauty = 2. Query 2: Items [1,2] and [2,4] are affordable, max beauty = 4. Query 3: All items affordable, max beauty = 4.

Example 2 — No Affordable Items

$ Input: items = [[10,1000]], queries = [5]

› Output: [0]

💡 Note: Query 5: The only item costs 10, which exceeds budget of 5, so return 0.

Example 3 — Multiple Queries

$ Input: items = [[1,2],[1,2],[1,3],[1,4]], queries = [1,1]

› Output: [4,4]

💡 Note: All items have price 1, so for budget 1, we can afford all items. Maximum beauty among all is 4.

Constraints

1 ≤ items.length ≤ 10⁵
1 ≤ price_i, beauty_i, queries[j] ≤ 10⁹
1 ≤ queries.length ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input

Items with [price, beauty] and query budgets

Process

For each query, find items within budget and maximum beauty

Output

Array of maximum beauties for each query

Key Takeaway

🎯 Key Insight: Preprocess items by sorting and computing running maximum beauty to enable efficient binary search queries

Asked in

a Amazon 45 G Google 38 M Microsoft 32 f Meta 28

The key insight is to sort items by price and precompute maximum beauty achievable up to each price point, enabling binary search for queries. Best approach uses binary search with preprocessing for optimal O(n log n + m log n) time complexity.

Common Approaches

Approach	Time	Space	Notes
✓ Binary Search with Preprocessing	O(n log n + m log n)	O(n)	Sort items by price and precompute maximum beauty, then binary search for each query
Brute Force	O(n × m)	O(1)	For each query, scan all items to find maximum beauty within budget
Sort and Linear Search	O(n log n + n × m)	O(1)	Sort items by price, then for each query scan sorted items to find maximum beauty

Binary Search with Preprocessing — Algorithm Steps

Sort items by price
Precompute maximum beauty up to each price point
For each query, binary search to find valid price range
Return precomputed maximum beauty

Visualization

Tap to expand

Step-by-Step Walkthrough

Sort and Preprocess

Sort by price and compute running maximum beauty

Binary Search

Find rightmost item within budget using binary search

Lookup Result

Return precomputed maximum beauty

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int compare(const void* a, const void* b) {
    int* itemA = (int*)a;
    int* itemB = (int*)b;
    return itemA[0] - itemB[0];
}

int* solution(int items[][2], int itemsSize, int* queries, int queriesSize, int* returnSize) {
    // Sort items by price
    qsort(items, itemsSize, sizeof(int) * 2, compare);
    
    // Precompute maximum beauty up to each price point
    int maxBeauty = 0;
    for (int i = 0; i < itemsSize; i++) {
        if (items[i][1] > maxBeauty) {
            maxBeauty = items[i][1];
        }
        items[i][1] = maxBeauty;
    }
    
    *returnSize = queriesSize;
    int* result = (int*)malloc(queriesSize * sizeof(int));
    
    for (int i = 0; i < queriesSize; i++) {
        // Binary search for rightmost position where price <= query
        int left = 0, right = itemsSize;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (items[mid][0] <= queries[i]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        
        if (left == 0) {
            result[i] = 0;
        } else {
            result[i] = items[left - 1][1];
        }
    }
    
    return result;
}

int main() {
    // Example hardcoded input
    int items[3][2] = {{1,2},{3,2},{2,4}};
    int queries[3] = {1,2,3};
    int itemsSize = 3, queriesSize = 3;
    
    int returnSize;
    int* result = solution(items, itemsSize, queries, queriesSize, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n + m log n)

Sorting and preprocessing takes O(n log n), each query uses binary search O(log n)

⚡ Linearithmic

Space Complexity

O(n)

Storing sorted items and precomputed maximum beauty values

⚡ Linearithmic Space

34.5K Views

High Frequency

~25 min Avg. Time

967 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Binary Search with Preprocessing — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler