23.04.13 Today’s Leetcode

946. Validate Stack Sequences (medium)

class Solution:
    def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
        i = j = 0
        n = len(pushed)
        stack = []
        while i < n and j < n:
            stack.append(pushed[i])
            i += 1
            while stack and stack[-1] == popped[j]:
                stack.pop()
                j += 1
            
        return len(stack) == 0

1653. Minimum Deletions to Make String Balanced (medium)

class Solution:
    def minimumDeletions(self, s: str) -> int:
        temp = 0
        n = len(s)
        a, b = [0] * n, [0] * n
        for i in range(n):
            if s[i] == 'b':
                temp += 1
            a[i] = temp
        
        temp = 0
        for i in range(n - 1, -1, -1):
            if s[i] == 'a':
                temp += 1
            b[i] = temp
        
        res = 10**9
        for i in range(n):
            res = min(res, a[i] + b[i])
        
        return res - 1

2124. Check if All A’s Appears Before All B’s (easy)

class Solution:
    def checkString(self, s: str) -> bool:
        check = False
        for index, char in enumerate(s):
            if char == 'b':
                check = True
            if check and char == 'a':
                return False
        return True

2125. Number of Laser Beams in a Bank (medium)

class Solution:
    def numberOfBeams(self, bank: List[str]) -> int:
        def count(s):
            res = 0
            for c in s:
                if c == '1':
                    res += 1
            return res

        arr = []
        for b in bank:
            p = count(b)
            if p > 0:
                arr.append(p)

        n = len(arr)
        res = 0
        for i in range(n - 1):
            res += arr[i] * arr[i + 1]
        return res

406. Queue Reconstruction by Height (medium)

class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        # sort the people from tall to short
        # insert from tall to short (insert at index = p[1])
        people.sort(key=lambda p: (-p[0], p[1]))
        print(people)
        res = []
        for p in people:
            res.insert(p[1], p)
        return res