6 posts tagged with "Matrix"

class Solution:
    def searchMatrix(self, matrix: list[list[int]], target: int) -> bool:
        M, N = len(matrix), len(matrix[0])
        lo, hi = 0, M * N
        while lo < hi:
            mid = (lo + hi) // 2
            row, col = divmod(mid, N)
            if matrix[row][col] == target:
                return True
            if matrix[row][col] > target:
                hi = mid
            else:
                lo = mid + 1
        return False


class Solution1:
    def searchMatrix(self, matrix: list[list[int]], target: int) -> bool:
        M, N = len(matrix), len(matrix[0])
        lo, hi = 0, M
        while lo < hi:
            mid = (lo + hi) // 2
            if matrix[mid][0] == target:
                return True
            if matrix[mid][0] > target:
                hi = mid
            else:
                lo = mid + 1
        row = matrix[lo - 1]
        lo, hi = 0, N
        while lo < hi:
            mid = (lo + hi) // 2
            if row[mid] == target:
                return True
            if row[mid] > target:
                hi = mid
            else:
                lo = mid + 1
        return False

from collections import deque
from heapq import heappop, heappush
from itertools import product
from sys import maxsize

cellT = tuple[int, int]
countT = int


class Solution1:
    # [BFS] Runtime 1349 ms Beats 5.1%
    def shortestPathBinaryMatrix(self, grid: list[list[int]]):
        cellsT = set[cellT]

        N = len(grid)
        dummy_start_cell = (-1, -1)
        bottom_right_cell = (N - 1, N - 1)

        def find_adjacents(curr_row: int, curr_col: int):
            def is_valid(cand_cell: cellT):
                cand_row, cand_col = cand_cell
                return (
                    0 <= cand_row < N
                    and 0 <= cand_col < N
                    and grid[cand_row][cand_col] == 0
                )

            cand_cells = (
                (curr_row + row_offset, curr_col + col_offset)
                for row_offset, col_offset in product(range(-1, 2), repeat=2)
            )
            return filter(is_valid, cand_cells)

        queue: deque[cellsT] = deque([{dummy_start_cell}])
        visiteds: cellsT = set()
        count: countT = 1
        while queue:
            next_: cellsT = set()
            q: cellsT = queue.popleft()
            for cell in q:
                visiteds.add(cell)
                for adjacent in find_adjacents(*cell):
                    if adjacent in visiteds:
                        continue
                    if adjacent == bottom_right_cell:
                        return count
                    next_.add(adjacent)
            if next_:
                queue.append(next_)
            count += 1
        return -1


class Solution2:
    # [dijkstra] Runtime 995 ms Beats 6.89%
    def shortestPathBinaryMatrix(self, grid: list[list[int]]):
        N = len(grid)
        dummy_start_cell = (-1, -1)
        bottom_right_cell = (N - 1, N - 1)

        def find_adjacents(curr_row: int, curr_col: int):
            def is_valid(cand_cell: cellT):
                cand_row, cand_col = cand_cell
                return (
                    0 <= cand_row < N
                    and 0 <= cand_col < N
                    and grid[cand_row][cand_col] == 0
                )

            cand_cells = (
                (curr_row + row_offset, curr_col + col_offset)
                for row_offset, col_offset in product(range(-1, 2), repeat=2)
            )
            return filter(is_valid, cand_cells)

        heap: list[tuple[countT, cellT]] = [(0, dummy_start_cell)]
        visiteds: set[cellT] = set()
        while heap:
            cost, vertex = heappop(heap)
            if vertex == bottom_right_cell:
                return cost
            for new_vertex in find_adjacents(*vertex):
                if new_vertex in visiteds:
                    continue
                visiteds.add(new_vertex)
                new_cost = cost + 1
                heappush(heap, (new_cost, new_vertex))
        return -1


class Solution3:
    # [A*] Runtime 513 ms Beats 97.17%
    def shortestPathBinaryMatrix(self, grid: list[list[int]]):
        N = len(grid)
        dummy_start_cell = (-1, -1)
        bottom_right_cell = (N - 1, N - 1)

        def find_adjacents(curr_row: int, curr_col: int):
            def is_valid(cand_cell: cellT):
                cand_row, cand_col = cand_cell
                return (
                    0 <= cand_row < N
                    and 0 <= cand_col < N
                    and grid[cand_row][cand_col] == 0
                )

            cand_cells = (
                (curr_row + row_offset, curr_col + col_offset)
                for row_offset, col_offset in product(range(-1, 2), repeat=2)
            )
            return filter(is_valid, cand_cells)

        def heuristic(cell_row: int, cell_col: int):
            return max(abs(N - 1 - cell_row), abs(N - cell_col))

        heap: list[tuple[countT, countT, cellT]] = [(-maxsize, 0, dummy_start_cell)]
        costs: dict[cellT, countT] = {}
        while heap:
            estimate, cost, vertex = heappop(heap)
            if vertex == bottom_right_cell:
                return cost
            for new_vertex in find_adjacents(*vertex):
                new_cost = cost + 1
                if costs.get(new_vertex, maxsize) > new_cost:
                    costs[new_vertex] = new_cost
                    new_estimate = new_cost + heuristic(*new_vertex)
                    heappush(heap, (new_estimate, new_cost, new_vertex))
        return -1

class Solution:
    def spiralOrder(self, matrix: list[list[int]]) -> list[int]:
        if not matrix or not matrix[0]:
            return []
        result = []
        t, b, l, r = 0, len(matrix) - 1, 0, len(matrix[0]) - 1
        while t <= b and l <= r:
            result.extend([matrix[t][x] for x in range(l, r + 1)])
            result.extend([matrix[x][r] for x in range(t + 1, b + 1)])
            if t < b and l < r:
                result.extend([matrix[b][x] for x in range(r - 1, l, -1)])
                result.extend([matrix[x][l] for x in range(b, t, -1)])
            t, b, l, r = t + 1, b - 1, l + 1, r - 1
        return result

class Solution:
    def findBall(self, grid: list[list[int]]) -> list[int]:
        N = len(grid[0])

        def drop(pos: int) -> int:
            for row in grid:
                adj = pos + row[pos]
                if not 0 <= adj < N:
                    return -1
                if row[pos] != row[adj]:
                    return -1
                pos = adj
            return pos

        return [drop(x) for x in range(N)]

class Solution:
    def numIslands(self, grid) -> int:
        M, N = len(grid), len(grid[0])

        def dfs(m, n):
            r = 0 <= m < M and 0 <= n < N and grid[m][n] == '1'
            if r:
                grid[m][n] = None
                list(map(dfs, (m + 1, m - 1, m, m), (n, n, n + 1, n - 1)))
            return r

        return sum(dfs(m, n) for m in range(M) for n in range(N))

class Solution:
    def floodFill(
        self, image: list[list[int]], sr: int, sc: int, color: int
    ) -> list[list[int]]:
        COLOR, M, N = image[sr][sc], len(image), len(image[0])

        def dfs(m, n):
            if not all([0 <= m < M, 0 <= n < N]):
                return

            if not all([image[m][n] == COLOR, image[m][n] != color]):
                return

            image[m][n] = color
            list(map(dfs, (m + 1, m - 1, m, m), (n, n, n + 1, n - 1)))

        dfs(sr, sc)
        return image