# Issue

"Assume you have a road (or numberline) with lights over head that light up a section of the numberline. Lights are represented by a 2D array where the light at index i covers from arr[i][0] to arr[i][1] (inclusive).

You are also given a list of points on this line, and for each point, you want to compute how many lights illuminate that point. I want to return a list where list[i] = the number of lights that illuminate point i."

Sample input/output: `lights = [[1, 7], [5, 11], [7, 9]], points = [7, 1, 5]`

should return `[3, 1, 2]`

I wrote a solution where for each point in points, you loop over the lights array and see how many have lights[i][0] <= point <= lights[i][1]. This solution is too slow (being O(n *k) where n = num. lights and k = num. points). I also tried sorting the lamps and breaking when lamp[i][0] > point, but it still times out. Can anyone think of a faster algorithm to compute this array? I'm stumped on how else to approach this.

# Solution

This problem is better solved like this:

Get all the changes from the lights array and create an array that has twice its size. It will have tuples of point and light-change. The light change component is +1 or -1, depending on whether that point represents the

*beginning*of the light span or*end*of it. When it is the end, the point should be one more than found in the lights array, so to indicate that point is still reached by the light, and we should only discount it when moving to the right to the next point.Sort this result by point. There might be duplicates.

Then accumulate from left to right the light-change values, so adding up all those -1 and +1 from left to right, and storing the intermediate results again with the point where the light-change was found. The final accumulated value will of course be 0.

Optionally make that array unique by point, only keeping the right most of the duplicate points, as those have the right accumulated value to go with it. (I did not do that in below implementation)

Finally use binary search on that array to translate each given point to the number of lights that shine on that point.

### Implementation:

```
from bisect import bisect
def solve(lights, points):
pairs = sorted((x + i, -i or 1) for changes in lights for i, x in enumerate(changes))
offsets, changes = zip(*pairs)
total = 0
cumul = [0] + [total := total + change for change in changes]
return [cumul[bisect(offsets, x)] for x in points]
lights = [[1, 7], [5, 11], [7, 9]]
points = [7, 1, 5]
print(solve(lights, points)) # [3, 1, 2]
```

And here is the version that removes duplicates. It is only of benefit if there really are many duplicate offsets in the `cumul`

list:

```
def solve(lights, points):
pairs = sorted((x + i, -i or 1) for changes in lights for i, x in enumerate(changes))
total = 0
cumulpairs = [(x, total := total + change) for x, change in pairs]
# remove duplicates - assuming Python 3.7+ with ordered dicts
offsets, cumul = zip(*dict(cumulpairs).items())
cumul = [0] + list(cumul)
return [cumul[bisect(offsets, x)] for x in points]
```

Answered By - trincot Answer Checked By - Dawn Plyler (PHPFixing Volunteer)

## 0 Comments:

## Post a Comment

Note: Only a member of this blog may post a comment.