Solving a Leetcode problem daily — Day 3: Spiral Matrix

Solving a Leetcode problem daily — Day 3: Spiral Matrix | by Subhradeep Saha | Apr, 2024 | Medium

Subhradeep Saha ・ Apr 28, 2024 ・

Medium

Here is the Leetcode problem - Spiral Matrix

Problem Statement

Given a two-dimensional matrix (matrix), where each element represents a number, the task is to write a function that returns a new list containing all the elements of the matrix traversed in a spiral order.

Example 1:

Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,2,3,6,9,8,7,4,5]

Example 2

Input: matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
Output: [1,2,3,4,8,12,11,10,9,5,6,7]

Constraints:

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 10
• -100 <= matrix[i][j] <= 100

What We Want to Achieve

This problem aims to develop a function that iterates through a matrix in a specific pattern, ensuring:

• Every element is visited once: No number in the matrix is left untouched.
• Spiral Path: The traversal follows a clockwise spiral path, starting from the top-left corner and gradually moving inwards.
• Resultant List: The function returns a new list containing all the elements of the matrix in the order they were visited during the spiral traversal.

The Code

Here’s the complete C++ code that tackles this challenge:

class Solution {
public:
    void traverse(vector<int>& res, vector<vector<int>>& matrix, int i, int j, int r, int c) {
        int idx;
        for(idx = j; idx <= c; idx++) {
            if(abs(matrix[i][idx]) <= 100) {
                res.push_back(matrix[i][idx]);   
            }
            matrix[i][idx] = 101;
        }

        for(idx = i+1; idx <= r; idx++) {
            if(abs(matrix[idx][c]) <= 100) {
                res.push_back(matrix[idx][c]);   
            }
            matrix[idx][c] = 101;
        }

        for(idx=c-1; idx >= j; idx--) {
            if(abs(matrix[r][idx]) <= 100) {
                res.push_back(matrix[r][idx]);   
            }
            matrix[r][idx] = 101;
        }

        for(idx=r-1; idx > i; idx--) {
            if(abs(matrix[idx][j]) <= 100) {
                res.push_back(matrix[idx][j]);   
            }
            matrix[idx][j] = 101;
        }
    }

    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        int r = m-1, c = n-1, i = 0, j = 0;

        vector<int> res;

        while(i <= r && j <= c) {
            traverse(res, matrix, i, j, r, c);
            i++; j++; r--; c--;
        }

        return res;
    }
};

Decoding the Code: Step-by-Step Breakdown

The code is divided into two main functions:

a) spiralOrder (Public Function):

Initialization:

• It retrieves the matrix dimensions (m for rows, n for columns).
• It initializes variables representing the boundaries (i, j, r, c) for the entire matrix (top-left and bottom-right corners).
• It creates a result vector (res) to store the elements in spiral order

Looping Through Layers:

1. It employs a while loop that continues as long as both i (top row) is less than or equal to r (bottom row) and j (leftmost column) is less than or equal to c (rightmost column). This ensures the loop iterates until all elements within the matrix boundaries are processed.
2. Traverse a Layer: Inside the loop, it calls the helper function traverse with the current boundaries (i, j, r, c) and the result vector (res). This call essentially processes a single layer of the spiral within the specified boundaries.
3. Update Boundaries: After traversing a layer, the loop updates the boundaries (i, j, r, c) by incrementing i and j (moving inwards) and decrementing r and c (shrinking the remaining area). This effectively prepares the boundaries for the next layer of the spiral.

b) traverse (Helper Function):

• Logic for Traversing a Single Layer: It takes the matrix (matrix), boundaries (i, j, r, c) representing the current layer's top-left and bottom-right corners, and the result vector (res) to store the elements in spiral order.(matrix[i][j] will be the starting element for 1 traverse)
• Looping Through Elements: It uses four for loops, each iterating through an index (idx) to visit the elements in the current layer:

1. Move Right (First Row): The first loop iterates from j (leftmost column) to c (rightmost column) in the current row (i). It checks if the element matrix[i][idx] is unvisited (absolute value less than or equal to 100) using abs(matrix[i][idx]) <= 100. If unvisited, it adds the element to the res vector and marks it as visited by assigning a high value (101) to matrix[i][idx].
2. Move Down (Last Column): Similar to the first loop, this iteration goes from i+1 (the row below the first row) to r (bottommost row) in the current rightmost column (c). It follows the same logic of checking for unvisited elements and adding them to the result with a visit mark.
3. Move Left (Last Row): This loop iterates from c-1 (one column before the last) to j (leftmost column) in the bottom row (r). It checks and adds unvisited elements.
4. Move Up (First Column): The final loop iterates from r-1 (one row above the bottom row) to i-1 (1 row below the topmost row) in the current leftmost column (j). It uses the same logic for checking, adding, and marking visited elements.

Key Points:

• The traverse function ensures that elements are visited only once by checking if their absolute value is less than or equal to 100 (since in the constraints it is mentioned that items of the matrix are in the range [-100, 100]). Marking visited elements with a high value (101) prevents revisiting them.
• The spiralOrder function progressively shrinks the boundaries (i, j, r, c) as it processes each layer, effectively spiralling inwards until all elements are captured.

Testing the Code

Let’s delve into some test cases to solidify our understanding of how the provided C++ code accomplishes the spiral order traversal:

Test Case 1: Basic Spiral

Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]

Expected output: [1, 2, 3, 6, 9, 8, 7, 4, 5]

Walkthrough:

1. Initialization:

• The code retrieves the matrix dimensions (3 rows, 3 columns).
• It sets boundaries (i = 0, j = 0, r = 2, c = 2).
• An empty result vector (res) is created.

1. Looping Through Layers:

The while loop starts (i <= r and j <= c are true).
a) First Layer Traversal:

1. The traverse function is called with boundaries (i = 0, j = 0, r = 2, c = 2).
2. It iterates through the first row (elements 1, 2, 3) from left to right, adding them to res and marking them visited.
3. It moves down the rightmost column (element 6), adding it to res and marking it visited.
4. It iterates through the last row (elements 9, 8) from right to left, adding them to res and marking them visited.
5. It moves up the leftmost column (element 7), adding it to res and marking it visited.
6. After traversing the first layer, res becomes [1, 2, 3, 6, 9, 8].
7. Boundaries are updated (i = 1, j = 1, r = 1, c = 1).

b) Second Layer Traversal:

1. The loop iterates again (i <= r and j <= c are still true).
2. The traverse function is called with the updated boundaries.
3. It tries to iterate through the top row (element 4) but finds it already visited.
4. It moves down the rightmost column (no element present).
5. It tries to iterate through the bottom row (element 5) but finds it already visited.
6. It moves up the leftmost column (no element present).
7. Since no new elements were found, this layer traversal effectively ends.

c) Loop Termination:

After the second layer, i (now 1) is greater than r (now 1), and the while loop terminates.

1. Return Result:

The function returns the final res vector containing the spiral order traversal: [1, 2, 3, 6, 9, 8, 7, 4, 5].

Test Case 2: Rectangular Matrix

Input: matrix = [[1, 2, 3, 4], [5, 6, 7, 8]]
Expected Output: [1, 2, 3, 4, 8, 7, 6, 5]

Walkthrough:

This case follows similar logic to the first test case, but with fewer layers due to the rectangular shape. The code will traverse the elements in a spiral pattern, starting from the top-left corner and moving inwards until all elements are visited.

Real-World Applications: Beyond the Classroom

• Image Processing: When dealing with digital images represented as matrices (pixels as elements), spiral order traversal can be used for efficient image compression techniques. By prioritizing central pixels that often contain crucial image information, this approach can achieve better compression ratios.
• Data Mining: When analyzing large datasets represented as matrices, spiral order traversal can be used to prioritize processing central elements that might hold more valuable or statistically significant information compared to the edges.

These are just a few examples, and the specific applications can vary depending on the software and its purpose. However, the core concept of efficiently iterating through a matrix in a spiral pattern proves valuable in various real-world scenarios.

Conclusion

We’ve successfully navigated the challenge of finding the spiral order traversal in a matrix! This problem not only tested our understanding of matrix manipulation and loops but also introduced a valuable concept with practical applications. By combining clear explanations, code breakdown, and real-world examples, I have hopefully provided a comprehensive guide to tackling this spiral adventure.