FastPrep
Problem · Array

Optimal Lamp Coordinate

Learn this problem
● MediumCapital One logoCapital OneINTERNOA

Problem statement

You are given a strictly increasing integer array objects containing the coordinates of objects on a number line, and a nonnegative integer radius.

Place one lamp at any integer coordinate c. The lamp illuminates every object whose coordinate lies in the inclusive interval [c - radius, c + radius].

Return a coordinate that illuminates the maximum possible number of objects. If several coordinates illuminate that maximum number, return the smallest such coordinate.

Function

optimalLampCoordinate(objects: int[], radius: int) → int

Examples

Example 1

objects = [-5,3,4,9]radius = 5return = -1

A lamp at -1 illuminates the objects at -5, 3, and 4. No coordinate can illuminate all four objects. Other coordinates can also illuminate three objects, but -1 is the smallest one that does so.

Example 2

objects = [1,2,8]radius = 1return = 1

A lamp at 1 covers the inclusive interval [0,2], illuminating the first two objects. No lamp can illuminate all three, and 1 is the smallest coordinate that illuminates two.

Example 3

objects = [7]radius = 3return = 4

Every lamp coordinate from 4 through 10 illuminates the only object. The smallest valid coordinate is 4.

Constraints

  • 1 <= objects.length <= 2 * 10^5
  • -10^9 <= objects[i] <= 10^9
  • objects is strictly increasing.
  • 0 <= radius <= 10^9

More Capital One problems

drafts saved locally
public int optimalLampCoordinate(int[] objects, int radius) {
    // Write your code here.
}
objects[-5,3,4,9]
radius5
expected-1
checking account