algoadvance

Leetcode 3248. Snake in Matrix

Problem Statement

You have been given a matrix of size m x n. Your task is to return a list of integers representing the matrix in a “snake-like” order. The snake-like pattern starts from the top-left corner and moves to the end of the row, then changes direction, moves down to the next row, and repeats the process.

Clarifying Questions

  1. Input Constraints: What are the constraints on the dimensions of the matrix m and n?
  2. Matrix Contents: Are there any constraints on the values within the matrix (e.g., positive integers, negative integers, or any integer)?
  3. Empty Matrix: How should the function handle an empty matrix?
  4. Edge Cases: Should the solution consider matrices that have only one row or one column?

Answers and Assumptions:

  1. Let’s assume that the matrix dimensions m and n are such that ( 0 \leq m, n \leq 1000 ).
  2. The values within the matrix can be any integers.
  3. If the matrix is empty, the function will return an empty list.
  4. The solution should handle edge cases such as matrices with a single row or column.

Example

For a matrix:

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

The snake-like order would be:

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

Strategy

To solve this problem, we can:

  1. Traverse each row in the matrix.
  2. If the row index is even, traverse from left to right.
  3. If the row index is odd, traverse from right to left.
  4. Append the traversed elements to the result list.

The steps are as follows:

  1. Initialize an empty list to store the result.
  2. Iterate over each row in the matrix using a loop.
  3. Based on the row index (even or odd), traverse the row accordingly and append the elements to the result list.
  4. Return the result list.

Code

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

public class SnakeInMatrix {
    public List<Integer> snakeOrder(int[][] matrix) {
        List<Integer> result = new ArrayList<>();
        if (matrix == null || matrix.length == 0) {
            return result;
        }
        int m = matrix.length;
        int n = matrix[0].length;

        for (int i = 0; i < m; i++) {
            if (i % 2 == 0) {
                // Move left to right for even-indexed rows
                for (int j = 0; j < n; j++) {
                    result.add(matrix[i][j]);
                }
            } else {
                // Move right to left for odd-indexed rows
                for (int j = n - 1; j >= 0; j--) {
                    result.add(matrix[i][j]);
                }
            }
        }
        return result;
    }

    // Helper method to print the result
    public static void main(String[] args) {
        SnakeInMatrix sim = new SnakeInMatrix();
        int[][] matrix = {
            {1, 2, 3},
            {4, 5, 6},
            {7, 8, 9}
        };
        System.out.println(sim.snakeOrder(matrix)); // Output: [1, 2, 3, 6, 5, 4, 7, 8, 9]
    }
}

Time Complexity

The time complexity of this solution is O(m * n), where m is the number of rows and n is the number of columns in the matrix. This is because we iterate over each element in the matrix exactly once.

The space complexity is O(m * n) for the result list which stores all the elements of the matrix.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI