Matrix Traversal and Logic Flashcards
7 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 7 Matrix Traversal and Logic flashcards as text
In a matrix DP problem for counting paths from top-left to bottom-right (moving only right or down), the recurrence is dp[i][j] = dp[i-1][j] + dp[i][j-1]. What are the base cases?
Answer: dp[0][j] = 1 for all j and dp[i][0] = 1 for all i
The entire first row and first column have exactly one path each (only move right or only move down), so they are all initialized to 1.
You want to find the shortest path in a weighted grid where each cell has a cost to enter. Which algorithm handles this correctly?
Answer: Dijkstra's algorithm with a min-heap priority queue
Dijkstra's algorithm correctly handles non-negative weighted edges and finds the minimum-cost path in a weighted grid.
In the 'surrounded regions' problem, you flip all 'O' regions not connected to the border to 'X'. What is the most efficient first step?
Answer: Mark all 'O' cells reachable from any border cell using BFS/DFS
Starting BFS/DFS from border 'O' cells and marking them safe in one pass avoids redundant work and is O(M*N).
A matrix is called Toeplitz if every diagonal from top-left to bottom-right has the same value. What is the time complexity to verify a Toeplitz matrix of size M×N?
Answer: O(M*N)
You must check each cell (except the first row and column) against its top-left neighbor, visiting each cell once: O(M*N).
When transposing a non-square M×N matrix in-place is not possible (since the result is N×M), what is a common out-of-place solution's space complexity?
Answer: O(M*N)
An out-of-place transpose requires allocating a new N×M matrix to hold all M*N elements, so space is O(M*N).
In a matrix where you can move in 8 directions (including diagonals), how many neighbors does an interior cell have?
Answer: 8
An interior cell has 8 neighbors: up, down, left, right, and the four diagonal directions.
You want to find all cells in a matrix that can reach both the Pacific and Atlantic oceans (water flows to equal or lower neighbors, oceans border the matrix). What is the recommended approach?
Answer: Reverse BFS/DFS from each ocean's border separately, then intersect the reachable sets
Running BFS/DFS inward from each ocean's border (water flows uphill in reverse) and intersecting results is O(M*N) and avoids redundant searches.