Matrix

46. Set Matrix Zeroes

1. The problem "Set Matrix Zeroes" on LeetCode can be found at: https://leetcode.com/problems/set-matrix-zeroes/

2. Here is the optimized Java code for the "Set Matrix Zeroes" problem with detailed comments:

class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        
        // Variables to track if first row and column has zeros
        boolean firstRowZero = false;
        boolean firstColZero = false;
        
        // Check if first row has zeros
        for (int j = 0; j < n; j++) {
            if (matrix[0][j] == 0) {
                firstRowZero = true;
                break;
            }
        }
        
        // Check if first column has zeros
        for (int i = 0; i < m; i++) {
            if (matrix[i][0] == 0) {
                firstColZero = true;
                break;
            }
        }
        
        // Use first row and column as markers for zeros in matrix
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][j] == 0) {
                    matrix[0][j] = 0;
                    matrix[i][0] = 0;
                }
            }
        }
        
        // Clear rows based on markers in first column
        for (int i = 1; i < m; i++) {
            if (matrix[i][0] == 0) {
                for (int j = 1; j < n; j++) {
                    matrix[i][j] = 0;
                }
            }
        }
        
        // Clear columns based on markers in first row
        for (int j = 1; j < n; j++) {
            if (matrix[0][j] == 0) {
                for (int i = 1; i < m; i++) {
                    matrix[i][j] = 0;
                }
            }
        }
        
        // Clear first row if necessary
        if (firstRowZero) {
            for (int j = 0; j < n; j++) {
                matrix[0][j] = 0;
            }
        }
        
        // Clear first column if necessary
        if (firstColZero) {
            for (int i = 0; i < m; i++) {
                matrix[i][0] = 0;
            }
        }
    }
}

1. Description of the algorithm:

   • Firstly, we iterate through the first row and column of the matrix to check if there are any zeros. We use boolean variables firstRowZero and firstColZero to track this information.

   • Next, we iterate through the rest of the matrix (excluding the first row and column) and use the first row and column as markers. Whenever we encounter a zero in matrix[i][j], we set the corresponding cell in the first row matrix[0][j] and the first column matrix[i][0] to zero.

   • After marking the zeros, we iterate through the first column (excluding the first row) to clear the corresponding rows if matrix[i][0] is zero.

   • Similarly, we iterate through the first row (excluding the first column) to clear the corresponding columns if matrix[0][j] is zero.

   • Finally, if firstRowZero is true, we clear the entire first row with zeros. If firstColZero is true, we clear the entire first column with zeros.

   This algorithm works by using the first row and column as markers for zeros in the matrix. By doing this in multiple passes, we ensure that we do not incorrectly mark cells that should not be zeros.

   During the interview process, it is important to think about how to optimize the space complexity of the solution. The above solution has a space complexity of O(1) as we are reusing the first row and column of the matrix to mark the zeros. This is a commonly asked question during interviews.

2. Problem abstractions that use a similar algorithm:

   Problems that involve marking or modifying certain cells in a matrix based on specific conditions can be approached using a similar algorithm of using one or more rows/columns of the matrix as markers.

   Some examples include:

   • Zero Matrix (Follow-up to this problem)

   • Game of Life

   • Rotate Image

   • Set Matrix Zeroes II (Follow-up to this problem with additional constraints)

3. Similar problems:

   • Zero Matrix (Follow-up to "Set Matrix Zeroes"): https://leetcode.com/problems/zero-matrix/

   • Game of Life: https://leetcode.com/problems/game-of-life/

   • Rotate Image: https://leetcode.com/problems/rotate-image/

   • Set Matrix Zeroes II (Follow-up to "Set Matrix Zeroes" with additional constraints): https://leetcode.com/problems/set-matrix-zeroes-ii/

47. Spiral Matrix

1. Problem Description:

   • Problem: Spiral Matrix

   • Link: Spiral Matrix Problem on LeetCode

