Codewriting You've been hired to work on a planet exploration rover's data analysis…
- User
Codewriting
You've been hired to work on a planet exploration rover's data analysis system. One of your tasks is to process the rover's camera data, represented as a 2D square array of integers matrix, to help map the terrain for navigation.
Your task is to flatten the elements of the given matrix into a single list by traversing it in a spiral order, starting from the top-left corner and moving clockwise. Once the matrix is flattened, calculate the sum of the elements located at indices divisible by 3 (0-based) in this flattened list and return this sum.
Note: You are not expected to provide the most optimal solution, but a solution with time complexity not worse than O(matrix.length2) will fit within the execution time limit.
Example
- For
matrix = [ [1, 2, 3], [4, 5, 6], [7, 8, 9] ]the output should be
solution(matrix) = 14.Explanation:
▼ Expand to see the example video.
Note: If you are not able to see the video, use this link to access it.
The matrix is traversed in a spiral order:
[1, 2, 3, 6, 9, 8, 7, 4, 5]. The elements at indices divisible by 3 are[1, 6, 7]with sum14.- For
matrix = []the output should be
solution(matrix) = 0.Explanation:
The matrix is empty, so the flattened list is also empty. The sum of elements at indices divisible by 3 in an empty list is
0.Input/Output
- Assistant
To solve this problem, we need to perform a spiral traversal of a square matrix and sum specific elements based on their indices. Here's a step-by-step guide to the solution:
-
Check for Empty Matrix:
- If the input matrix is empty or the first row is empty, return
0immediately since there's nothing to process.
- If the input matrix is empty or the first row is empty, return
-
Initialize Boundaries:
- Set
top,bottom,left, andrightto define the current boundaries of the matrix that we need to traverse.
- Set
-
Spiral Traversal:
- Use a
whileloop to traverse the matrix in spiral order until thetopexceedsbottomorleftexceedsright. - Move Right: Traverse from the left boundary to the right boundary on the topmost row.
- Move Down: Traverse from the top boundary to the bottom boundary on the rightmost column.
- Move Left: Traverse from the right boundary to the left boundary on the bottommost row.
- Move Up: Traverse from the bottom boundary to the top boundary on the leftmost column.
- After each direction, update the corresponding boundary (
top,bottom,left,right) to move inward.
- Use a
-
Collect Elements:
- As we traverse the matrix, append each element to a list called
spiral_order.
- As we traverse the matrix, append each element to a list called
-
Calculate the Sum:
- Iterate over the
spiral_orderlist, selecting elements at indices divisible by3(0-based indexing). - Sum these selected elements to get the final result.
- Iterate over the
-
Return the Result:
- Return the calculated sum.
Here is the Python function implementing the solution:
def solution(matrix): # Check for empty matrix if not matrix or not matrix[0]: return 0 N = len(matrix) spiral_order = [] top, bottom = 0, N - 1 left, right = 0, N - 1 while top <= bottom and left <= right: # Move right for i in range(left, right + 1): spiral_order.append(matrix[top][i]) top += 1 # Move down for i in range(top, bottom + 1): spiral_order.append(matrix[i][right]) right -= 1 # Move left if top <= bottom: for i in range(right, left - 1, -1): spiral_order.append(matrix[bottom][i]) bottom -= 1 # Move up if left <= right: for i in range(bottom, top - 1, -1): spiral_order.append(matrix[i][left]) left += 1 # Sum elements at indices divisible by 3 sum_elements = sum(spiral_order[i] for i in range(0, len(spiral_order), 3)) return sum_elementsExample Usage:
matrix = [ [1, 2, 3], [4, 5, 6], [7, 8, 9] ] print(solution(matrix)) # Output: 14 empty_matrix = [] print(solution(empty_matrix)) # Output: 0 -