Most Beautiful Item for Each Query

Leetcode Problem:

• Most Beautiful Item for Each Query

Summary

• Given a 2D integer array of item prices and beauties, and a 0-indexed integer array of queries, determine the maximum beauty of an item whose price is less than or equal to each query.

Approach

• The solution uses a modified merge sort algorithm to sort the items based on their prices
• Then, it iterates over the sorted items and updates the beauty of each item if its price is less than the current query
• Finally, it uses a binary search approach to find the maximum beauty for each query.

Complexity

• O(n log n + m log n), where n is the number of items and m is the number of queries.

Explanation

• The modified merge sort algorithm sorts the items based on their prices and then updates the beauty of each item if its price is less than the current query
• This is done to ensure that the items are sorted in ascending order of their prices
• The binary search approach is used to find the maximum beauty for each query by finding the first item whose price is greater than the query and returning its beauty.

Solution Code:

struct _item{
    int price;
    int beauty;
};

class Solution {
public:
    _item arr[100001];
    _item tmp[100001];
    void merge(int l, int mid, int r){
        int i = l;
        int j = mid + 1;
        int cur = l;
        while(i <= mid & j <= r){
            if(arr[i].price < arr[j].price){
                tmp[cur++] = arr[i++];
            } else if (arr[i].price > arr[j].price){
                tmp[cur++] = arr[j++];
            } else{
                if(arr[i].beauty >= arr[j].beauty){
                    tmp[cur++] = arr[i++];
                } else {
                    tmp[cur++] = arr[j++];
                }
            }
        }
        while(i<= mid){
            tmp[cur++] = arr[i++];
        }
        for(i = l; i < cur; i++){
            arr[i] = tmp[i];
        }
    }
    void merge_sort(int l, int r){
        if(l >= r) return;
        int mid = (l + r) / 2;
        merge_sort(l, mid);
        merge_sort(mid+1, r);
        merge(l, mid, r);
    }
    vector maximumBeauty(vector>& items, vector& queries) {
        for(int i = 0 ; i < items.size(); i++){
            arr[i].price = items[i][0];
            arr[i].beauty = items[i][1];
        }
        merge_sort(0, items.size() - 1);
        int maxBeauty = arr[0].beauty;
        for(int i = 1 ; i < items.size(); i++){
            if(arr[i].beauty < maxBeauty){
                arr[i].beauty = maxBeauty;
            } else {
                maxBeauty = arr[i].beauty;
            }
        }
        vector ansV;
        for(int i = 0 ; i < queries.size(); i++){
            int l = 0;
            int r = items.size() - 1;
            int ans = 0;
            while(l <= r){
                int mid = (l + r ) / 2;
                if (arr[mid].price > queries[i]){
                    r = mid - 1;
                    continue;
                }
                ans = arr[mid].beauty;
                l = mid + 1;
            }
            ansV.push_back(ans);
        }
        return ansV;
    }
};