Busiest Station on a Grid
Updated
Problem statement
A city is a grid of width by height cells. A cell is written (x, y), where 0 <= x < width and 0 <= y < height. You are given stations, where stations[i] = [x, y] is the cell of station i.
Every cell of the grid, including the cells that hold stations, uses its nearest station. The distance between cells (x1, y1) and (x2, y2) is |x1 - x2| + |y1 - y2|, the number of steps when you can only move up, down, left or right. If a cell is equally near to several stations, it uses the one with the smallest index.
Return the index of the busiest station: the station used by the most cells. If several stations are used by the same, largest number of cells, return the smallest of their indexes.
Function
busiestStation(width: int, height: int, stations: int[][]) → intExamples
Example 1
width = 4height = 3stations = [[1,1],[3,2]]return = 0Write each cell's station number, one row per y. Row y = 0: 0 0 0 1. Row y = 1: 0 0 0 1. Row y = 2: 0 0 1 1. Station 0 serves 8 cells and station 1 serves 4, so the answer is 0.
Example 2
width = 5height = 3stations = [[4,1],[0,1]]return = 0The stations sit at the two ends of the middle row. Each cell in column x = 2 is equally far from both stations (2 steps in the middle row, 3 in the top and bottom rows), so they go to the smaller index, station 0. Station 0 serves columns 2, 3 and 4 (9 cells) and station 1 serves columns 0 and 1 (6 cells). The answer is 0.
Example 3
width = 5height = 2stations = [[0,0],[4,1]]return = 0Row y = 0: 0 0 0 1 1. Row y = 1: 0 0 1 1 1. No cell is a tie, and each station serves 5 cells. When stations tie for the most cells, return the smallest index, so the answer is 0.
Constraints
1 <= width, height <= 1001 <= stations.length <= 100stations[i].length == 20 <= stations[i][0] < widthand0 <= stations[i][1] < height- No two stations are on the same cell
More DocuSign Onsite Interview questions
- Count Binary SubstringsONSITE INTERVIEW · Seen Sep 2026
- Two Positions That Add Up to a TargetPHONE SCREEN · ONSITE INTERVIEW · Seen Sep 2026
- Compress Consecutive Integer RangesONSITE INTERVIEW · Seen Aug 2026
- JSON Schema Object ValidatorONSITE INTERVIEW · Seen Aug 2026
- Most Transactions Kept Without Going NegativeONSITE INTERVIEW · Seen May 2025
- Three-Part Splits With a Light MiddleONSITE INTERVIEW · Seen May 2025
- Combine Two Sorted Lists Into OneONSITE INTERVIEW · Seen Apr 2022
- Exact Palindrome CheckPHONE SCREEN · ONSITE INTERVIEW · Seen Apr 2022
- Paired Words That Share a SubstringONSITE INTERVIEW · Seen Apr 2022
- Reverse the Characters of a TextPHONE SCREEN · ONSITE INTERVIEW · Seen Apr 2022
Similar questions at other companies
- Rotting OrangesSalesforce · ONSITE INTERVIEWSalesforce interview questions
- Minimum Time to Spread Through a GridAmazon · PHONE SCREEN · ONSITE INTERVIEW
- Minimum Time to Rot All OrangesMicrosoft · ONSITE INTERVIEWMicrosoft interview questions
- Number of Islands with Diagonal ConnectivityGoogle · ONSITE INTERVIEWGoogle interview questions
- Island Count and Maximum AreaOracle · ONSITE INTERVIEWOracle interview questions
- Shortest Increasing Path to a TargetUber · ONSITE INTERVIEWUber interview questions
- Find and Reconstruct a Binary-Matrix PathMeta · PHONE SCREEN · ONSITE INTERVIEWMeta interview questions
- Rotting OrangesOtter.ai · ONSITE INTERVIEWOtter.ai interview questions
- Fuel-Aware Grid ReachabilityBloomberg LP · PHONE SCREEN · ONSITE INTERVIEWBloomberg LP interview questions
- Maximum Number of Fish in a GridGlobalization Partners · ONSITE INTERVIEW