2. Java code for Spiral Matrix problem:

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

public class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> result = new ArrayList<>();
        
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return result;
        }
        
        int m = matrix.length;
        int n = matrix[0].length;
        
        int top = 0, bottom = m - 1;
        int left = 0, right = n - 1;
        
        while(result.size() < m * n) {
            // Traverse top row
            for(int i = left; i <= right && result.size() < m * n; i++) {
                result.add(matrix[top][i]);
            }
            top++;
            
            // Traverse right column
            for(int i = top; i <= bottom && result.size() < m * n; i++) {
                result.add(matrix[i][right]);
            }
            right--;
            
            // Traverse bottom row
            for(int i = right; i >= left && result.size() < m * n; i--) {
                result.add(matrix[bottom][i]);
            }
            bottom--;
            
            // Traverse left column
            for(int i = bottom; i >= top && result.size() < m * n; i--) {
                result.add(matrix[i][left]);
            }
            left++;
        }
        
        return result;
    }
}

1. Algorithm Description:

   • The algorithm follows a simple pattern of traversing the boundaries of the matrix in a clockwise manner.

   • It keeps track of the top, bottom, left, and right boundaries of the remaining unvisited region in the matrix.

   • At each step, it adds the elements from the top row, right column, bottom row, and left column into the result list, while updating the boundaries accordingly.

   • The process continues until all elements of the matrix have been visited.

2. Similar Problems:

   • The spiral matrix algorithm can be suited to solve problems that involve traversing a 2D array in a spiral or clockwise manner. Some similar problems include:

     • Spiral Matrix II: Construct a matrix filled with the numbers from 1 to n^2 in a clockwise spiral order.

     • Spiral Matrix III: Traverse and return the coordinates of a matrix filled with numbers in the order of visiting cells in a spiral pattern starting from the top-left cell.

3. Similar Problems with Java code:

// Spiral Matrix II
public class Solution {
    public int[][] generateMatrix(int n) {
        int[][] matrix = new int[n][n];
        
        int top = 0, bottom = n - 1;
        int left = 0, right = n - 1;
        int num = 1;
        
        while(num <= n * n) {
            // Traverse top row
            for(int i = left; i <= right; i++) {
                matrix[top][i] = num++;
            }
            top++;
            
            // Traverse right column
            for(int i = top; i <= bottom; i++) {
                matrix[i][right] = num++;
            }
            right--;
            
            // Traverse bottom row
            for(int i = right; i >= left; i--) {
                matrix[bottom][i] = num++;
            }
            bottom--;
            
            // Traverse left column
            for(int i = bottom; i >= top; i--) {
                matrix[i][left] = num++;
            }
            left++;
        }
        
        return matrix;
    }
}

// Spiral Matrix III
public class Solution {
    public int[][] spiralMatrixIII(int R, int C, int r0, int c0) {
        int[][] result = new int[R * C][2];
        
        int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        int direction = 0;
        
        int steps = 1;
        int count = 0;
        int pos = 0;
        
        while(count < R * C) {
            if(direction % 2 == 0) {
                steps++;
            }
            
            for(int i = 0; i < steps; i++) {
                int newRow = r0 + directions[direction][0];
                int newCol = c0 + directions[direction][1];
                
                if(newRow >= 0 && newRow < R && newCol >= 0 && newCol < C) {
                    result[pos][0] = newRow;
                    result[pos][1] = newCol;
                    count++;
                    pos++;
                }
                
                r0 = newRow;
                c0 = newCol;
            }
            
            direction = (direction + 1) % 4;
        }
        
        return result;
    }
}

These solutions provide the basic implementation of the spiral matrix algorithm in different scenarios.

48. Rotate Image

1. Problem Description: The problem "Rotate Image" on LeetCode (https://leetcode.com/problems/rotate-image/) asks us to rotate an N x N 2D matrix (image) in-place by 90 degrees.

2. Optimized Java Code with Comments:

public class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        
        // Transpose the matrix
        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;
            }
        }
        
        // 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-j-1];
                matrix[i][n-j-1] = temp;
            }
        }
    }
}

