FunctionRacerProblemsRace

Brighten the Darkest House

HardSorting and searchingPython, JavaScript, TypeScript, Java, C++

Houses stand in a row, and lamps[i] lamps stand at house i. A lamp at house i lights every house j with |i - j| <= reach. The brightness of a house is the number of lamps that light it.

You may put up extra more lamps, at any houses you like, several at one house if you wish. Return the largest brightness the darkest house can have afterwards.

Example 1

lamps [1,0,0,0,1]
reach 1
extra 1
returns 1

The brightness is 1, 1, 0, 1, 1. A new lamp at the middle house lifts that house to 1. The two end houses stay at 1.

Example 2

lamps [2,0,1]
reach 0
extra 4
returns 2

With reach 0 a house has only its own lamps. Three new lamps bring every house to 2, and the fourth cannot lift all three houses.

Constraints

Race itor take your time

Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.

More Sorting and searching problems