Matrix

1380. Lucky Numbers in a Matrix

class Solution {
public:
    vector<int> luckyNumbers(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();

        vector<int> minRowVals(m, INT_MAX);
        vector<int> maxColVals(n, INT_MIN);

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                minRowVals[i] = std::min(minRowVals[i], matrix[i][j]);
                maxColVals[j] = std::max(maxColVals[j], matrix[i][j]);
            }
        }
        vector<int> res;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == minRowVals[i] && matrix[i][j] == maxColVals[j]) {
                    res.push_back(matrix[i][j]);
                }
            }
        }
        return res;
    }
};

867. Transpose Matrix

public int[][] transpose(int[][] A) {
    int m = A.length, n = A[0].length;
    int[][] res = new int[n][m];
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            res[j][i] = A[i][j];
        }
    }
    return res;
}

54. Spiral Matrix

public List<Integer> spiralOrder(int[][] matrix) {
    List<Integer> list = new ArrayList<>();
    if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return list;
    int bottom = matrix.length - 1, right = matrix[0].length - 1;
    int left = 0, top = 0;
    int k = 0;
    while (top <= bottom && left <= right) {
        for (int i = left; i <= right; i++) {
            if (inValid(list, matrix)) return list;
            list.add(matrix[top][i]);
        }
        top++;
        for (int i = top; i <= bottom; i++) {
            if (inValid(list, matrix)) return list;
            list.add(matrix[i][right]);
        }
        right--;
        for (int i = right; i >= left; i--) {
            if (inValid(list, matrix)) return list;
            list.add(matrix[bottom][i]);
        }
        bottom--;
        for (int i = bottom; i >= top; i--) {
            if (inValid(list, matrix)) return list;
            list.add(matrix[i][left]);
        }
        left++;
    }
    return list;
}

private boolean inValid(List<Integer> list, int[][] matrix) {
    return list.size() >= matrix.length * matrix[0].length;
}

public List < Integer > spiralOrder(int[][] matrix) {
    List ans = new ArrayList();
    if (matrix.length == 0)
        return ans;
    int r1 = 0, r2 = matrix.length - 1;
    int c1 = 0, c2 = matrix[0].length - 1;
    while (r1 <= r2 && c1 <= c2) {
        for (int c = c1; c <= c2; c++) ans.add(matrix[r1][c]);
        for (int r = r1 + 1; r <= r2; r++) ans.add(matrix[r][c2]);
        if (r1 < r2 && c1 < c2) {
            for (int c = c2 - 1; c > c1; c--) ans.add(matrix[r2][c]);
            for (int r = r2; r > r1; r--) ans.add(matrix[r][c1]);
        }
        r1++;
        r2--;
        c1++;
        c2--;
    }
    return ans;
}

59. Spiral Matrix II

public int[][] generateMatrix(int n) {
    int[][] m = new int[n][n];
    int k = 1;
    int top = 0, bottom = n - 1, left = 0, right = n - 1;
    while (k <= n * n) {
        for (int i = left; i <= right; i++) {
            m[top][i] = k++;
        }
        top++;
        for (int i = top; i <= bottom; i++) {
            m[i][right] = k++;
        }
        right--;
        for (int i = right; i >= left; i--) {
            m[bottom][i] = k++;
        }
        bottom--;
        for (int i = bottom; i >= top; i--) {
            m[i][left] = k++;
        }
        left++;
    }
    return m;
}

1861. Rotating the Box

class Solution {
    public char[][] rotateTheBox(char[][] box) {
        int m = box.length;
        int n = box[0].length;
        char[][] rotated = new char[n][m];

        // Initialize rotated box with empty spaces
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                rotated[i][j] = '.';
            }
        }

        // Process each row: simulate stones falling right with obstacles
        for (int i = 0; i < m; i++) {
            int writePos = n - 1; // Position to place the next stone in the row after gravity
            for (int j = n - 1; j >= 0; j--) {
                if (box[i][j] == '*') {
                    // Place obstacle in rotated box
                    rotated[j][m - 1 - i] = '*';
                    // Reset write position to the left of the obstacle
                    writePos = j - 1;
                } else if (box[i][j] == '#') {
                    // Place stone at the write position
                    rotated[writePos][m - 1 - i] = '#';
                    writePos--;
                }
                // Empty spaces '.' are handled by initialization
            }
        }

        return rotated;
    }
}

1275. Find Winner on a Tic Tac Toe Game

public String tictactoe(int[][] moves) {
    int[][] board = new int[3][3];
    int step = 0;
    for (int i = 0; i < moves.length; i++) {
        int player = i % 2 == 0 ? 1 : -1;
        int x = moves[i][0], y = moves[i][1];
        board[x][y] = player;
        if (win(board, x, y, player)) {
            return player == 1 ? "A" : "B";
        }
        step++;
    }
    return step < 9 ? "Pending" : "Draw";
}

private boolean win(int[][] board, int x, int y, int p) {
    int rowcount = 0, colcount = 0;
    for (int i = 0; i < 3; i++) {
        if (board[x][i] == p) rowcount++;
        if (board[i][y] == p) colcount++;
    }
    if (colcount == 3 || rowcount == 3) return true;
    int diagcount = 0, adiagcount = 0;
    for (int i = 0; i < 3; i++) {
        if (board[i][i] == p) diagcount++;
        if (board[i][2 - i] == p) adiagcount++;
    }
    return diagcount == 3 || adiagcount == 3;
}

348. Design Tic-Tac-Toe

    int[][]board;
    int win;
    public TicTacToe(int n) {
        board = new int[n][n];
        this.win = 0;
    }
    
    /** Player {player} makes a move at ({row}, {col}).
        @param row The row of the board.
        @param col The column of the board.
        @param player The player, can be either 1 or 2.
        @return The current winning condition, can be either:
                0: No one wins.
                1: Player 1 wins.
                2: Player 2 wins. */
    public int move(int row, int col, int player) {
        if(this.win != 0){
            return this.win;
        }
        this.board[row][col] = player;
        if(checkCol(col, player) || checkRow(row,player) || checkRightDiagnal(player) || checkLeftDiagnal(player)){
            return player;
        }
        return 0;
    }
    private boolean checkCol(int col, int player){
        for(int i = 0; i < board.length; i++){
            if(board[i][col] != player){
                return false;
            }
        }
        return true;
    }
    private boolean checkRow(int row, int player){
        for(int i = 0;  i < board.length; i++){
            if(board[row][i] != player){
                return false;
            }
        }
        return true;
    }
    private boolean checkLeftDiagnal(int player){
        for(int i = 0; i < board.length; i++){
            if(board[i][i] != player){
                return false;
            }
        }
        return true;
    }
    private boolean checkRightDiagnal(int player){
        for(int i = 0; i < board.length; i++){
            if(board[i][board.length - i - 1] != player){
                return false;
            }
        }
        return true;
    }

/** Initialize your data structure here. */
int[][] board;
int count = 0, n = 0;
public TicTacToe(int n) {
    this.n = n;
    board = new int[n][n];
}

/** Player {player} makes a move at ({row}, {col}).
    @param row The row of the board.
    @param col The column of the board.
    @param player The player, can be either 1 or 2.
    @return The current winning condition, can be either:
            0: No one wins.
            1: Player 1 wins.
            2: Player 2 wins. */
public int move(int row, int col, int player) {
    board[row][col] = player;
    if (win(row, col, player)) return player;
    return 0;
}

private boolean win(int row, int col, int player) {
    int countRow = 0, countCol = 0;
    for (int i = 0; i < n; i++) {
        if (board[row][i] == player) countRow++;
        if (board[i][col] == player) countCol++;
    }
    if (countRow == n || countCol == n) return true;
    if (row == col || row == n - 1 - col) {
        int countDiag = 0, countAdiag = 0;
        for (int i = 0; i < n; i++) {
            if (board[i][i] == player) countDiag++;
            if (board[i][n - 1 - i] == player) countAdiag++;
        }
        if (countDiag == n || countAdiag == n) return true;
    }
    return false;
}

36. Valid Sudoku

    public boolean isValidSudoku(char[][] board) {
        Map<Integer, Set<Integer>> rowMap = new HashMap<>(); 
        Map<Integer, Set<Integer>> colMap = new HashMap<>();
        Map<Integer, Set<Integer>> gridMap = new HashMap<>();
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.') continue;
                int val = board[i][j] - '0';
                int grid = (i / 3) * 3 + j / 3; 
                rowMap.putIfAbsent(i, new HashSet<>());
                colMap.putIfAbsent(j, new HashSet<>());
                gridMap.putIfAbsent(grid, new HashSet<>());
                if (rowMap.get(i).contains(val) || colMap.get(j).contains(val) || gridMap.get(grid).contains(val)) return false;
                rowMap.get(i).add(val);
                colMap.get(j).add(val);
                gridMap.get(grid).add(val);
            }
        }
        return true;
    }

832. Flipping an Image

593. Valid Square

For a square, the distance of any edge and the diagonal distance are the same. Calculate the distance of the edges and validate them equal and larger than 0.

public boolean validSquare(int[] p1, int[] p2, int[] p3, int[] p4) {
    return check(p1,p2,p3,p4) || check(p1,p3,p2,p4) || check(p1,p4,p2,p3);
}

private boolean check(int[] p1, int[] p2, int[] p3, int[] p4) {
    return dist(p1, p2) == dist(p3, p4) 
        && dist(p1, p3) == dist(p2, p4) 
        && dist(p1, p4) == dist(p2, p3) 
        && dist(p1, p3) == dist(p2, p3) 
        && dist(p1, p4) == dist(p2, p4) 
        && dist(p1, p3) > 0;
}

private int dist(int[] p1, int[] p2) {
    return (p1[0] - p2[0]) * (p1[0] - p2[0]) + (p1[1] - p2[1]) * (p1[1] - p2[1]);
}

391. Perfect Rectangle

Two rules:

A bunch of rectangles can form a Perfect Rectangle or not. So the sum of areas of multiple rectangles should be equals to the sum of Perfect Rectangle.

The 2nd one is For a Perfect Rectangle formed by multiple rectangles, the count 4 point objects(can easily get it from a single array) presence MUST be an EVEN number.

So we need a set to verify ALL point objects that we get for each iteration - if we store it already, remove it; if not, add into the set.

Finally, for a valid perfect rectangle, the set should contain ONLY 4 point object and which is the point object for the Perfect Rectangle.

public boolean isRectangleCover(int[][] rectangles) {
    if (rectangles.length == 0 || rectangles[0].length == 0) return false;

    int x1 = Integer.MAX_VALUE;
    int x2 = Integer.MIN_VALUE;
    int y1 = Integer.MAX_VALUE;
    int y2 = Integer.MIN_VALUE;
    
    HashSet<String> set = new HashSet<String>();
    int area = 0;
    
    for (int[] rect : rectangles) {
        x1 = Math.min(rect[0], x1);
        y1 = Math.min(rect[1], y1);
        x2 = Math.max(rect[2], x2);
        y2 = Math.max(rect[3], y2);
        
        area += (rect[2] - rect[0]) * (rect[3] - rect[1]);
        
        String s1 = rect[0] + " " + rect[1];
        String s2 = rect[0] + " " + rect[3];
        String s3 = rect[2] + " " + rect[3];
        String s4 = rect[2] + " " + rect[1];
        
        if (!set.add(s1)) set.remove(s1);
        if (!set.add(s2)) set.remove(s2);
        if (!set.add(s3)) set.remove(s3);
        if (!set.add(s4)) set.remove(s4);
    }
    
    if (!set.contains(x1 + " " + y1) || 
        !set.contains(x1 + " " + y2) || 
        !set.contains(x2 + " " + y1) || 
        !set.contains(x2 + " " + y2) || 
        set.size() != 4) return false;
    return area == (x2-x1) * (y2-y1);
}

85. Maximal Rectangle

public int maximalRectangle(char[][] matrix) {
    for (int i = 0; i < matrix.length; i++) {
        for (int j = 1; j < matrix[0].length; j++) {
            if (matrix[i][j] == '1') {
                matrix[i][j] = (char) (matrix[i][j-1] + 1);
            } else {
                matrix[i][j] = '0';
            }
        }
    }
    int max = 0;
    for (int i = 0; i < matrix.length; i++) {
        for (int j = 0; j < matrix[0].length; j++) {
            int min = matrix[i][j] - '0';
            if (min > 0) {
                max = Math.max(max, min);
                for (int k = i-1; k >= 0 && matrix[k][j] != '0'; k--) {
                    min = Math.min(min, matrix[k][j] - '0');
                    max = Math.max(max, min * (i-k+1));
                }
            }
        }
    }
    return max;
}

840. Magic Squares In Grid

Brute force

public int numMagicSquaresInside(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    if (m < 3 || n < 3) return 0;
    int count = 0;
    for (int i = 0; i < m - 2; i++) {
        for (int j = 0; j < n - 2; j++) {
            if (valid(grid, i, j)) count++;
        }
    }
    return count;
}

private boolean valid(int[][] grid, int x, int y) {
    int[] arr = new int[10];
    for (int i = x; i < x + 3; i++) {
        for (int j = y; j < y + 3; j++) {
            if (grid[i][j] < 1 || grid[i][j] > 9 || arr[grid[i][j]] != 0) {
                return false;
            }
            arr[grid[i][j]] = 1;
        }
    }
    int sum1 = grid[x][y] + grid[x + 1][y + 1] + grid[x + 2][y + 2];
    int sum2 = grid[x + 2][y] + grid[x + 1][y + 1] + grid[x][y + 2];
    for (int i = 0; i < 3; i++) {
        if (grid[x + i][y] + grid[x + i][y + 1] + grid[x + i][y + 2] != sum1) return false;
        if (grid[x][y + i] + grid[x + 1][y + i] + grid[x + 2][y + i] != sum2) {
            return false;
        }
    }
    return sum1 == sum2;
}

1504. Count Submatrices With All Ones

DP solution: O(m*m*n)

public int numSubmat(int[][] matrix) {
    int m = matrix.length, n = matrix[0].length;
    int res = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (matrix[i][j] == 1) {
                matrix[i][j] += (j == 0) ? 0 : matrix[i][j - 1];
                int max = matrix[i][j];
                for (int k = i; k >= 0; k--) {
                    max = Math.min(max, matrix[k][j]);
                    res += max;
                }
            } 
        }
    }
    return res;
}

Stack Solution: Similar as histogram problem: O(m*n)

public int numSubmat(int[][] matrix) {
    int m = matrix.length, n = matrix[0].length;
    int res = 0;
    int[] h = new int[n];
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            h[j] = (matrix[i][j] == 0) ? 0 : h[j] + 1;
        }
        res += helper(h);
    }
    return res;
}

private int helper(int[] nums) {
    int n = nums.length;
    int[] sum = new int[n];
    Stack<Integer> stack = new Stack<>();
    for (int i = 0; i < n; i++) {
        while (!stack.isEmpty() && nums[stack.peek()] >= nums[i]) {
            stack.pop();
        }
        if (!stack.isEmpty()) {
            int preIndex = stack.peek();
            sum[i] = sum[preIndex];
            sum[i] += nums[i] * (i - preIndex);
        } else {
            sum[i] = nums[i] * (i + 1);
        }
        stack.push(i);
    }
    int res = 0;
    for (int nn : sum) res += nn;
    return res;
}

149. Max Points on a Line

O(n^3)

public int maxPoints(int[][] points) {
    int n = points.length;
    if (n < 3){
        return n;
    }
    int max = 2;
    for (int i = 0; i < n - 2; i++) {
        int base = 1;
        long x1 = points[i][0], y1 = points[i][1];
        for (int j = i + 1; j < n; j++) {
            int count = 0;
            long x2 = points[j][0], y2 = points[j][1];
            if (x1 == x2 && y1 == y2) {
                base++;
            } else {
                count = 1;
                for (int k = j + 1; k < n; k++) {
                    long x3 = points[k][0], y3 = points[k][1]; 
                    if ((x2 - x1)*(y3 - y1) == (x3 - x1)*(y2 - y1)) {
                        count++;
                    }
                }
            }
            max = Math.max(max, base + count);
        }
    }
    return max;
}

PreviousPrefixSum NextInterval & Sweepline

Last updated 9 months ago