2D Array: Matrix Traversal, Search & Interview Problems
A 2d array is a collection of values arranged in rows and columns, commonly used to represent a 2d matrix, grid, table, image, or board. It matters because real systems model seats, pixels, maps, transactions, and schedules as grids. After reading, you will be able to traverse, transform, and search matrix data confidently.
Matrix problems sit between basic arrays and graph or dynamic programming problems. A python 2d array may look simple as a list of lists, but interviewers test whether you handle boundaries, indexing, sorted properties, and memory trade-offs without off-by-one errors.
You will learn the standard traversal patterns, ways to search a 2d matrix, high-frequency matrix questions, and reusable Python templates for coding interviews, GATE-style questions, and production-style grid logic.
Core Concepts
2D array problems become easier when you separate representation, indexing, traversal order, search property, transformation, and optimisation. The same 2d matrix may be processed row by row, column by column, diagonally, in a spiral, as a graph, as a prefix-sum table, or as a dynamic programming state grid.
1.Representation And Indexing
A rectangular 2d array has m rows and n columns. In Python, the common representation is a list of lists, where matrix[r][c] accesses row r and column c. The row index always comes first. For a matrix with 4 rows and 5 columns, valid row indices are 0..3 and valid column indices are 0..4.
A familiar example is a cinema booking screen where each row represents a seat row and each column represents a seat number. An industry-specific example is a hospital ward dashboard where rows represent beds and columns represent hourly vitals such as pulse, oxygen, and temperature categories. In both cases, mixing row and column order gives wrong data even when the code runs.
Jagged arrays also appear in practice. For example, monthly household expense categories may vary by month, and a SaaS usage export may contain a different number of events per customer. A true 2d matrix assumes equal row length; jagged data needs row-specific length checks.
Code Example
2.Basic Traversal Patterns
Traversal means visiting matrix cells in a controlled order. Row-wise traversal is the default when data is stored or displayed row by row. Column-wise traversal is useful when the meaning is attached to columns, such as comparing test scores across attempts or calculating daily totals from a weekly sales table.
A familiar example is reading a phone gallery grid row by row from top-left to bottom-right. An industry-specific example is a banking reconciliation sheet where columns represent payment channels such as UPI, cards, net banking, and wallet, and analysts need column totals for each channel.
Reverse traversal appears in bottom-up dynamic programming and when processing latest data first. Zigzag traversal alternates direction, which is common in snake-like board games, LED matrix displays, and some compression-inspired scan orders.
Code Example
3.Boundary And Spiral
Boundary traversal visits only the outer ring of a 2d matrix. Spiral traversal extends that idea by repeatedly peeling the outer layer and moving inward. The mental model is a shrinking rectangle with four boundaries: top, bottom, left, and right.
A familiar example is walking around the border of a rangoli pattern before moving into the next inner border. An industry-specific example is a warehouse robot scanning shelf labels around the perimeter of each storage block before entering the next aisle layer.
Spiral traversal is a favourite interview problem because it looks visual but depends on precise boundary updates. Single-row and single-column matrices must be handled carefully to avoid duplicate elements.
Code Example
4.Diagonal Traversal
Diagonal traversal groups cells by diagonal identity. In a main diagonal direction, cells often share r - c. In an anti-diagonal direction, cells share r + c. These properties convert a visual matrix problem into a grouping problem.
A familiar example is a bishop moving diagonally on a chessboard. An industry-specific example is image processing, where diagonal filters may detect slanted edges in a scanned document or manufacturing inspection photo.
Interviewers use diagonal traversal to test whether you can derive cell relationships rather than memorise loops. Variants include main diagonal, anti-diagonal, all diagonals from top-left to bottom-right, all anti-diagonals, and zigzag diagonal traversal.
Code Example
6.Search Patterns
To search a 2d matrix efficiently, first identify what is sorted. If nothing is sorted, linear search is the only universally correct approach. If every row is sorted and each row starts after the previous row ends, the matrix behaves like one sorted 1D array. If rows and columns are both sorted, staircase search is usually best.
A familiar example is searching a train number in a printed IRCTC-style timetable grid when entries are already ordered by route and time. An industry-specific example is an e-commerce pricing matrix where rows represent product categories and columns represent sorted price slabs.
Per-row binary search fits a weaker condition: each row is sorted, but rows do not form a single global order. This difference is heavily tested because using flattened binary search on the wrong sorted property gives incorrect answers.
Code Example
7.Matrix Transformations
Matrix transformations change the shape or position of elements. Transpose swaps rows and columns. Rotation by 90 degrees can be done by transposing and then reversing rows. Reflection flips rows or columns. Set-zeroes modifies all cells in a row and column when a zero appears.
A familiar example is rotating a phone photo from portrait to landscape. An industry-specific example is a logistics control panel where shelf coordinates must be rotated to match a new warehouse map after layout redesign.
These matrix questions test whether you can reason about coordinates. For an n x n matrix, in-place rotation is possible. For a non-square m x n matrix, rotation changes dimensions to n x m, so an auxiliary matrix is usually simpler and safer.
Code Example
8.Prefix Sum Matrix
A prefix sum matrix precomputes cumulative totals so that any rectangular region sum can be answered in constant time. Instead of adding all cells in the region again and again, you pay O(mn) once during preprocessing and answer each query in O(1).
A familiar example is checking electricity usage totals across selected days and time slots in a smart-meter dashboard. An industry-specific example is a fintech fraud-monitoring heatmap where rows represent merchant categories and columns represent hourly transaction buckets.
The safest implementation uses an extra top row and left column filled with zeroes. This avoids special cases when the query rectangle touches the first row or first column.
Code Example
9.Grid As Graph
Many advanced matrix questions treat each cell as a graph node. A cell may connect to four neighbours: up, down, left, and right. Some problems allow eight directions by including diagonals. Once you see a grid as a graph, island counting, flood fill, shortest path, and rotting-oranges-style problems become BFS or DFS problems.
A familiar example is a monsoon flood map where connected flooded cells form one affected region. An industry-specific example is a medical imaging system that groups connected abnormal pixels in an X-ray or MRI slice for review.
The key is a visited structure. Without it, DFS or BFS may revisit cells endlessly. Boundary checks must also come before accessing the matrix cell.
Code Example
10.Dynamic Programming Grids
Dynamic programming on a 2d matrix stores answers to smaller grid states. A cell often represents the best answer up to that position, such as minimum cost to reach it, number of ways to reach it, or maximum square ending there. The answer is built from neighbouring states.
A familiar example is finding the cheapest path through a city grid where each crossing has a toll. An industry-specific example is an ed-tech learning path where rows represent modules, columns represent difficulty levels, and the platform computes the minimum effort route through prerequisites.
Good DP solutions define four things clearly: state, transition, base case, and iteration order. In grid DP, iteration order matters because each cell must depend only on already-computed cells.
Code Example
11.Sparse Matrix Storage
A sparse matrix contains mostly zero or empty values. Storing every cell wastes memory when only a small fraction of cells matter. Instead, store only non-zero cells using coordinate triples such as (row, column, value) or a dictionary keyed by (row, column).
A familiar example is a metro station versus time-slot table where most station-time combinations have no service disruption. An industry-specific example is an ad-tech impression matrix where millions of user-campaign pairs exist but only a tiny subset has actual clicks or conversions.
Sparse storage is not always faster. It helps when non-zero entries are few and operations target those entries. For dense matrices, normal 2D lists are simpler and often faster due to direct indexing.
Code Example
Learning Path
Build matrix skill in layers. Start with indexing and traversal, then add sorted search, transformations, prefix sums, graph thinking, and dynamic programming. Use small hand-drawn matrices before writing code; visual tracing catches mistakes faster than debugging large inputs.
Frequently Asked Questions
What is a 2d array in matrix problems?
A 2d array is a row-column data structure where each element is accessed using two indices: row and column. In matrix questions, it represents grids such as images, boards, maps, tables, and numeric matrices. Most interview problems test traversal, search, transformation, or grid-based reasoning.
What is the difference between a 2d array and a 2d matrix?
A 2d array is the programming representation, while a 2d matrix is the mathematical or conceptual grid. In code, a matrix is often implemented using a 2D array. The distinction matters when discussing operations such as transpose, rotation, multiplication, and search properties.
How do you create a python 2d array correctly?
Use a list comprehension such as [[0 for _ in range(cols)] for _ in range(rows)]. Avoid [[0] * cols] * rows because it creates repeated references to the same inner list. That reference-sharing bug causes one row update to accidentally affect multiple rows.
How do you search a 2d matrix efficiently?
Choose the search method based on sortedness. Use linear search for unsorted matrices, flattened binary search for globally sorted matrices, staircase search for row-column sorted matrices, and per-row binary search when only individual rows are sorted.
When should I use spiral traversal?
Use spiral traversal when the problem asks for layer-by-layer access from the outside toward the centre. It is common in print-matrix, UI ordering, and interview traversal problems. The main challenge is updating boundaries without duplicating cells.
What are the most common matrix questions in interviews?
Common matrix questions include spiral order, rotate image, set matrix zeroes, search a 2d matrix, transpose matrix, count islands, flood fill, number of paths, minimum path sum, and 2D prefix sum range queries. These problems cover traversal, transformation, graph search, and dynamic programming.
What is the common mistake in 2d array problems?
The most common mistake is mixing up row and column bounds. Another frequent mistake is using a search algorithm that assumes a stronger sorted property than the matrix actually has. Always inspect dimensions, edge cases, and matrix ordering before coding.
Is matrix traversal always O(mn)?
If every cell must be visited, traversal is O(mn). Some searches can be faster when the matrix is sorted, such as O(log mn) flattened binary search or O(m+n) staircase search. Prefix sums also make repeated region queries O(1) after O(mn) preprocessing.
Key Takeaways
A 2d array becomes manageable when you define rows, columns, bounds, and the access pattern before coding. The core traversal variants are row-wise, column-wise, reverse, boundary, spiral, diagonal, anti-diagonal, and zigzag. Search strategy depends entirely on sortedness: unsorted, globally sorted, row-column sorted, or row-wise sorted.
For GATE and interviews, the most tested points are time complexity, boundary conditions, row-column index discipline, binary-search eligibility, staircase-search movement, and grid BFS or DFS with a visited structure. Prefix sums and dynamic programming grids are common advanced follow-ups.
The natural next step is to practise mixed matrix questions in sets: five traversal problems, five search problems, five transformation problems, and five grid graph or DP problems. Trace each solution on a 1xN, Nx1, square, rectangular, and empty-matrix edge case.