Practice #030: Leetcode Weekly Contest 308

Leetcode: 2389. Longest Subsequence With Limited Sum

Category: Binary Search

from typing import List
from itertools import accumulate
from bisect import bisect_right


class Solution:
    def answerQueries(self, nums: List[int], queries: List[int]) -> List[int]:
        nums.sort()
        p = list(accumulate(nums))
        return [bisect_right(p, q) for q in queries]


assert Solution().answerQueries([4, 5, 2, 1], [3, 10, 21]) == [2, 3, 4]
assert Solution().answerQueries([2, 3, 4, 5], [1]) == [0]

Leetcode: 2390. Removing Stars From a String

Problem Statement

Category: Stack

class Solution:
    def removeStars(self, s: str) -> str:
        st = []
        for c in s:
            if c == "*":
                st.pop()
            else:
                st.append(c)
        return "".join(st)


assert Solution().removeStars("leet**cod*e") == "lecoe"
assert Solution().removeStars("erase*****") == ""

Leetcode: 2391. Minimum Amount of Time to Collect Garbage

Problem Statement

from typing import List
from itertools import accumulate
from collections import defaultdict


class Solution:
    def garbageCollection(self, garbage: List[str], travel: List[int]) -> int:
        ans = 0
        d = defaultdict(int)
        p = list(accumulate([0] + travel))
        for j, g in enumerate(garbage):
            ans += len(g)
            for i in g:
                d[i] = max(d[i], j)
        ans += sum(p[i] for i in d.values())
        return ans


assert Solution().garbageCollection(["G", "P", "GP", "GG"], [2, 4, 3]) == 21
assert Solution().garbageCollection(["MMM", "PGM", "GP"], [3, 10]) == 37

Leetcode: 2392. Build a Matrix With Conditions

Problem Statement

Is there an alternative problem easier to solve? Build two graphs for rows and columns conditions where each condition is an edge between two numbers from \(1\) to \(k\). The problem becomes finding the Topological Sort of these two graphs and filled the final matrix with it. Time and space complexity are \(O(n)\).

from typing import List


class Solution:
    def topological_sort(self, graph):
        NOT_VISITED = 1
        OPEN = 2
        CLOSED = 4

        status = {u: NOT_VISITED for u in graph}
        ans = []

        def dfs(u):
            if status[u] == CLOSED:
                return True
            if status[u] == OPEN:
                return False

            status[u] = OPEN
            for v in graph[u]:
                if not dfs(v):
                    return False

            ans.append(u)
            status[u] = CLOSED
            return True

        for c in status:
            if status[c] == NOT_VISITED:
                if not dfs(c):
                    return False

        ans.reverse()
        return ans

    def buildMatrix(
        self, k: int, rowConditions: List[List[int]], colConditions: List[List[int]]
    ) -> List[List[int]]:
        def build_graph(edges):
            A = {i: [] for i in range(1, k + 1)}
            for u, v in edges:
                A[u].append(v)
            return A

        r = self.topological_sort(build_graph(rowConditions))
        c = self.topological_sort(build_graph(colConditions))
        if not r or not c:
            return []

        ans = [[0] * k for _ in range(k)]
        for e in range(1, k + 1):
            if e in r and e in c:
                ans[r.index(e)][c.index(e)] = e
        return ans


assert Solution().buildMatrix(3, [[1, 2], [3, 2]], [[2, 1], [3, 2]]) == [
    [3, 0, 0],
    [0, 0, 1],
    [0, 2, 0],
]
assert Solution().buildMatrix(3, [[1, 2], [2, 3], [3, 1], [2, 3]], [[2, 1]]) == []