A flight search caches a fixed list of daily fares, fares, for the next few months. The calendar widget sends many questions of the form "what is the cheapest fare from day left to day right?". The fares don't change while the widget is open.
Write cheapestFares(fares, queries) where each query is [left, right] (inclusive). Return an array with the cheapest fare for each query, in the same order. Aim for O(1) per query after some preparation.
Input: fares = [4,6,1,5,7,3], queries = [[3,5],[0,1],[0,5]] Output: [3,4,1]
Days 3 to 5 are 5, 7, 3, so 3; days 0 to 1 give 4; the whole list gives 1.
Input: fares = [9], queries = [[0,0]] Output: [9]
One day, one fare.
1 <= fares.length <= 10^51 <= fares[i] <= 10^60 <= queries.length <= 10^50 <= left <= right < fares.lengthRun tries your code on the examples. Submit runs every test, including hidden edge cases, and solves the problem when they all pass.
Ctrl + Enter runs, Ctrl + Shift + Enter submits (⌘ on a Mac).
I'm here to help with #691 Lowest Price in Many Ranges. I give hints, never the solution, so you get to solve it yourself. Ask for a hint, select code to ask about it, or press Ask Tuto why on a failing test.
Your first 3 answers need no account. for free to keep asking.