ryuji0123

class Solution:
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
        def find(i):
            if parent[i] != i:
                parent[i] = find(parent[i])
            return parent[i]

        def union(x, y):
            px, py = find(x), find(y)
            if px == py:

ryuji0123

from collections import deque

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        def appendNextIsland(x, y):
            for i, j in [(x + 1, y), (x, y + 1), (x - 1, y), (x, y - 1)]:
                    if not (0 <= i < X and 0 <= j < Y) or grid[i][j] == 0 or not available[i][j]: continue
                    stack.append([i, j])
                    available[i][j] = False
                    self.area += 1

ryuji0123

from collections import deque

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        def appendNextCoordinate(x, y, rest_word, used):
            for i, j in [(x + 1, y), (x, y + 1), (x - 1, y), (x, y - 1)]:
                    if not (0 <= i < X and 0 <= j < Y) or board[i][j] != rest_word[0] or (i, j) in used: continue
                    stack.append([(i, j), rest_word[1:], used + [(i, j)]])
        
        try:

ryuji0123

from collections import deque

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        def appendNextIsland(x, y):
            for i, j in [(x + 1, y), (x, y + 1), (x - 1, y), (x, y - 1)]:
                    if not (0 <= i < X and 0 <= j < Y) or grid[i][j] == '0' or not available[i][j]: continue
                    stack.append([i, j])
                    available[i][j] = False
        

ryuji0123

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        try:
            X, Y = len(matrix), len(matrix[0])
        except:
            return 0
        dp = [[0 for _ in range(Y)] for _ in range(X)]
        ret = 0
        for x in range(X):
            for y in range(Y):

ryuji0123

class Solution:
    def nthUglyNumber(self, n: int) -> int:
        uref = [2, 3, 5]
        pointers = [0, 0, 0]
        dp = [1]
        for _ in range(1, n):
            next_dp = min(dp[pointers[idx]] * un for idx, un in enumerate(uref))
            dp.append(next_dp)
            for idx, un in enumerate(uref):
                if next_dp == dp[pointers[idx]] * un: pointers[idx] += 1

ryuji0123

class Solution:
    def numSquares(self, N: int) -> int:
        nums = []
        i = 1
        while i ** 2 <= N:
            nums.append(i ** 2)
            i += 1
        
        dp = [0] + [float('inf')] * N
        

ryuji0123

from bisect import bisect_left

class Solution:
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        if matrix == []: return False

ryuji0123

from bisect import bisect_left
import numpy as np

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        mat = np.array(matrix)
        try:
            i = bisect_left(mat[:, -1], target)
            return mat[i][bisect_left(mat[i, :], target)] == target
        except:

ryuji0123

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        dp = [[] for _ in range(target + 1)]
        
        for t in range(1, target + 1):
            for c in candidates:
                if t < c: continue
                if t == c:
                    dp[t].append([c])
                    continue