Solve matrix rotation and 1-D illumination

Question

LeetCode 48. Rotate Image – rotate an n×n matrix 90° clockwise (extra space allowed). Find the point(s) with the maximum number of illuminated lamps in a 1-D grid (similar to LeetCode 1001 Grid Illumination).

https://leetcode.com/problems/rotate-image/description/ https://leetcode.com/problems/grid-illumination/description/

Matrix Rotation and 1-D Lamp Coverage

You are given an n×n integer matrix (n ≥ 1). Return the matrix rotated 90 degrees clockwise using extra space. On the same 1-D grid of length n (indices 0..n-1), you are also given a list lamps of lamp positions and a non-negative integer radius r. A lamp at position x illuminates all positions y such that |y − x| ≤ r (clipped to the grid bounds). Return all positions y that are covered by the maximum number of lamps, sorted in ascending order. Implement solve(matrix, lamps, radius) that returns [rotated_matrix, max_positions]. Duplicate lamp positions are allowed and count multiple times toward coverage.

Constraints

• 1 ≤ n ≤ 500, where n = len(matrix)
• matrix is square: len(matrix[i]) == n for all rows
• 0 ≤ len(lamps) ≤ 200000
• 0 ≤ lamps[i] < n for all i
• 0 ≤ radius ≤ 10^9
• Matrix values are integers in the range [-10^9, 10^9]

Examples

Example 1

Input: matrix = [[1,2,3],[4,5,6],[7,8,9]], lamps = [0,2], radius = 1
Output: rotated = [[7,4,1],[8,5,2],[9,6,3]], max_positions = [1]

Explanation: Rotation maps (r,c) -> (c,n-1-r). For illumination on n=3: lamp at 0 covers {0,1}, lamp at 2 covers {1,2}; counts = [1,2,1], so position 1 is maximal.

Example 2

Input: matrix = [[1,2],[3,4]], lamps = [0,0,1], radius = 0
Output: rotated = [[3,1],[4,2]], max_positions = [0]

Explanation: Radius 0 covers only the lamp's own position. Counts: pos0=2, pos1=1, so [0] is maximal.

Hints

1. For rotation, place matrix[r][c] at rotated[c][n-1-r].
2. To find coverage efficiently, use a difference array: for each lamp at x, increment diff[max(0,x-r)] and decrement diff[min(n-1,x+r)+1].
3. Compute prefix sums over the difference array to get coverage counts, then collect indices with the maximum count.

Approach

Rotation is achieved by mapping each cell (r, c) to (c, n-1-r) into a new matrix, which is O(n^2). For illumination, each lamp at x covers an interval [max(0, x-r), min(n-1, x+r)]. Using a difference array allows adding all intervals in O(len(lamps)), then a single prefix pass yields coverage per position in O(n). The maximal coverage value is tracked during the prefix pass, and all positions achieving it are collected.

• Time complexity: O(n^2 + m), where n is the matrix dimension and m = len(lamps)
• Space complexity: O(n^2) additional space for the rotated matrix plus O(n) for the difference array