Solve matrix rotation and 1-D illumination
Company: Capital One
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Take-home Project
##### 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/
Quick Answer: 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]
Solution
from typing import List
def solve(matrix: List[List[int]], lamps: List[int], radius: int):
n = len(matrix)
# 1) Rotate matrix 90 degrees clockwise using extra space
rotated = [[0] * n for _ in range(n)]
for r in range(n):
for c in range(n):
rotated[c][n - 1 - r] = matrix[r][c]
# 2) 1-D lamp coverage with uniform radius using difference array
# diff[i] = change in coverage at position i
diff = [0] * (n + 1)
for x in lamps:
left = 0 if x - radius < 0 else x - radius
right = n - 1 if x + radius >= n else x + radius
diff[left] += 1
diff[right + 1] -= 1
counts = [0] * n
curr = 0
max_count = -1
for i in range(n):
curr += diff[i]
counts[i] = curr
if curr > max_count:
max_count = curr
max_positions = [i for i, v in enumerate(counts) if v == max_count]
return [rotated, max_positions]
Explanation
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.
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.