deque-blog

def trap(heights: List[int]) -> int:
    right_heights = list(heights)
    for i in reversed(range(len(right_heights)-1)):
        right_heights[i] = max(right_heights[i], right_heights[i+1])

    left_h = 0
    total_volume = 0
    for i in range(1, len(heights)-1):
        h = heights[i]
        left_h = max(heights[i-1], left_h)

deque-blog

def trap(heights: List[int]) -> int:
    left_h = 0
    total_volume = 0
    for i in range(1, len(heights)-1):
        h = heights[i]
        left_h = max(heights[i-1], left_h)
        right_h = max(heights[i+1:], default=0)
        volume = max(0, min(left_h, right_h) - h)
        total_volume += volume
    return total_volume

deque-blog

def trap(heights: List[int]) -> int:
    total_volume = 0
    for i, h in enumerate(heights):
        left_h = max(heights[:i], default=0)
        right_h = max(heights[i+1:], default=0)
        volume = max(0, min(left_h, right_h) - h)
        total_volume += volume
    return total_volume

deque-blog

def maxSubArray(nums: List[int]) -> int:
    max_sum = float('-inf')
    cum_sum = 0
    for num in nums:
        cum_sum += num
        if cum_sum >= max_sum:
            max_sum = cum_sum
        if cum_sum <= 0:
            cum_sum = 0
    return max_sum

deque-blog

def maxSubArray(nums: List[int]) -> int:
    max_sum = float('-inf')
    for i in range(len(nums)):
        cum_sum = 0
        for j in range(i, len(nums)):
            cum_sum += nums[j]
            if cum_sum > max_sum:
                max_sum = cum_sum
    return max_sum

deque-blog

def wordBreak(self, s: str, wordDict: List[str]) -> bool:
    if not wordDict:
        return False

    word_dict = set(wordDict)
    smallest_word = min(len(w) for w in wordDict)
    longest_word = max(len(w) for w in wordDict)

    @lru_cache(maxsize=None)
    def can_break_from(i: int) -> bool:

deque-blog

def expand_selection(self, states: Set[int]):
    expanded = set()
    to_expand = list(states)
    while to_expand:
        s = to_expand.pop()
        expanded.add(s)
        if s < len(self.nodes)  and self.stars[s]:
            if s+1 not in expanded:
                states.add(s+1)
                to_expand.append(s+1)

deque-blog

def match(self, s: str) -> bool:
    current_nodes = { 0 }
    self.expand_selection(current_nodes)
    for c in s:
        next_nodes = set()
        for s in current_nodes:
            if s < len(self.nodes):
                if self.nodes[s] == c or self.nodes[s] == '.':
                    next_nodes.add(s+1)
                    if self.stars[s]:

deque-blog

@classmethod
def compile(cls, pattern: str):
    nodes = []
    stars = []
    for c in pattern:
        if c == "*":
            stars[-1] = True
        else:
            nodes.append(c)
            stars.append(False)

deque-blog

@dataclass(frozen=True)
class Regex:
    nodes: List[str]
    stars: List[bool]