FastPrep
Problem · Array

Farthest Affordable Shop per Query

Learn this problem
● MediumAdobe logoAdobeFULLTIMEONSITE INTERVIEW

Problem statement

A street has an ordered array shopCosts, where shopCosts[i] is the amount required to visit shop i.

Each row of queries is [start, budget]. Begin at the zero-based shop start and visit consecutive shops to the right. Visiting a shop spends its cost, including the starting shop.

For each query, return the farthest shop index you can visit without spending more than budget. Return -1 when the starting shop itself is unaffordable. Each query is independent.

Function

farthestAffordableShops(shopCosts: int[], queries: int[][]) → int[]

Examples

Example 1

shopCosts = [2,4,1,3]queries = [[0,7],[1,4],[2,10],[3,2]]return = [2,1,3,-1]

The first query spends 2 + 4 + 1 and reaches shop 2. The last budget cannot pay the cost at shop 3.

Example 2

shopCosts = [1,1,1]queries = [[0,2],[1,2]]return = [1,2]

A budget of 2 pays for two consecutive unit-cost shops from either starting point.

Constraints

  • 1 <= shopCosts.length <= 100000
  • 1 <= queries.length <= 100000
  • 0 <= shopCosts[i] <= 10^9
  • Each query is [start, budget], where 0 <= start < shopCosts.length and 0 <= budget <= 10^9.
  • Use signed 64-bit arithmetic for prefix sums.

More Adobe problems

drafts saved locally
public int[] farthestAffordableShops(int[] shopCosts, int[][] queries) {
    // Write your code here.
}
shopCosts[2,4,1,3]
queries[[0,7],[1,4],[2,10],[3,2]]
expected[2,1,3,-1]
checking account