Solve matrix rotation and 1-D illumination
Company: Capital One
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Online Assessment
##### 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/
Overview: This question evaluates array and matrix manipulation, spatial indexing, and efficient counting techniques by combining an n×n matrix rotation task with locating maximally illuminated positions in a one-dimensional grid, and it falls under the Coding & Algorithms domain.
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]
Hints
- For rotation, place matrix[r][c] at rotated[c][n-1-r].
- 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].
- Compute prefix sums over the difference array to get coverage counts, then collect indices with the maximum count.