Katkat
Back

Find the Row Watched by the Most Security Cameras

Capital OneSoftware Engineer · Online Assessment
MediumSoftware EngineerOnline AssessmentCoding & Algorithms

Last updated

Each security camera covers a symmetric band of rows around its mounted position; find the integer row watched by the most cameras, breaking ties toward the smallest row number, using a sweep-line count instead of scanning every covered row.

A warehouse's shelving is modeled as a single line of integer row numbers. You're given cameras, where cameras[i] = [center_i, spread_i] describes a security camera mounted at row center_i that watches every row from center_i - spread_i to center_i + spread_i, inclusive on both ends.

The coverage count of a row r is the number of cameras that watch it. Return the row with the highest coverage count; if several rows tie for the maximum, return the smallest one.

Function Signature

def busiest_row(cameras: list[list[int]]) -> int:

Rules

  • Only integer rows matter.
  • A camera with spread_i = 0 watches only its own center_i.
  • Multiple cameras can share the same center_i; each counts separately.
  • cameras is non-empty, so a busiest row always exists and the maximum coverage is at least 1.

Constraints

  • 1 <= len(cameras) <= 10^5
  • -10^8 <= center_i <= 10^8
  • 0 <= spread_i <= 10^8
  • Every watched row fits comfortably in a 32-bit signed integer.

Examples

cameras = [[1, 3], [8, 2], [4, 2]]
busiest_row(cameras)  # -> 2

The cameras watch [-2, 4], [6, 10], and [2, 6]. Rows 2, 3, and 4 are each watched by two cameras (the first and third), the maximum; the smallest of them is 2.

cameras = [[2, 0], [-2, 0]]
busiest_row(cameras)  # -> -2

Each camera watches only its own row, so 2 and -2 both have coverage 1, and -2 is the smaller.

cameras = [[14, 6], [2, 4], [11, 1]]
busiest_row(cameras)  # -> 10

The cameras watch [8, 20], [-2, 6], and [10, 12]. Rows 10, 11, and 12 are watched by two cameras (the first and third), the maximum; 10 is the smallest.

Hints

Hint 1

Coordinates range up to 10^8 in either direction, so don't build an array indexed by row — work with events instead.

Hint 2

Turn each camera into a '+1 coverage starts here' event at its left edge and a '-1 coverage ends after here' event at one past its right edge.

Hint 3

Sort all events by position and sweep left to right, keeping a running coverage total and tracking the best (count, smallest position) seen.

Hint 4

When several events share the same position, apply all of them before checking whether a new best has been reached — otherwise you might read the count mid-update.

Follow-up questions

  • How would you answer a follow-up query 'what is the coverage at row X?' efficiently after the sweep has already run once?
  • How would you report *all* rows that tie for the maximum coverage, not just the smallest?
  • How would the approach change if cameras could be added and removed dynamically, and you needed the busiest row after every update?
  • How would you adapt this if coverage needed to be weighted, so some cameras count more than others?