23.03.01 Today’s Leetcode

912. Sort an Array (medium)

class Solution {
    public int[] sortArray(int[] nums) {
        mergeSort(nums,0,nums.length-1);
        return nums;
    }
    public static void mergeFun(int[] arr, int l, int m, int r) {
        int n1 = m + 1 - l;
        int n2 = r - m;
        int[] left = new int[n1];
        for (int i = 0; i < n1; i++) {
            left[i] = arr[l + i];
        }
        int[] right = new int[n2];
        for (int i = 0; i < n2; i++) {
            right[i] = arr[m + 1 + i];
        }
        int i = 0, j = 0, k = l;
        while (i < n1 || j < n2) {
            if (j == n2 || i < n1 && left[i] < right[j])
                arr[k++] = left[i++];
            else
                arr[k++] = right[j++];
        }
    }

    public static void mergeSort(int[] arr, int low, int high) {
        if (low < high) {
            int middle = (high - low) / 2 + low;
            mergeSort(arr, low, middle);
            mergeSort(arr, middle + 1, high);
            mergeFun(arr, low, middle, high);
        }
    }
}

542. 01 Matrix (medium)

BFS Approach

class Solution:
    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:
        m, n = len(mat), len(mat[0])
        DIR = [0, 1, 0, -1, 0]

        q = deque([])
        for r in range(m):
            for c in range(n):
                if mat[r][c] == 0:
                    q.append((r, c))
                else:
                    mat[r][c] = -1  # Marked as not processed yet!

        while q:
            r, c = q.popleft()
            for i in range(4):
                nr, nc = r + DIR[i], c + DIR[i + 1]
                if nr < 0 or nr == m or nc < 0 or nc == n or mat[nr][nc] != -1: continue
                mat[nr][nc] = mat[r][c] + 1
                q.append((nr, nc))
        return mat

DP Approach

class Solution:
    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:
        m, n = len(mat), len(mat[0])

        def get_value(mat, x, y):
            if x >= m or y >= n or x < 0 or y < 0:
                return 10**9
            return mat[x][y]

        for i in range(m):
            for j in range(n):
                if mat[i][j] == 0: continue
                mat[i][j] = min(get_value(mat, i - 1, j), get_value(mat, i, j - 1)) + 1
        
        for i in range(m - 1, -1, -1):
            for j in range(n - 1, -1, -1):
                if mat[i][j] == 0: continue
                mat[i][j] = min(mat[i][j], get_value(mat, i + 1, j) + 1, get_value(mat, i, j + 1) + 1)
        return mat

994. Rotting Oranges (medium)

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        q = deque([])
        count = 0
        m, n = len(grid), len(grid[0])
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 2:
                    q.append((i, j))
                if grid[i][j] == 1:
                    count += 1

        def get_value(x, y):
            if x >= m or y >= n or x < 0 or y < 0:
                return math.inf
            return grid[x][y]

        time = 0
        while q:
            temp = deque([])
            while q:
                x, y = q.popleft()
                dirs = [0, 1, 0, -1, 0]
                for i in range(4):
                    nx, ny = x + dirs[i], y + dirs[i + 1]
                    if get_value(nx, ny) == 1:
                        grid[nx][ny] = 2
                        temp.append((nx, ny))
                        count -= 1
            # print(temp)
            q = temp
            if q:
                time += 1

        if count == 0: return time
        return -1