Ctrl K

How a Rumor Spreads

Easy
An open-plan office has its desks in a rectangle of rows rows with cols desks each. The desk in row i and column j is written [i, j] (0-based). A piece of news appears at desk [start_row, start_col]. It then spreads in waves. Every minute, each desk that learned the news during the previous minute tells its neighbours in this exact order: in front ([i - 1, j]), right ([i, j + 1]), behind ([i + 1, j]), left ([i, j - 1]). Desks of the same wave take turns in the order they themselves learned the news. A neighbour that already knows (or has already been told) is skipped, and there are no desks outside the office. Return the coordinates of every desk in the order the desks learned the news, starting with [start_row, start_col].
Example 1
rows=2, cols=3, start_row=0, start_col=1 → [[0, 1], [0, 2], [1, 1], [0, 0], [1, 2], [1, 0]]

Desk (0, 1) knows first. It tells, in order: nobody in front, (0, 2) on the right, (1, 1) behind, (0, 0) on the left. Then (0, 2) tells (1, 2), (1, 1) tells (1, 0), and (0, 0) has nobody left to tell.

Example 2
rows=1, cols=4, start_row=0, start_col=3 → [[0, 3], [0, 2], [0, 1], [0, 0]]

A single row: the news can only travel left.

Example 3
rows=3, cols=3, start_row=1, start_col=1 → [[1, 1], [0, 1], [1, 2], [2, 1], [1, 0], [0, 2], [0, 0], [2, 2], [2, 0]]
Constraints
  • 1 ≤ rows, cols ≤ 100
  • 0 ≤ start_row < rows
  • 0 ≤ start_col < cols
Have you seen this problem in a real interview?
Solved by0
Tried by0
Submissions0
Acceptance—
Topics
Similar problemsShadows of Block Towers EasySurface of Cube Towers EasyWhere the Friends Should Meet HardSmallest Paddock MediumNearest Points to the Base Medium
loading Python…
Input
rows=2, cols=3, start_row=0, start_col=1
Expected
[[0, 1], [0, 2], [1, 1], [0, 0], [1, 2], [1, 0]]

Run checks the first 3 tests in your browser. Submit checks all 76 tests on the server, hidden ones included.