FastPrep
Problem · Array

Find Point Illuminated by Most Lamps

Learn this problem
● MediumUber logoUberOA
See Uber hiring insights

Problem statement

There are some lamps placed on a coordinate line. Each of these lamps illuminates some space around it within a given radius. You are given the coordinates of the lamps on the line, and the effective radius of the lamps' light.

In other words, you are given a two-dimensional array lamps, where lamps[i] contains information about the ith lamp. lamps[i][0] is an integer representing the lamp's coordinate, and lamps[i][1] is a positive integer representing the effective radius of the ith lamp. That means that the ith lamp illuminates everything in a range from lamps[i][0] - lamps[i][1] to lamps[i][0] + lamps[i][1] inclusive.

Your task is to find the coordinate of the point that is illuminated by the highest number of lamps. In case of a tie, return the point among them with the minimal possible coordinate.

Function

solution(lamps: int[][]) → int

Examples

Example 1

lamps = [[-2, 3], [2, 3], [2, 1]]return = 1

The first lamp illuminates everything in range [-5, 1]. The second lamp illuminates everything in range [-1, 5]. The third lamp illuminates everything in range [1, 3].

The only point that is illuminated by all of the lamps is 1, hence the answer is 1.

Example 2

lamps = [[-2, 1], [2, 1]]return = -3

The given lamps illuminate ranges [-3, -1] and [1, 3] respectively. Every point in these ranges are illuminated by only 1 lamp, but the one with the minimal coordinate among them is -3, so it is the answer.

More Uber problems

drafts saved locally
public int solution(int[][] lamps) {
    // write your code here
}
lamps[[-2, 3], [2, 3], [2, 1]]
expected1
checking account