1. Algorithm Explanation: To rotate the matrix, we can perform two operations: transpose and reverse.

First, we transpose the matrix by swapping elements at position (i, j) with (j, i). This effectively reflects the matrix along its main diagonal.

Then, we reverse each row of the transposed matrix. This is done by swapping elements at position (i, j) with (i, n-j-1) where n is the size of the matrix.

By performing these two operations, the matrix is rotated by 90 degrees in a clockwise direction.

During an interview, it's important to explain the algorithm step by step, highlighting the key operations and their purpose. Emphasize the fact that the rotation is performed in-place, which means we modify the original matrix without using any additional space.

1. This algorithm can be used to solve similar problems that involve rotations or reflections of a matrix. Some examples include:

• "Rotate Image II": A variant of the Rotate Image problem where instead of rotating by 90 degrees, we need to rotate by an arbitrary angle.

• "Flip Image": Given a binary matrix, we need to reverse each row of the matrix.

• "Rotate List": Given a linked list, rotate the list to the right by k places.

1. Similar Problems with Java Code and Descriptions:

• "Rotate Image II" (https://leetcode.com/problems/rotate-image-ii/):

public class Solution {
    public void rotate(int[][] matrix, int angle) {
        int n = matrix.length;
        
        // Transpose the matrix
        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;
            }
        }
        
        // Rotate by an arbitrary angle
        int rotations = angle / 90;
        for(int r=0; r<rotations; r++){
            // 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-j-1];
                    matrix[i][n-j-1] = temp;
                }
            }
        }
    }
}

• "Flip Image" (https://leetcode.com/problems/flipping-an-image/):

public class Solution {
    public int[][] flipAndInvertImage(int[][] image) {
        int n = image.length;
        
        // Reverse each row
        for(int i=0; i<n; i++){
            for(int j=0; j<n/2; j++){
                int temp = image[i][j];
                image[i][j] = image[i][n-j-1];
                image[i][n-j-1] = temp;
            }
        }
        
        // Invert each cell
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                image[i][j] = 1 - image[i][j];
            }
        }
        
        return image;
    }
}

• "Rotate List" (https://leetcode.com/problems/rotate-list/):

public class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if(head == null || head.next == null || k == 0)
            return head;
        
        // Get the length of the list
        int length = 0;
        ListNode currentNode = head;
        while(currentNode != null){
            length++;
            currentNode = currentNode.next;
        }
        
        // Adjust k to be within the length of the list
        k = k % length;
        
        if(k == 0)
            return head;
        
        // Find the new head after rotation
        ListNode fastPointer = head;
        ListNode slowPointer = head;
        for(int i=0; i<k; i++){
            fastPointer = fastPointer.next;
        }
        
        while(fastPointer.next != null){
            fastPointer = fastPointer.next;
            slowPointer = slowPointer.next;
        }
        
        ListNode newHead = slowPointer.next;
        slowPointer.next = null;
        fastPointer.next = head;
        
        return newHead;
    }
}

These are just a few examples, but the transpose and reverse operations can be applied to a variety of problems involving matrix manipulations.

49. Word Search

Sure! Here is the solution to the "Word Search" problem on LeetCode.

1. Problem Description:

   • Problem Link: Word Search

   • Given a 2D board and a word, find if the word exists in the grid. The word can be constructed from letters of adjacent cells horizontally or vertically. The same letter cell may not be used more than once.

2. Optimized Java Code:

