2D Arrays and Matrix Problems

1. Introduction: From Lines to Grids

While 1D arrays are like a single street with houses in a row, a Matrix (or 2D array) is like an entire city grid. Data is structured in rows and columns.

In the real world, matrices are everywhere. A screen pixel layout is a matrix. A spreadsheet is a matrix. The board of Chess or Tic-Tac-Toe is a matrix. In computer science, 2D arrays are fundamentally used in image processing, dynamic programming tables, and representing graphs.

Navigating a 2D grid introduces new complexities. Instead of moving just left or right, you must manage boundaries in four directions (up, down, left, right). Mastering matrix problems is crucial for technical interviews because they rigorously test your ability to track boundary conditions and manage complex nested loops.

2. Core Concept: Memory Layout of 2D Arrays

How are matrices stored in memory? Computer memory is inherently 1-Dimensional. So how does it hold a 2D structure?

Array of Arrays (Java's approach)

In Java, a 2D array is an array of arrays. When you declare int[][] matrix = new int[3][4];, the JVM first allocates an array of 3 pointers (references). Then, for each of those 3 pointers, it allocates a separate 1D array of 4 integers. This means rows in Java are not necessarily contiguous in memory with respect to each other. matrix[0] might be stored far away from matrix[1]. (In C/C++, matrices are stored contiguously in Row-Major order).

Because of this "array of arrays" structure in Java, it is entirely possible to have a "Jagged Array" where rows have different lengths!

int[][] jagged = new int[3][];
jagged[0] = new int[2];
jagged[1] = new int[5];
jagged[2] = new int[1];

To traverse a standard $M \times N$ matrix, we use nested loops:

for (int row = 0; row < matrix.length; row++) {         // matrix.length gives M (rows)
    for (int col = 0; col < matrix[0].length; col++) {  // matrix[0].length gives N (cols)
        System.out.println(matrix[row][col]);
    }
}

3. Beginner Code Example: Search in a Sorted Matrix

Problem Statement: (LeetCode 74) Write an efficient algorithm that searches for a value target in an $M \times N$ integer matrix. This matrix has the following properties:

• Integers in each row are sorted from left to right.
• The first integer of each row is greater than the last integer of the previous row.

Brute Force (Suboptimal)

Loop through every single cell to find the target. $O(M \times N)$ time.

Optimal Approach (Treat it as a 1D Array)

Because the matrix is completely sorted top-to-bottom and left-to-right, we can conceptually flatten it into a 1D array of length $M \times N$ and perform standard Binary Search!

The Math Trick: How do we map a 1D index back to 2D coordinates [row][col]?

• row = 1D_index / N (where N is the number of columns)
• col = 1D_index % N

public class MatrixSearch {
    public static boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return false;
        
        int rows = matrix.length;
        int cols = matrix[0].length;
        
        // Define pointers for 1D binary search
        int left = 0;
        int right = rows * cols - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            
            // Map 1D index 'mid' to 2D coordinates
            int midValue = matrix[mid / cols][mid % cols];
            
            if (midValue == target) {
                return true;
            } else if (midValue < target) {
                left = mid + 1; // Search right half
            } else {
                right = mid - 1; // Search left half
            }
        }
        return false;
    }
}

Complexity Analysis:

• Time Complexity: $O(\log(M \times N))$ which is mathematically equivalent to $O(\log M + \log N)$.
• Space Complexity: $O(1)$. No extra space was used.

4. Intermediate Code Example: Spiral Traversal

Problem Statement: (LeetCode 54) Given an $M \times N$ matrix, return all elements of the matrix in spiral order.

This is a classic boundary management problem. We maintain four boundaries: top, bottom, left, and right. We traverse the perimeter, peeling off the outer layer like an onion, and then shrink the boundaries inward.

import java.util.ArrayList;
import java.util.List;

public class SpiralMatrix {
    public static List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> result = new ArrayList<>();
        if (matrix.length == 0) return result;
        
        int top = 0;
        int bottom = matrix.length - 1;
        int left = 0;
        int right = matrix[0].length - 1;
        
        while (top <= bottom && left <= right) {
            // 1. Traverse Top Row (Left to Right)
            for (int col = left; col <= right; col++) {
                result.add(matrix[top][col]);
            }
            top++; // Shrink top boundary
            
            // 2. Traverse Right Column (Top to Bottom)
            for (int row = top; row <= bottom; row++) {
                result.add(matrix[row][right]);
            }
            right--; // Shrink right boundary
            
            // Critical check: Ensure we haven't crossed boundaries before doing the reverse steps
            if (top <= bottom) {
                // 3. Traverse Bottom Row (Right to Left)
                for (int col = right; col >= left; col--) {
                    result.add(matrix[bottom][col]);
                }
                bottom--; // Shrink bottom boundary
            }
            
            if (left <= right) {
                // 4. Traverse Left Column (Bottom to Top)
                for (int row = bottom; row >= top; row--) {
                    result.add(matrix[row][left]);
                }
                left++; // Shrink left boundary
            }
        }
        
        return result;
    }
}

Complexity Analysis:

• Time Complexity: $O(M \times N)$. Every element is visited exactly once.
• Space Complexity: $O(M \times N)$ to store the output list, but $O(1)$ auxiliary memory.

