Matrix Traversal and Logic Flashcards
6 cards from real CodeSignal Technical Assessment practice questions. Tap to flip, then mark Knew It or Still Learning — missed cards come back until you master them.
Read the first 6 Matrix Traversal and Logic flashcards as text
A developer is implementing a spiral traversal algorithm for a 2D matrix, starting from the top-left corner and moving clockwise. Given the matrix `[[1, 2, 3], [8, 9, 4], [7, 6, 5]]`, what is the correct sequence of visited elements?
Answer: 1, 2, 3, 4, 5, 6, 7, 8, 9
The traversal starts at the top-left (1), moves right (2, 3), then down (4, 5), then left (6, 7), then up (8), and finally inwards to the center (9). This path traces the numbers in ascending order in this specific matrix, resulting in the sequence 1, 2, 3, 4, 5, 6, 7, 8, 9.
You are tasked with finding a target value in an `M x N` matrix where each row is sorted from left to right, and each column is sorted from top to bottom. Which of the following strategies offers the best worst-case time complexity?
Answer: Start from the top-right corner. If the target is smaller, move left; if larger, move down.
The strategy of starting at the top-right (or bottom-left) corner allows you to eliminate one row or one column at each step. This reduces the search space linearly, leading to a time complexity of O(M + N), which is more efficient than O(M log N) or O(M * N) in the worst case.
A programmer is writing a function to rotate an `N x N` matrix 90 degrees clockwise in-place. If the input matrix is `[[5, 1, 9], [2, 4, 8], [13, 3, 6]]`, what should the matrix look like after the rotation?
Answer: [[13, 2, 5], [3, 4, 1], [6, 8, 9]]
A 90-degree clockwise rotation can be achieved by first transposing the matrix (swapping matrix[i][j] with matrix[j][i]) and then reversing each row. Transposing the input gives `[[5, 2, 13], [1, 4, 3], [9, 8, 6]]`. Reversing each row of the transposed matrix results in `[[13, 2, 5], [3, 4, 1], [6, 8, 9]]`.
In a 2D grid representing a map of land ('L') and water ('W'), an island is a group of adjacent 'L's (horizontally or vertically). To count the number of distinct islands, a common algorithm iterates through each cell. What is the crucial next step when the iteration encounters an 'L' that has not been visited yet?
Answer: Increment the island count, then perform a traversal (like DFS or BFS) starting from that cell to find and mark all parts of the same island as visited.
When an unvisited land cell is found, it signifies the discovery of a new, distinct island. The island count must be incremented. Then, a graph traversal algorithm like Depth-First Search (DFS) or Breadth-First Search (BFS) must be launched from that cell to explore and mark all connected land cells belonging to that same island. This marking prevents recounting parts of the same island later in the iteration.
You are given an `M x N` matrix. If an element is 0, its entire row and column must be set to 0. Why is a naive approach of immediately setting rows and columns to zero upon finding a 0 logically flawed?
Answer: The zeros that are newly set as part of the process can cause additional, incorrect rows and columns to be zeroed out.
If you find a 0 at `matrix[i][j]` and immediately set row `i` and column `j` to zero, you introduce new zeros. When the algorithm's iteration later encounters one of these newly created zeros, it will incorrectly zero out that cell's entire row and column, which was not part of the original problem's requirement. The correct approach requires first marking which rows/columns need to be zeroed (e.g., using the first row/column or separate arrays) and then performing the zeroing in a second pass.
When implementing a zig-zag diagonal traversal of a matrix (e.g., `1, 2, 4, 7, 5, 3, ...`), what property of a cell's coordinates is typically used to determine the direction of traversal (up-right vs. down-left) for the diagonal it belongs to?
Answer: The parity (even or odd) of the sum of the row and column indices (`i + j`).
In a zig-zag diagonal traversal, all elements on the same diagonal share the same sum of their indices (`i + j`). The direction of traversal for a given diagonal is constant. This direction can be determined by the parity of this sum. For example, all diagonals where `i + j` is even might be traversed up-right, while those where `i + j` is odd are traversed down-left.