FastPrepRadar Barrier Crossing

Radar Barrier Crossing

Snap Inc. logoSnap Inc.● MediumFULLTIMEONSITE INTERVIEW
Learn

Problem statement

A rectangular area spans 0 <= x <= width and 0 <= y <= height. Each row [x, y, radius] in radars describes a closed circular detection region centered inside the rectangle.

An object wants to travel continuously from the left wall to the right wall without entering or touching any detection region. Two radar regions belong to the same component when their circles overlap or touch, directly or through other radars.

A left-to-right undetected crossing is impossible exactly when one connected radar component touches both the bottom wall and the top wall. Return true when an undetected crossing is possible; otherwise return false.

Function

canCrossUndetected(width: int, height: int, radars: int[][]) → boolean

Examples

Example 1

width = 10height = 10radars = [[5,2,3],[5,8,3]]return = false

The two circles touch. The lower one reaches the bottom wall and the upper one reaches the top wall, so their component forms a complete barrier.

Example 2

width = 12height = 10radars = [[2,2,2],[6,2,2],[10,2,2]]return = true

The horizontal component touches the bottom wall but not the top wall, so it does not separate the left and right walls.

Example 3

width = 8height = 6radars = []return = true

With no detection regions, an undetected left-to-right route exists.

Constraints

  • 1 <= width, height <= 10^9.
  • 0 <= radars.length <= 1000.
  • Every radar row contains exactly [x, y, radius].
  • 0 <= x <= width and 0 <= y <= height.
  • 0 <= radius <= 10^9.
  • Circle overlap, tangency, and wall contact are inclusive.
  • Use 64-bit arithmetic for squared-distance comparisons.

More Snap Inc. problems

See Snap Inc. hiring insights
public boolean canCrossUndetected(int width, int height, int[][] radars) {
    // Write your code here.
}
width10
height10
radars[[5,2,3],[5,8,3]]
expectedfalse
Checking account…