FastPrep
Problem · Array

Maximum Laptop Rating in a Price Range

Learn this problem
● HardPostman logoPostmanINTERNOA

Problem statement

You are given n laptops. Laptop i has price prices[i] and rating ratings[i].

For each inclusive price query [low, high], return the maximum rating among laptops whose price is between low and high. Return -1 for a query whose price range contains no laptop.

Multiple laptops may have the same price; all of them are eligible for a matching query.

Function

maximumRatings(prices: int[], ratings: int[], queries: int[][]) → int[]

Examples

Example 1

prices = [1000,1100,1300,1700,2000]ratings = [300,400,200,500,600]queries = [[1000,1400],[1700,1900],[0,2000]]return = [400,500,600]

The highest eligible ratings for the three inclusive ranges are 400, 500, and 600, respectively.

Example 2

prices = [5,1,9]ratings = [40,10,30]queries = [[1,9],[2,8]]return = [40,40]

The full range has maximum rating 40. The narrower range includes only the laptop priced at 5, which also has rating 40.

Constraints

  • 1 ≤ prices.length = ratings.length ≤ 10^6
  • 1 ≤ queries.length ≤ 10^6
  • 1 ≤ prices[i], ratings[i] ≤ 10^9
  • Each query contains exactly two values [low, high] with 0 ≤ low ≤ high ≤ 10^9.

More Postman problems

drafts saved locally
public int[] maximumRatings(int[] prices, int[] ratings, int[][] queries) {
    // write your code here
}
prices[1000,1100,1300,1700,2000]
ratings[300,400,200,500,600]
queries[[1000,1400],[1700,1900],[0,2000]]
expected[400,500,600]
checking account