class Solution {
    public boolean exist(char[][] board, String word) {
        // Convert the word to a character array for easy access
        char[] target = word.toCharArray();
        
        // Iterate through the board and search for the word
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (search(board, i, j, target, 0)) {
                    return true;
                }
            }
        }
        return false;
    }
    
    private boolean search(char[][] board, int row, int col, char[] target, int index) {
        // Base case: If we have matched all characters in the word, return true
        if (index == target.length) {
            return true;
        }
        
        // Check for out of bounds or if the current cell is not equal to the target character
        if (row < 0 || row >= board.length || col < 0 || col >= board[0].length || board[row][col] != target[index]) {
            return false;
        }
        
        // Mark the current cell as visited
        board[row][col] ^= 256;
        
        // Recursively search in all four directions
        boolean found =
            search(board, row + 1, col, target, index + 1) ||
            search(board, row - 1, col, target, index + 1) ||
            search(board, row, col + 1, target, index + 1) ||
            search(board, row, col - 1, target, index + 1);
        
        // Unmark the current cell after the search is complete
        board[row][col] ^= 256;
        
        // Return the search result
        return found;
    }
}

1. Algorithm Description:

   • To solve this problem, we can perform a backtracking search starting from each cell in the board. At each step, we check if the current cell matches the current character of the target word, and if so, we mark it as visited and continue the search recursively in all four directions (up, down, left, right).

   • To optimize the space complexity, we can make use of the board itself to temporarily mark the currently visited cells by using the XOR operation. This way, we don't need to create a separate visited array.

   • We return true if we have matched all characters of the word, and false otherwise. If at any point the search fails (out of bounds or mismatch), we backtrack by unmarking the current cell and continue the search from another direction.

   • This algorithm has a time complexity of O(N * 3^L), where N is the number of cells in the board and L is the length of the target word. The 3^L factor comes from the branching factor of search in four directions (up, down, left, right), and L represents the depth of the recursive call stack.

2. Similar Problems:

   • The algorithm used in the "Word Search" problem can be abstracted to be applied in other problems that involve backtracking and searching for a specific pattern or combination of characters in a given matrix/grid. Some similar problems include:

     • Number of Islands

     • Sudoku Solver

     • Path Sum III

3. Similar Problems with Java Code and Descriptions:

• Number of Islands:

class Solution {
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }
        
        int count = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == '1') {
                    count++;
                    dfs(grid, i, j);
                }
            }
        }
        
        return count;
    }
    
    private void dfs(char[][] grid, int row, int col) {
        if (row < 0 || row >= grid.length || col < 0 || col >= grid[0].length || grid[row][col] == '0') {
            return;
        }
        
        grid[row][col] = '0';
        
        dfs(grid, row + 1, col);
        dfs(grid, row - 1, col);
        dfs(grid, row, col + 1);
        dfs(grid, row, col - 1);
    }
}

• Sudoku Solver:

class Solution {
    public void solveSudoku(char[][] board) {
        solve(board);
    }
    
    private boolean solve(char[][] board) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.') {
                    for (char c = '1'; c <= '9'; c++) {
                        if (isValid(board, i, j, c)) {
                            board[i][j] = c;
                            if (solve(board)) {
                                return true;
                            } else {
                                board[i][j] = '.';
                            }
                        }
                    }
                    return false;
                }
            }
        }
        
        return true;
    }
    
    private boolean isValid(char[][] board, int row, int col, char c) {
        for (int i = 0; i < 9; i++) {
            if (board[i][col] == c || board[row][i] == c ||
                board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == c) {
                return false;
            }
        }
        return true;
    }
}

• Path Sum III:

class Solution {
    public int pathSum(TreeNode root, int sum) {
        if (root == null) {
            return 0;
        }
        
        return countPaths(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
    }
    
    private int countPaths(TreeNode node, int sum) {
        if (node == null) {
            return 0;
        }
        
        int count = 0;
        if (node.val == sum) {
            count++;
        }
        
        count += countPaths(node.left, sum - node.val);
        count += countPaths(node.right, sum - node.val);
        
        return count;
    }
}

Please note that these solutions are optimized for brevity and not necessarily for performance. In a real interview scenario, it's important to discuss the pros and cons of different approaches and optimize the code for efficiency if required.