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
You are given a matrix of 0s and 1s. You want to find the largest rectangle containing only 1s. Which approach leverages the 'largest rectangle in histogram' problem?
Answer: Process each row as a histogram of heights, apply stack-based largest rectangle algorithm
Building a running height histogram per row and applying the O(N) stack algorithm gives O(M*N) total time.
What does it mean for a matrix traversal algorithm to be 'in-place'?
Answer: It modifies the matrix directly without allocating extra storage proportional to input size
An in-place algorithm uses O(1) extra space (excluding output) by modifying the original data structure.
In the 'word search' problem, you search for a word in a matrix by moving to adjacent cells (up, down, left, right). Why must you mark cells as visited during DFS and unmark them on backtrack?
Answer: To allow the same cell to be reused in other candidate paths while preventing reuse within the current path
Temporary marking prevents using the same cell twice within one path but allows it for entirely different paths explored via backtracking.
A 'diagonal' of an M×N matrix where row - col = k contains elements sharing the same value of (row - col). How many distinct diagonals (top-left to bottom-right) exist in a 4×5 matrix?
Answer: 8
The value (row - col) ranges from -(N-1) = -4 to (M-1) = 3, giving M+N-1 = 4+5-1 = 8 diagonals.
When using Union-Find (Disjoint Set Union) to count connected components in a matrix, what operation determines if two cells are in the same component?
Answer: Find with path compression on both cells and compare roots
The Find operation (with path compression) returns the root representative of each cell's set; equal roots mean same component.
Given a matrix where you can move up, down, left, or right, and you want the minimum number of steps from source to destination, which is guaranteed to give the correct answer?
Answer: BFS from the source cell
BFS on an unweighted grid explores cells in order of their distance, guaranteeing the first time the destination is reached is via the shortest path.
You need to set all cells in the same row and column as any zero to zero in-place in O(1) extra space. Which technique avoids using O(M+N) extra arrays?
Answer: Use the first row and first column of the matrix itself as markers
By using the first row and first column as flag arrays (with separate variables for their own zero status), the algorithm runs in O(1) extra space.