A. Count Common Words With One Occurrence (opens new window)

Count the number of character that is unique in both words.

DETAILS

def countWords(self, w1: List[str], w2: List[str]) -> int:
        c1, c2 = collections.Counter(w1), collections.Counter(w2)
        ans = 0
        for w in c1:
            if c1[w] == 1 and c2[w] == 1:
                ans += 1
        return ans

B. Minimum Number of Buckets Required to Collect Rainwater from Houses (opens new window)

• If 3 or more consecutive houses, fail.
• Adjancent houses need 2 buckets.
• Assign the buckets to cover the rest houses.

DETAILS

def minimumBuckets(self, A: str) -> int:
        res = [(k, len(list(g))) for k, g in itertools.groupby(A)]
        for key, val in res:
            if key == "H" and val > 2:
                return -1
        if res[0][0] == "H" and res[0][1] > 1:
            return -1
        if res[-1][0] == "H" and res[-1][1] > 1:
            return -1
        if len(A) == 1 and A == "H":
            return -1
        tmp = list(A)
        ans = 0
        n = len(A)
        for i in range(1, n - 1):
            if tmp[i] == "." and tmp[i + 1] == "H" and tmp[i - 1] == "H":
                ans += 1
                tmp[i + 1] = "."
                tmp[i - 1] = "."
        c = collections.Counter(tmp)
        return ans + c["H"]

C. Minimum Cost Homecoming of a Robot in a Grid (opens new window)

DETAILS

def minCost(self, start: List[int], home: List[int], R: List[int], C: List[int]) -> int:
        m, n = len(R), len(C)
        ans = 0
        if start == home: return ans
        if start[0] != home[0]:
            r = R[min(start[0], home[0]): max(start[0], home[0]) + 1]
            ans += sum(r) - R[start[0]]
        if start[1] != home[1]:
            c = C[min(start[1], home[1]) : max(start[1], home[1]) + 1]
            ans += sum(c) - C[start[1]]
        return ans

D. Count Fertile Pyramids in a Land (opens new window)

DP

DETAILS

def countPyramids(self, A: List[List[int]]) -> int:
        def helper(A):
            m, n = len(A), len(A[0])
            lft, rgt = [[0] * n for _ in range(m)], [[0] * n for _ in range(m)]
            for i in range(m):
                curr = 0
                for j in range(n):
                    if A[i][j] == 1:
                        curr += 1
                    else:
                        curr = 0
                    lft[i][j] = curr
            for i in range(m):
                curr = 0
                for j in range(n - 1, -1, -1):
                    if A[i][j] == 1:
                        curr += 1
                    else:
                        curr = 0
                    rgt[i][j] = curr
            ans = 0
            max1 = [[0] * n for _ in range(m)]

            for i in range(n):
                if A[0][i] == 1:
                    maxk = min(i, n - 1 - i, m - 1)
                    curr = 0
                    for j in range(1, maxk + 1):
                        cx, cy = j, i
                        if lft[cx][cy] >= j + 1 and rgt[cx][cy] >= j + 1:
                            curr += 1
                        else:
                            break
                    max1[0][i] = curr
            for row in range(1, m):
                for col in range(1, n - 1):
                    if A[row][col] == 1:
                        maxk = min(col, n - 1 - col, m - 1 - row)
                        curr = max(0, max1[row - 1][col] - 1, max1[row - 1][col + 1] - 1, max1[row - 1][col - 1] - 1)
                        if maxk > curr:
                            for j in range(curr + 1, maxk + 1):
                                cy = row + j
                                if lft[cy][col] >= j + 1 and rgt[cy][col] >= j + 1:
                                    curr += 1
                                else:
                                    break
                        max1[row][col] = curr
            ans += sum(sum(x) for x in max1)
            return ans
        B = A[::-1]
        return helper(A) + helper(B)