Tasks

Matrices

Index	Task Name	Task Number	Difficulty	Link
1	Spiral Matrix	54	Medium	Spiral Matrix on LeetCode
2	Set Matrix Zeroes	73	Medium	Set Matrix Zeroes on LeetCode
3	Rotate Image	48	Medium	Rotate Image on LeetCode
4	Number of Islands	200	Medium	Number of Islands on LeetCode
5	Maximal Square	221	Medium	Maximal Square on LeetCode
6	Search a 2D Matrix	74	Medium	Search a 2D Matrix on LeetCode
7	Pacific Atlantic Water Flow	417	Medium	Pacific Atlantic Water Flow on LeetCode
8	Word Search II	212	Hard	Word Search II on LeetCode
9	Longest Increasing Path in a Matrix	329	Hard	Longest Increasing Path in a Matrix on LeetCode
10	Island Perimeter	463	Easy	Island Perimeter on LeetCode
11	Where Will the Ball Fall	1706	Medium	Link

// 54. Spiral Matrix

// Time: O(n * m)
// Space: O(n * m)
var spiralOrder = function(matrix) {
    // Get the number of rows in the matrix.
    let rows = matrix.length;
    // Get the number of columns in the matrix.
    let cols = matrix[0].length;
    // Initialize the current row pointer.
    let row = 0;
    // Initialize the current column pointer (starts at -1 to account for the initial increment).
    let col = -1;
    // Initialize the direction of traversal (1 for right/bottom, -1 for left/top).
    let direction = 1;
    // Initialize an array to store the spiral order elements.
    const result = [];

    // Continue while there are rows and columns left to traverse in the matrix.
    while (rows > 0 && cols > 0) {
        // Traverse from left to right along the current row.
        for (let i = 0; i < cols; i++) {
            // Update the column pointer.
            col += direction;
            // Push the current element to the result array.
            result.push(matrix[row][col]);
        }
        // Decrement the number of remaining rows to traverse.
        rows--;

        // Traverse from top to bottom along the current column.
        for (let i = 0; i < rows; i++) {
            // Update the row pointer.
            row += direction;
            // Push the current element to the result array.
            result.push(matrix[row][col]);
        }
        // Decrement the number of remaining columns to traverse.
        cols--;

        // Change the direction of traversal (right to left or left to right).
        direction *= -1;
    }

    // Return the spiral order result.
    return result;
};

// 73. Set Matrix Zeroes

// Time: O(m * n)
// Space: O(1)
var setZeroes = function(mat) {
    // Get the number of rows and columns in the matrix.
    const rows = mat.length;
    const cols = mat[0].length;

    // Initialize flags to track whether the first row and first column should be set to zero.
    let fcol = false;
    let frow = false;

    // Check if the first column contains any zeros.
    for (let i = 0; i < rows; i++) {
        if (mat[i][0] === 0) {
            fcol = true;
            break;
        }
    }

    // Check if the first row contains any zeros.
    for (let i = 0; i < cols; i++) {
        if (mat[0][i] === 0) {
            frow = true;
            break;
        }
    }

    // Iterate through the rest of the matrix to mark zeros by modifying the first row and column.
    for (let i = 1; i < rows; i++) {
        for (let j = 1; j < cols; j++) {
            if (mat[i][j] === 0) {
                mat[0][j] = mat[i][0] = 0;
            }
        }
    }

    // Set zeros in rows based on the first column's flags.
    for (let i = 1; i < rows; i++) {
        if (mat[i][0] === 0) {
            mat[i].fill(0);
        }
    }

    // Set zeros in columns based on the first row's flags.
    for (let j = 1; j < cols; j++) {
        if (mat[0][j] === 0) {
            for (let i = 1; i < rows; i++) {
                mat[i][j] = 0;
            }
        }
    }

    // If the first column originally contained zeros, set the entire column to zeros.
    if (fcol) {
        for (let i = 0; i < rows; i++) {
            mat[i][0] = 0;
        }
    }

    // If the first row originally contained zeros, set the entire row to zeros.
    if (frow) {
        mat[0].fill(0);
    }

    // Return the modified matrix with zeros set accordingly.
    return mat;
};

/*
Matrices
---------------------------------
1. Check if first row/column contains 0. Set flags accordingly.
2. Check other rows/columns. Set first element of row/column to 0 if row/col contains 0.
3. Check first element in every other row/col to fill row/col with 0 if needed.
4. Check flags for the first row/col to fill with 0 if needed.
5. Return result matrix.
---------------------------------
Time: O(n * m) | Space: O(1)
*/

// 48. Rotate Image

// Time: O(n^2)
// Space: O(1)
var rotate = function(matrix) {
    const n = matrix.length; // Get the size of the square matrix.

    // Transpose the matrix (swap rows and columns).
    for (let i = 0; i < n; i++) {
        for (let j = i; j < n; j++) {
            // Swap matrix[i][j] with matrix[j][i]
            const temp = matrix[i][j];
            matrix[i][j] = matrix[j][i];
            matrix[j][i] = temp;
        }
    }

    // Reverse each row to complete the rotation.
    for (let i = 0; i < n; i++) {
        matrix[i].reverse();
    }
};

/*
Matrices
------------------------------
1. Swap rows and columns.
2. Reverse each row.
------------------------------
Time: O(n^2) | Space: O(1)
*/

// 1706. Where Will the Ball Fall

// Time: O(row * col)
// Space: O(col)
var findBall = function(grid) {
    // Initialize an array called 'result' to store the final position of the ball for each column.
    const result = Array(grid[0].length).fill(-1);

    // Iterate through each column in the grid.
    for (let col = 0; col < grid[0].length; col++) {
        // Initialize the currentColumn variable to the current column index.
        let currentColumn = col;

        // Iterate through each row in the grid for the current column.
        for (let row = 0; row < grid.length; row++) {
            // Calculate the nextColumn, which is the column the ball will move to in the next row.
            let nextColumn = currentColumn + grid[row][currentColumn];

            const outsideLeftBoundary = nextColumn < 0;
            const outsideRightBoundary = nextColumn >= grid[0].length;
            const itsATrap = grid[row][currentColumn] !== grid[row][nextColumn];

            // Check if the ball goes out of bounds or hits a wall in the next row.
            if (outsideLeftBoundary || outsideRightBoundary || itsATrap) {
                // If any of the above conditions are met, break out of the loop for this column.
                break;
            }

            // If the ball reaches the last row without going out of bounds or hitting a wall, 
            // update the result array with the final column position for this column.
            if (row === grid.length - 1) {
                result[col] = nextColumn;
            }

            // Update the currentColumn to the nextColumn for the next iteration.
            currentColumn = nextColumn;
        }
    }

    // Return the result array containing the final positions of the ball for each column.
    return result;
};