DEV Community

Dev Cookies
Dev Cookies

Posted on

🚀 Day 16: Matrix Traversal Pattern (Amazon Interview Series)

Amazon interviewers love matrix/grid problems because they test:

  • Traversal strategies (row-wise, column-wise, diagonals, spiral).
  • Boundary handling.
  • In-place transformations.
  • BFS/DFS usage for pathfinding.

These problems simulate warehouse navigation, routing, and optimization problems that Amazon faces in real-world systems.

📝 Problem 1: Rotate Image (90° in-place)

👉 Amazon-style phrasing:
Given an n x n matrix, rotate it by 90 degrees clockwise in-place.

Java Solution 

public class RotateImage {
    public static void rotate(int[][] matrix) {
        int n = matrix.length;
        // Step 1: Transpose
        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++) {
            for (int j = 0; j < n / 2; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[i][n - 1 - j];
                matrix[i][n - 1 - j] = temp;
            }
        }
    }
}
Enter fullscreen mode Exit fullscreen mode

✅ Time Complexity: O(n²)
✅ Amazon relevance: Warehouse rotation & inventory mapping.

📝 Problem 2: Spiral Matrix

👉 Amazon-style phrasing:
Return all elements of the matrix in spiral order.

Java Solution 

import java.util.*;

public class SpiralMatrix {
    public static List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> res = new ArrayList<>();
        if (matrix.length == 0) return res;

        int top = 0, bottom = matrix.length - 1;
        int left = 0, right = matrix[0].length - 1;

        while (top <= bottom && left <= right) {
            for (int j = left; j <= right; j++) res.add(matrix[top][j]);
            top++;
            for (int i = top; i <= bottom; i++) res.add(matrix[i][right]);
            right--;
            if (top <= bottom) {
                for (int j = right; j >= left; j--) res.add(matrix[bottom][j]);
                bottom--;
            }
            if (left <= right) {
                for (int i = bottom; i >= top; i--) res.add(matrix[i][left]);
                left++;
            }
        }
        return res;
    }
}
Enter fullscreen mode Exit fullscreen mode

✅ Time Complexity: O(m*n)
✅ Amazon relevance: Picking items in optimized traversal path.

📝 Problem 3: Set Matrix Zeroes

👉 Amazon-style phrasing:
If an element in a matrix is 0, set its entire row and column to 0.

Java Solution 

public class SetMatrixZeroes {
    public static void setZeroes(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        boolean[] rows = new boolean[m];
        boolean[] cols = new boolean[n];

        // Mark rows and cols
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) {
                    rows[i] = true;
                    cols[j] = true;
                }
            }
        }

        // Update matrix
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (rows[i] || cols[j]) {
                    matrix[i][j] = 0;
                }
            }
        }
    }
}
Enter fullscreen mode Exit fullscreen mode

✅ Time Complexity: O(m*n)
✅ Space: O(m+n)
✅ Why Amazon likes it: Inventory system fault marking.

📝 Problem 4: Search in a 2D Matrix II

👉 Amazon-style phrasing:
Given a matrix where each row and column is sorted in ascending order, search for a target.

Java Solution 

public class Search2DMatrix {
    public static boolean searchMatrix(int[][] matrix, int target) {
        int row = 0, col = matrix[0].length - 1;
        while (row < matrix.length && col >= 0) {
            if (matrix[row][col] == target) return true;
            else if (matrix[row][col] > target) col--;
            else row++;
        }
        return false;
    }
}
Enter fullscreen mode Exit fullscreen mode

✅ Time Complexity: O(m+n)
✅ Amazon relevance: Finding items in sorted warehouse layout.

📝 Problem 5: Minimum Path Sum

👉 Amazon-style phrasing:
Given a grid filled with non-negative numbers, find a path from top-left to bottom-right minimizing the sum.

Java Solution 

public class MinPathSum {
    public static int minPathSum(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        for (int i = 1; i < m; i++) grid[i][0] += grid[i-1][0];
        for (int j = 1; j < n; j++) grid[0][j] += grid[0][j-1];

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                grid[i][j] += Math.min(grid[i-1][j], grid[i][j-1]);
            }
        }
        return grid[m-1][n-1];
    }
}
Enter fullscreen mode Exit fullscreen mode

✅ Time Complexity: O(m*n)
✅ Amazon relevance: Finding shortest delivery route inside a warehouse.

🎯 Key Takeaways

  • Matrix rotation & traversal test array manipulation skills.
  • Boundary problems like Spiral and Set Zeroes train careful thinking.
  • Search in sorted matrix uses two-pointer optimization.
  • Dynamic Programming on grids (Min Path Sum) is heavily asked at Amazon.

📅 Next in the series (Day 17):
👉 Trie & String Matching Pattern – solving problems like Word Search II, Prefix Dictionary, Longest Word in Dictionary, Replace Words.

Top comments (0)