Count Lamps Lighting Each Point
Updated
Problem statement
Write lit(x) for how many lamps light position x, where lamp i lights x when lamps[i][0] <= x <= lamps[i][1]. All values lie on one number line. With q entries in points, return the array [lit(points[0]), lit(points[1]), ..., lit(points[q - 1])].
- The answer has exactly
qentries, so a value that appears inpointsmore than once is answered every time it appears. - When
lamps[i][0]equalslamps[i][1], lampilights that single position. - Two rows of
lampsholding the same pair are two different lamps, so a position inside that range gets 2 from them, not 1.
A good solution runs in about O((n + q) log n) time for n lamps. The official tests are small enough that checking every lamp against every point also finishes in time.
Function
lampsPerPoint(lamps: int[][], points: int[]) → int[]Examples
Example 1
lamps = [[-6,-2],[-4,3],[3,8]]points = [-5,-2,3,9]return = [1,2,2,0]-5: inside[-6, -2]only, so 1.-2: the right end of[-6, -2]and inside[-4, 3], so 2.3: the right end of[-4, 3]and the left end of[3, 8], so 2.9: past every lamp, so 0.
Example 2
lamps = [[0,100],[20,30],[25,25]]points = [25,99,-1,30]return = [3,1,0,2]25: inside all three, including the one-point lamp[25, 25], so 3.99: only the wide lamp[0, 100], so 1.-1: left of every lamp, so 0.30:[0, 100]and the right end of[20, 30], so 2.
The counts follow the order of points, not sorted order.
Example 3
lamps = [[-1000000000,1000000000]]points = [1000000000,-1000000000,0]return = [1,1,1]The single lamp spans the whole allowed range, ends included, so every point gets a count of 1.
Example 4
lamps = [[-8,-1],[3,10],[-8,-1],[0,5]]points = [0,7,-4,7]return = [1,1,2,1]0: the left end of[0, 5]. Both[-8, -1]lamps stop at-1, so 1.7: only[3, 10]reaches it, so 1.-4: inside[-8, -1], which is listed twice, in rows 0 and 2. Each row is its own lamp, so 2.- The last query repeats
7and gets its own entry, 1.
Constraints
1 <= lamps.length <= 5000lamps[i].length == 2-10^9 <= lamps[i][0] <= lamps[i][1] <= 10^91 <= points.length <= 5000-10^9 <= points[j] <= 10^9
More Capital One Online Assessment questions
- Rank Football TeamsOA · Seen Oct 2026
- Count Subarrays Matching a Comparison PatternOA · Seen Oct 2026
- Arithmetic Triplets After QueriesOA · Seen Oct 2026
- Branch with the Most FilesOA · Seen Oct 2026
- Count One-Swap Number PairsOA · Seen Oct 2026
- Distinct Values on Maximum-Sum FramesOA · Seen Oct 2026
- Earliest Meeting Time for All EmployeesOA · Seen Oct 2026
- Earn the Most 🐝OA · Seen Oct 2026
- Sort Adjacent PairsOA · Seen Oct 2026
- Bouncing Diagonal WeightsOA · Seen Oct 2026
Similar questions at other companies
- Choose ContainersIMC Trading · OAIMC Trading interview questions
- Calculating QuantilesIndeed · OAIndeed interview questions
- Minimum Cost to Make Array EqualWalmart · OAWalmart interview questions
- Subscription and Usage-Based Billing CalculatorStripe · OAStripe interview questions
- Maximum Interactive Team SizeMicrosoft · OAMicrosoft interview questions
- Linear InterpolatorTwo Sigma · OATwo Sigma interview questions
- Minimum Seats for One-Way Car PoolingSquadStack.ai · OA
- Find Sum of BeautiesAmazon · OA
- Minimize Maximum Group DifferenceDRW · OADRW interview questions
- Maximum Riders in CarUber · OAUber interview questions
Capital One interview experiences
- Capital One Experienced Engineer Power Day and OA: 6 Experiences
- Capital One New Grad OA Questions: 14 Experiences (Part 2 of 2)
- Capital One TDP Agentic Round (AI Coding): 7 Experiences
- Capital One SWE Power Day, Level Not Reported: 6 Experiences
- Capital One TIP Intern OA and Power Day: 13 Experiences
- Capital One TDP Agentic Power Day: 25 Experiences (Part 1 of 2)