LeetCode 55, 200, 323

💡 Data Structure and Algorithm Practice

55. Jump Game

Possible Algorithms

• Greedy
• Backtracking

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        # Greedy
        goal = len(nums) - 1

        for i in range(len(nums) - 1, -1, -1):
            # We can reach the goal if current_index + max_jump >= goal_index
            if i + nums[i] >= goal:
                # change our goal to the current_index
                goal = i
        
        return True if goal == 0 else False

200. Number of Islands

Possible Algorithms

• BFS
• DFS
• Union Find

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        # BFS
        # Seen grid
        # Increase the number of island at the base case
        
        ROWS = len(grid)
        COLS = len(grid[0])
        seen = [[0 for _ in range(COLS)] for _ in range(ROWS)]
        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        count = 0
        
        def BFS(row, col):
            q = collections.deque()
            if grid[row][col] == "1":
                q.append((row, col))
                seen[row][col] = 1
            
                while q:
                    cur_row, cur_col = q.popleft()
                    for x, y in directions:
                        new_row, new_col = cur_row + x, cur_col + y
                        if 0 <= new_row < ROWS and 0 <= new_col < COLS:
                            if seen[new_row][new_col] == 1:
                                continue
                            else:
                                seen[new_row][new_col] = 1
                                if grid[new_row][new_col] == "1":
                                    q.append((new_row, new_col))
        
        for i in range(ROWS):
            for j in range(COLS):
                if grid[i][j] == "1" and seen[i][j] == 0:
                    BFS(i, j)
                    count += 1
        
        return count

323. Number of Connected Components in an Undirected Graph

Possible Algorithms

• Union Find
• DFS

class Solution:
    def countComponents(self, n: int, edges: List[List[int]]) -> int:
        par = [i for i in range(n)]
        rank = [1] * n
        
        def find(n1):
            res = n1
            
            while res != par[res]:
                par[res] = par[par[res]]    # make the linked list a bit shorter: parent = grand parent
                res = par[res]
            return res
        
        def union(n1, n2):
            p1, p2 = find(n1), find(n2)
            
            # if they are already connected
            if p1 == p2:
                return 0    # union did nothing
            
            if rank[p2] > rank[p1]:
                par[p1] = p2
                rank[p2] += rank[p1]
            else:
                par[p2] = p1
                rank[p1] += rank[p2]
                
            return 1        # union was performed
        
        res = n
        for n1, n2 in edges:
            res -= union(n1, n2)
        
        return res