5. Advanced Code Example: Rotate Image (Matrix) 90° In-Place

Problem Statement: (LeetCode 48) You are given an $N \times N$ 2D matrix representing an image. Rotate the image by 90 degrees (clockwise). You MUST rotate the image in-place, which means you have to modify the input 2D matrix directly. Do not allocate another 2D matrix.

The Math Insight: Rotating a square matrix 90 degrees clockwise can be achieved cleanly in two simple geometric steps:

1. Transpose the matrix: Swap matrix[i][j] with matrix[j][i]. This turns rows into columns.
2. Reverse each row: Swap the left and right elements of every row.

public class MatrixRotation {
    public static void rotate(int[][] matrix) {
        int n = matrix.length;
        
        // Step 1: Transpose the matrix
        // Note: j starts at i to only swap across the diagonal once.
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }
        
        // Step 2: Reverse each row
        for (int i = 0; i < n; i++) {
            int left = 0;
            int right = n - 1;
            while (left < right) {
                int temp = matrix[i][left];
                matrix[i][left] = matrix[i][right];
                matrix[i][right] = temp;
                left++;
                right--;
            }
        }
    }
}

Complexity Analysis:

• Time Complexity: $O(N^2)$. Transposing takes roughly $N^2/2$ operations. Reversing takes $N^2/2$ operations. Dropping constants, we get $O(N^2)$, which is optimal because we must touch all $N \times N$ elements.
• Space Complexity: $O(1)$ auxiliary space. All swaps happen in-place.

6. Common Mistakes Beginners Make

1. ArrayIndexOutOfBoundsException on Non-Square Matrices

   • The Mistake: Assuming rows == cols.
   • Why it's wrong: For an $M \times N$ matrix, iterating a column using matrix.length instead of matrix[0].length will crash if $M \neq N$.
   • The Fix: Always use int rows = matrix.length and int cols = matrix[0].length.

2. Forgetting Boundary Checks in Spiral/Layered Traversals

   • The Mistake: In the spiral traversal, omitting the if (top <= bottom) check before printing the bottom row.
   • Why it's wrong: If the matrix is a single row (e.g., [[1, 2, 3]]), the top and right loops print everything. Without the if check, the bottom loop will traverse the same row backwards, printing duplicates!

3. Swapping Elements Twice in Transposition

   • The Mistake: for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { swap(m[i][j], m[j][i]) } }
   • Why it's wrong: If j starts at 0, you swap elements, and then when the loops continue, you swap them back to their original positions!
   • The Fix: The inner loop must start at j = i.

7. Interview Q&A

Q1: How do you handle checking neighbours in a 2D grid without writing a bunch of messy if statements? Answer: Use a direction array. Define int[][] dirs = {{0,1}, {1,0}, {0,-1}, {-1,0}}; (Right, Down, Left, Up). You can loop through these directions to calculate newRow = row + dir[0] and newCol = col + dir[1], followed by a single boundary check function isValid(newRow, newCol).

Q2: What is a "Sparse Matrix" and how do you store it efficiently? Answer: A sparse matrix is a matrix where the vast majority of elements are 0. Storing it as a standard 2D array wastes memory. Instead, it is better stored using a HashMap (Mapping a coordinate string like "row,col" to the value) or using specialized data structures like Compressed Sparse Row (CSR) format.

Q3: (LeetCode 73) Set Matrix Zeroes: How can you do this in $O(1)$ space? Answer: Instead of allocating $O(M+N)$ space for arrays to remember which rows and columns need to be zeroed, we can use the first row and first column of the matrix itself as our memory arrays! We use two boolean variables to track if the first row/col originally had a zero, then use the first row/col to mark zeros for the rest of the matrix.

Q4: Can we use Binary Search on a matrix where rows and columns are sorted, but it's not strictly sorted globally? (LeetCode 240) Answer: Yes, but not the 1D mapping approach. We start at the top-right corner. If the target is smaller than the current element, we can safely eliminate the entire column and move left. If it is larger, we eliminate the row and move down. This solves it in $O(M + N)$ time.

8. Practice Problems

1. Search a 2D Matrix II (LeetCode 240)
   • Goal: Search a matrix where rows and cols are sorted independently.
   • Hint: Start from the top-right corner.
2. Set Matrix Zeroes (LeetCode 73)
   • Goal: Set rows and cols to 0 in $O(1)$ space.
3. Valid Sudoku (LeetCode 36)
   • Goal: Validate a 9x9 Sudoku board.
   • Hint: Track seen numbers in rows, columns, and 3x3 sub-boxes using arrays or HashSets.

9. Summary

• Mental Model: A matrix in Java is an array of arrays. matrix.length is the number of rows, matrix[0].length is the number of columns.
• Boundaries: Matrix problems are heavily focused on boundary management. Always ensure your pointers don't slip out of bounds.
• Math Maps: A 1D sorted array can be cleanly mapped to and from a 2D matrix using / cols and % cols.
• In-Place Operations: Rotating or transposing matrices can be done with optimal geometric swaps, entirely in-place.
• Direction Arrays: Master the dirs array technique for clean, professional code when moving locally around a grid.