Practice #024: Leetcode Biweekly Contest 83

Leetcode 2347. Best Poker Hand

Problem Statement 

from typing import List


class Solution:
    def bestHand(self, ranks: List[int], suits: List[str]) -> str:
        cr = {}
        cs = {}
        for r in ranks:
            cr.setdefault(r, 0)
            cr[r] += 1
        for s in suits:
            cs.setdefault(s, 0)
            cs[s] += 1

        if len(cs) == 1:
            return "Flush"

        if 3 in cr.values() or 4 in cr.values():
            return "Three of a Kind"

        if 2 in cr.values():
            return "Pair"

        return "High Card"


assert Solution().bestHand([13, 2, 3, 1, 9], ["a", "a", "a", "a", "a"]) == "Flush"
assert (
    Solution().bestHand([4, 4, 2, 4, 4], ["d", "a", "a", "b", "c"]) == "Three of a Kind"
)
assert Solution().bestHand([10, 10, 2, 12, 9], ["a", "b", "c", "a", "d"]) == "Pair"

Leetcode 2348. Number of Zero-Filled Subarrays

Problem statement

  • Can we use brute-force to solve the problem? While iterating over the array, keep the size of the zero-subarray ending on the current position. Increment the array if you find a new zero and add the current size to the answer. This works because you are increasing the number of previous subarrays in 1. Time complexity is \(O(n)\) and space is \(O(1)\).
from typing import List


class Solution:
    def zeroFilledSubarray(self, nums: List[int]) -> int:
        ans = 0
        cnt = 0
        for n in nums:
            if n != 0:
                cnt = 0
            else:
                cnt += 1
                ans += cnt
        return ans


assert Solution().zeroFilledSubarray([1, 3, 0, 0, 2, 0, 0, 4]) == 6
assert Solution().zeroFilledSubarray([0, 0, 0, 2, 0, 0]) == 9
assert Solution().zeroFilledSubarray([2, 10, 2019]) == 0

Leetcode 2349. Design a Number Container System

Problem Statement 

from sortedcontainers import SortedList


class NumberContainers:
    def __init__(self):
        self.indexes = {}
        self.values = {}

    def change(self, index: int, number: int) -> None:
        cur = self.values.get(index, None)
        if cur is not None:
            self.indexes[cur].remove(index)

        self.indexes.setdefault(number, SortedList())
        self.indexes[number].add(index)
        self.values[index] = number

    def find(self, number: int) -> int:
        if number not in self.indexes or len(self.indexes[number]) == 0:
            return -1
        return self.indexes[number][0]


# Your NumberContainers object will be instantiated and called as such:
# obj = NumberContainers()
# obj.change(index,number)
# param_2 = obj.find(number)

Leetcode 2350. Shortest Impossible Sequence of Rolls

Problem Statement

  • Mistake: Missing required invariants. I could have solved the problem if I asked myself "What property does a sequence of size 1, 2, .. have to satisfy?"
  • How can we extend the solution for \(i\) to \(i+1\)? To have a sequence of size one, we have to find all number in the array. Be i the smallest index where \(1,2,..,k\) was found in \(a[0...(i-1)]\). We will only be able to build all sequences of size two, if we see \(1,2,..,k\) in \(a[i...(n-1)]\). The problem becomes counting the number of times that the groups of \(1,2,...,k\) appear in the input. Time complexity is \(O(n)\) and space is \(O(k)\).
from typing import List


class Solution:
    def shortestSequence(self, rolls: List[int], k: int) -> int:
        cur = set()
        cnt = 0
        for i, r in enumerate(rolls):
            cur.add(r)
            if len(cur) == k:
                cur = set()
                cnt += 1
        return cnt + 1


assert Solution().shortestSequence([4, 2, 1, 2, 3, 3, 2, 4, 1], 4) == 3
assert Solution().shortestSequence([1, 1, 2, 2], 2) == 2
assert Solution().shortestSequence([1, 1, 3, 2, 2, 2, 3, 3], 4) == 1