Rotate Every Ring
MediumMatrix
Problem
A rotating sign is built as an m × n grid of tiles, where m and n are both even, so the grid splits into concentric rectangular rings (the outer border, the border inside it, and so on). One step moves every tile one position counter-clockwise along its own ring: tiles on a ring's top edge move left, on its left edge move down, on its bottom edge move right and on its right edge move up.
Return the grid after steps steps. steps can be very large.
Example 1
- Input:
- grid = [[40, 10], [30, 20]], steps = 1
- Output:
- [[10, 20], [40, 30]]
10 moves left into the corner, 40 moves down, 30 moves right and 20 moves up.
Example 2
- Input:
- grid = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 16]], steps = 2
- Output:
- [[3, 4, 8, 12], [2, 11, 10, 16], [1, 7, 6, 15], [5, 9, 13, 14]]
The outer ring shifts two places; the inner 2 × 2 ring shifts two places too, which is half a turn for it.
Constraints
- 2 ≤ m, n ≤ 50
- m and n are even
- 1 ≤ steps ≤ 10^9
- 1 ≤ grid[i][j] ≤ 5000
Hint
Show the first hint
Each ring moves independently. Flatten one ring into a list: what does a step do to that list?
Walkthrough
How to approach it
01Clarify before coding
- Which direction? Counter-clockwise: the top edge moves left.
- Do rings rotate independently? Yes, each by the same number of steps along its own path.
- Can steps be huge? Up to 10^9, so simulating step by step is out.
02Brute force
Simulate one step at a time, moving every tile to its neighbour on the ring.
Cost: O(steps · m · n): 10^9 steps is impossible. Even capping steps at each ring's length leaves O(L²) work for a ring of length L.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.