UNIST, CSE 3th

3 minute read

310. Minimum Height Trees (medium)

Failed

class Solution:
    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
        tree = defaultdict(list)
        for a, b in edges:
            tree[a].append(b)
            tree[b].append(a)
        
        def height(root):
            res = 0
            visited = [False] * n
            visited[root] = True
            q = deque([root])
            while q:

                temp = deque([])
                
                while q:
                    cur = q.popleft()
                    visited[cur] = True
                    for node in tree[cur]:
                        if not visited[node]:
                            temp.append(node)
                
                q = temp
                res += 1
            
            return res

        ans = [-1] * n
        for i in range(n):
            ans[i] = height(i)

        temp = []
        minv = min(ans)
        for i in range(n):
            if ans[i] == minv:
                temp.append(i)
        return temp

Successed with updating leaf nodes

class Solution:
  def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
    # Edge case: n=1, return [0]
    if n == 1:
        return [0]
    
    # Build adjacency list for the graph
    adj_list = {i: set() for i in range(n)}
    for u, v in edges:
        adj_list[u].add(v)
        adj_list[v].add(u)
    
    # Find all leaf nodes (i.e., nodes with degree 1)
    leaves = [i for i in range(n) if len(adj_list[i]) == 1]
    
    # Repeat until we are left with 1 or 2 nodes
    while n > 2:
        
        # Remove the current leaf nodes along with their edges
        n -= len(leaves)
        new_leaves = []
        for leaf in leaves:
            neighbor = adj_list[leaf].pop()
            adj_list[neighbor].remove(leaf)
            
            # If the neighbor becomes a new leaf node, add it to the list
            if len(adj_list[neighbor]) == 1:
                new_leaves.append(neighbor)
        
        # Update the list of leaf nodes
        leaves = new_leaves
    
    # The remaining nodes are the roots of the MHTs
    return leaves

1472. Design Browser History (medium)

class BrowserHistory:

    def __init__(self, homepage: str):
        self.index = 0
        self.his = [homepage]

    def visit(self, url: str) -> None:
        self.his = self.his[:self.index + 1]
        self.index += 1
        self.his.append(url)
        # print(self.his)

    def back(self, steps: int) -> str:
        self.index -= steps
        if self.index < 0:
            self.index = 0
        # print('back', self.his[self.index])
        return self.his[self.index]

    def forward(self, steps: int) -> str:
        self.index += steps
        if self.index >= len(self.his):
            self.index = len(self.his) - 1
        # print('forward', self.his[self.index])
        return self.his[self.index]

        


# Your BrowserHistory object will be instantiated and called as such:
# obj = BrowserHistory(homepage)
# obj.visit(url)
# param_2 = obj.back(steps)
# param_3 = obj.forward(steps)

312. Burst Balloons (hard) - Failed

DFS Approach

class Solution:
    def maxCoins(self, nums: List[int]) -> int:
        n = len(nums)
        def check_boundary(arr, index):
            return index >= 0 and index < len(arr)

        def coins(arr, index):
            if not check_boundary(arr, index):
                return -1
            res = arr[index]
            if check_boundary(arr, index - 1):
                res *= arr[index - 1]
            if check_boundary(arr, index + 1):
                res *= arr[index + 1]
            return res

        res = 0
        def dfs(arr, cur):
            if len(arr) == 0:
                nonlocal res
                # print(res)
                res = max(res, cur)
                return
            for i in range(len(arr)):
                new_arr = arr[:i] + arr[i + 1:]
                coin = coins(arr, i)
                if coin < 0:
                    continue
                dfs(new_arr, cur + coin)
            
        dfs(nums, 0)
        return res

DP Approach

class Solution:
    def maxCoins(self, nums: List[int]) -> int:
        # Add padding to the input array
        nums = [1] + nums + [1]
        n = len(nums)
        # Initialize a dp table to store the maximum coins for subproblems
        dp = [[0] * n for _ in range(n)]
        
        # Iterate the input array in reverse order to fill the dp table
        for i in range(n-2, -1, -1):
            for j in range(i+2, n):
                # Iterate k from i+1 to j-1 to find the last balloon to burst
                for k in range(i+1, j):
                    # Compute the maximum coins for subproblems
                    dp[i][j] = max(dp[i][j], nums[i]*nums[k]*nums[j] + dp[i][k] + dp[k][j])
        
        # The result is the maximum coins for the original problem
        return dp[0][n-1]

313. Super Ugly Number (medium)

class Solution:
    def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int:
        # create a list to store the super ugly numbers, initialize with 1
        super_ugly = [1]
        # create a list to store the indices for each prime number
        idx = [0] * len(primes)
        # create a list to store the product of prime numbers with their corresponding indices
        # this will be used to find the next super ugly number
        prod = [p for p in primes]
        
        # loop until we find the nth super ugly number
        while len(super_ugly) < n:
            # find the minimum value in prod, which will be the next super ugly number
            next_ugly = min(prod)
            # append it to the list of super ugly numbers
            super_ugly.append(next_ugly)
            
            # update the index for each prime number whose product is equal to next_ugly
            for i in range(len(primes)):
                if next_ugly == prod[i]:
                    idx[i] += 1
                    prod[i] = primes[i] * super_ugly[idx[i]]
        
        # return the last element in the list of super ugly numbers, which is the nth super ugly number
        return super_ugly[-1]

You may also enjoy