SAMSUNG 49-Inch Odyssey G9

Because earth is not flat

Description

The problem requires filling an m x n matrix in spiral order using the values from a singly linked list. The matrix should be filled with the values of the list from the top-left corner in a clockwise spiral fashion. If there are more matrix cells than values in the list, the remaining cells should be filled with -1.

Intuition

The idea behind this problem is to traverse the matrix in a spiral manner while filling each cell with the values from the linked list. The direction changes (right, down, left, up) happen when the matrix boundaries or previously filled cells are encountered. Once the traversal is completed, any remaining unfilled cells are set to -1.

Approach

1. Initialize an empty matrix of size m x n with all values set to -1.
2. Set the initial direction to right (r).
3. Start from the top-left corner of the matrix (position [0, 0]).
4. For each node in the linked list:
   • Place its value in the current matrix cell.
   • Depending on the current direction (r, d, l, or u), attempt to move to the next cell.
   • If moving in the current direction leads outside the matrix or to an already filled cell, change the direction (from right to down, from down to left, etc.).
5. Continue until all nodes are processed or the matrix is completely filled.
6. If there are leftover matrix cells and no more list nodes, leave them as -1.

Complexity

Time Complexity: O(m * n)

We visit each cell in the matrix exactly once, which means the total time taken is proportional to the number of cells in the matrix.

Space Complexity: O(m * n)

We need to store the entire matrix of size m x n, and no additional significant space is used apart from the matrix and constant variables.

Code

C++

class Solution {
public:
    vector<vector<int>> spiralMatrix(int m, int n, ListNode* head) {
        vector<vector<int>> matrix(m, vector<int>(n, -1));
        string flag = "r";
        int row = 0, col = 0;

        while (head != nullptr) {
            matrix[row][col] = head->val;
            
            // Determine the next direction
            if (flag == "r" && (col + 1 >= n || matrix[row][col + 1] != -1)) flag = "d";
            else if (flag == "d" && (row + 1 >= m || matrix[row + 1][col] != -1)) flag = "l";
            else if (flag == "l" && (col - 1 < 0 || matrix[row][col - 1] != -1)) flag = "u";
            else if (flag == "u" && (row - 1 < 0 || matrix[row - 1][col] != -1)) flag = "r";
            
            // Move based on the current direction
            if (flag == "r") col++;
            else if (flag == "d") row++;
            else if (flag == "l") col--;
            else if (flag == "u") row--;
            
            // If the next position is already filled, break
            if (row >= m || col >= n || row < 0 || col < 0 || matrix[row][col] != -1) break;
            
            head = head->next;
        }
        return matrix;
    }
};

Python

class Solution:
    def spiralMatrix(self, m: int, n: int, head: ListNode) -> list[list[int]]:
        matrix = [[-1] * n for _ in range(m)]
        flag = 'r'
        row, col = 0, 0

        while head:
            matrix[row][col] = head.val

            # Determine the next direction
            if flag == 'r' and (col + 1 >= n or matrix[row][col + 1] != -1):
                flag = 'd'
            elif flag == 'd' and (row + 1 >= m or matrix[row + 1][col] != -1):
                flag = 'l'
            elif flag == 'l' and (col - 1 < 0 or matrix[row][col - 1] != -1):
                flag = 'u'
            elif flag == 'u' and (row - 1 < 0 or matrix[row - 1][col] != -1):
                flag = 'r'

            # Move based on the current direction
            if flag == 'r':
                col += 1
            elif flag == 'd':
                row += 1
            elif flag == 'l':
                col -= 1
            elif flag == 'u':
                row -= 1

            # If the next position is already filled, break
            if row >= m or col >= n or row < 0 or col < 0 or matrix[row][col] != -1:
                break

            head = head.next

        return matrix

Java

class Solution {
    public int[][] spiralMatrix(int m, int n, ListNode head) {
        int[][] matrix = new int[m][n];
        for (int[] row : matrix) {
            Arrays.fill(row, -1);
        }
        
        String flag = "r";
        int row = 0, col = 0;

        while (head != null) {
            matrix[row][col] = head.val;

            // Determine the next direction
            if (flag.equals("r") && (col + 1 >= n || matrix[row][col + 1] != -1)) flag = "d";
            else if (flag.equals("d") && (row + 1 >= m || matrix[row + 1][col] != -1)) flag = "l";
            else if (flag.equals("l") && (col - 1 < 0 || matrix[row][col - 1] != -1)) flag = "u";
            else if (flag.equals("u") && (row - 1 < 0 || matrix[row - 1][col] != -1)) flag = "r";

            // Move based on the current direction
            if (flag.equals("r")) col++;
            else if (flag.equals("d")) row++;
            else if (flag.equals("l")) col--;
            else if (flag.equals("u")) row--;

            // If the next position is already filled, break
            if (row >= m || col >= n || row < 0 || col < 0 || matrix[row][col] != -1) break;

            head = head.next;
        }
        return matrix;
    }
}

JavaScript

var spiralMatrix = function (m, n, head) {

    const matrix = new Array(m).fill(null).map(() => new Array(n).fill(-1));
    let flag = 'r';
    let row = 0;
    let col = 0;
    let scannedCol = 0;
    let scannedRow = 0;

    while (head) {
        matrix[row][col] = head.val

        if (flag === 'r' && matrix[row][col + 1] !== -1) {
            flag = 'd'
        } else if (flag === 'd' && matrix[row + 1]?.[col] !== -1) {
            flag = 'l'
        } else if (flag === 'l' && matrix[row]?.[col - 1] !== -1) {
            flag = 'u'
        } else if (flag === 'u' && matrix[row - 1]?.[col] !== -1) {
            flag = 'r'
        }

        if (flag === 'r') {
            col++
        }
        if (flag === 'd') {
            row++
        }
        if (flag === 'l') {
            col--
        }
        if (flag === 'u') {
            row--
        }
        if (matrix[row]?.[col] !== -1) {
            break;
        }

        head = head.next
    }
    return matrix
};