23.02.10 Today’s Leetcode

1162. As Far from Land as Possible (medium)

1. Brute Force (O(n^3))

class Solution:
    def maxDistance(self, grid: List[List[int]]) -> int:
        def dst(p1, p2):
            return abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])

        islands = []
        n = len(grid)
        for i in range(n):
            for j in range(n):
                if grid[i][j] == 1:
                    islands.append([i, j])

        res = -1
        for i in range(n):
            for j in range(n):
                if grid[i][j] == 0:
                    temp = 10**9
                    for island in islands:
                        temp = min(temp, dst([i, j], island))
                    if temp != 10**9:
                        res = max(res, temp)
                        
        return res

1. BFS

class Solution:
    def maxDistance(self, grid: List[List[int]]) -> int:
        def dst(p1, p2):
            return abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])

        def let(x, y):
            n = len(grid)
            if x < 0 or x >= n or y < 0 or y >= n:
                return False
            if grid[x][y] == 1:
                return False
            grid[x][y] = 1
            return True

        islands = []
        temp = []
        n = len(grid)
        for i in range(n):
            for j in range(n):
                if grid[i][j] == 1:
                    islands.append([i, j])
        
        distance = 0
        while islands:
            target = islands.pop()
            # print(islands)
            x, y = target
            dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]]
            for dir_ in dirs:
                i, j = x + dir_[0], y + dir_[1]
                if let(i, j):
                    temp.append([i, j])
            if len(islands) == 0 and len(temp) > 0:
                islands = temp
                temp = []
                distance += 1
    
        return -1 if distance == 0 else distance
        

1. DP

class Solution {
    public int maxDistance(int[][] grid) {
        int rows = grid.length;
        // Although it's a square matrix, using different variable for readability.
        int cols = grid[0].length;
        
        // Maximum manhattan distance possible + 1.
        final int MAX_DISTANCE = rows + cols + 1;

        int[][] dist = new int[rows][cols];
        for (int[] arr : dist)
            Arrays.fill(arr, MAX_DISTANCE);

        // First pass: check for left and top neighbours
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                // Distance of land cells will be 0.
                if (grid[i][j] == 1) {
                    dist[i][j] = 0;
                } else {
                    // Check left and top cell distances if they exist and update the current cell distance.
                    dist[i][j] = Math.min(dist[i][j], Math.min(i > 0 ? dist[i - 1][j] + 1 : MAX_DISTANCE,
                                                               j > 0 ? dist[i][j - 1] + 1 : MAX_DISTANCE));
                }
            }
        }

        // Second pass: check for the bottom and right neighbours.
        int ans = Integer.MIN_VALUE;
        for (int i = rows - 1; i >= 0; i--) {
            for (int j = cols - 1; j >= 0; j--) {
                // Check the right and bottom cell distances if they exist and update the current cell distance.
                dist[i][j] = Math.min(dist[i][j], Math.min(i < rows - 1 ? dist[i + 1][j] + 1 : MAX_DISTANCE,
                                                           j < cols - 1 ? dist[i][j + 1] + 1 : MAX_DISTANCE));
                
                ans = Math.max(ans, dist[i][j]);
            }
        }

        // If ans is 0, it means there is no water cell,
        // If ans is MAX_DISTANCE, it implies no land cell.
        return ans == 0 || ans == MAX_DISTANCE ? -1 : ans;
    }
};

566. Reshape the Matrix (easy)

class Solution:
    def matrixReshape(self, mat: List[List[int]], r: int, c: int) -> List[List[int]]:
        m, n = len(mat), len(mat[0])
        x, y = 0, 0
        if m * n != r * c:
            return mat
        res = [[0 for u in range(c)] for v in range(r)]
        for i in range(m):
            for j in range(n):
                res[x][y] = mat[i][j]
                y += 1
                if y == c:
                    x += 1
                    y = 0
        return res

118. Pascal’s Triangle (easy)

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        res = []
        for i in range(1, numRows + 1):
            temp = [0 for _ in range(i)]
            temp[0] = temp[-1] = 1
            for j in range(1, i - 1):
                temp[j] = res[-1][j - 1] + res[-1][j]
            res.append(temp)
        return res