22 posts tagged with "Easy"

class Solution:
    def numberOfEmployeesWhoMetTarget(self, hours: list[int], target: int) -> int:
        return sum(1 for x in hours if x >= target)

class Solution:
    def accountBalanceAfterPurchase(self, purchaseAmount: int) -> int:
        return 100 - (purchaseAmount + 5) // 10 * 10

class Solution:
    def finalString(self, s: str) -> str:
        buf = []
        for c in s:
            if c == 'i':
                buf = buf[::-1]
            else:
                buf.append(c)
        return ''.join(buf)

class Solution:
    def maxSum(self, nums: list[int]) -> int:
        ht: dict[int, list[int]] = {}
        result = -1
        for num in nums:
            tmp, max_digit = num, 0
            while tmp:
                tmp, max_digit = tmp // 10, max(max_digit, tmp % 10)
            ht[max_digit] = sorted(ht.get(max_digit, []) + [num])[-2:]
            if len(ht[max_digit]) == 2:
                result = max(result, sum(ht[max_digit]))
        return result

from collections import deque

vertexT = int


class Solution1:
    # [dfs] Runtime 2560 ms Beats 7.20%
    def validPath(
        self, n: int, edges: list[list[int]], source: int, destination: int
    ) -> bool:
        graph: dict[vertexT, list[vertexT]] = {}
        for vertex_1, vertex_2 in edges:
            graph.setdefault(vertex_1, []).append(vertex_2)
            graph.setdefault(vertex_2, []).append(vertex_1)

        visiteds: set[vertexT] = set()

        def dfs(vertex: vertexT):
            if vertex == destination:
                return True
            if vertex in visiteds:
                return False
            visiteds.add(vertex)
            return any(map(dfs, graph[vertex]))

        return dfs(source)


class Solution2:
    # [bfs] Runtime 1971 ms Beats 61.44%
    def validPath(
        self, n: int, edges: list[list[int]], source: int, destination: int
    ) -> bool:
        graph: dict[vertexT, set[vertexT]] = {}
        for vertex_1, vertex_2 in edges:
            graph.setdefault(vertex_1, set()).add(vertex_2)
            graph.setdefault(vertex_2, set()).add(vertex_1)

        visiteds: set[vertexT] = set()
        queue: deque[set[vertexT]] = deque([{source}])
        while queue:
            next_: set[vertexT] = set()
            q = queue.popleft()
            for vertex in q:
                if vertex == destination:
                    return True
                if vertex in visiteds:
                    continue
                visiteds.add(vertex)
                next_ |= graph[vertex]
            if next_:
                queue.append(next_)
        return False


class Uf3:
    def __init__(self, root: dict[vertexT, vertexT]):
        self.root = root

    def find(self, x: vertexT):
        if x not in self.root:
            self.root[x] = x
        if self.root[x] != x:
            self.root[x] = self.find(self.root[x])
        return self.root[x]

    def union(self, x: vertexT, y: vertexT):
        x_root, y_root = self.find(x), self.find(y)
        self.root[x_root] = y_root


class Solution3:
    # [uf]
    def validPath(
        self, n: int, edges: list[list[int]], source: int, destination: int
    ) -> bool:
        uf = Uf3({})
        for x, y in edges:
            uf.union(x, y)
        return uf.find(source) == uf.find(destination)


class Uf4:
    def __init__(self, root: dict[vertexT, vertexT]):
        self.root = root

    def find(self, x: vertexT):
        # [iteratively]
        if x not in self.root:
            self.root[x] = x
        while self.root[x] != x:
            self.root[x] = self.root[self.root[x]]
            x = self.root[x]
        return self.root[x]

    def union(self, x: vertexT, y: vertexT):
        x_root, y_root = self.find(x), self.find(y)
        self.root[x_root] = y_root


class Solution4:
    def validPath(
        self, n: int, edges: list[list[int]], source: int, destination: int
    ) -> bool:
        uf = Uf4({})
        for x, y in edges:
            uf.union(x, y)
        return uf.find(source) == uf.find(destination)


class Uf5:
    def __init__(self, root: dict[vertexT, vertexT]):
        self.root = root

    def find(self, x: vertexT):
        # dict.setdefault
        if self.root.setdefault(x, x) != x:
            self.root[x] = self.find(self.root[x])
        return self.root[x]

    def union(self, x: vertexT, y: vertexT):
        x_root, y_root = self.find(x), self.find(y)
        self.root[x_root] = y_root


class Solution5:
    def validPath(
        self, n: int, edges: list[list[int]], source: int, destination: int
    ) -> bool:
        uf = Uf5({})
        for x, y in edges:
            uf.union(x, y)
        return uf.find(source) == uf.find(destination)


class Uf6:
    DUMMY_VERTEX = -1

    def __init__(self, root: list[vertexT]):
        # use `list`
        self.root = root

    def find(self, x: vertexT):
        if self.root[x] is self.DUMMY_VERTEX:
            self.root[x] = x
        if self.root[x] != x:
            self.root[x] = self.find(self.root[x])
        return self.root[x]

    def union(self, x: vertexT, y: vertexT):
        x_root, y_root = self.find(x), self.find(y)
        self.root[x_root] = y_root


class Solution6:
    def validPath(
        self, n: int, edges: list[list[int]], source: int, destination: int
    ) -> bool:
        uf = Uf6(list(range(n)))
        for x, y in edges:
            uf.union(x, y)
        return uf.find(source) == uf.find(destination)


class Uf7:
    def __init__(self, root: list[vertexT]):
        self.root = root

    def find(self, x: vertexT):
        # without dummy (run union)
        if self.root[x] != x:
            self.root[x] = self.find(self.root[x])
        return self.root[x]

    def union(self, x: vertexT, y: vertexT):
        x_root, y_root = self.find(x), self.find(y)
        self.root[x_root] = y_root


class Solution7:
    def validPath(
        self, n: int, edges: list[list[int]], source: int, destination: int
    ) -> bool:
        uf = Uf7(list(range(n)))
        for x, y in edges:
            uf.union(x, y)
        return uf.find(source) == uf.find(destination)

class Solution:
    def arraySign(self, nums: list[int]) -> int:
        sig = True
        for num in nums:
            if num == 0:
                return 0
            if num < 0:
                sig = not sig
        return int(sig or -1)

class Solution:
    def isValid(self, s: str) -> bool:
        P = {
            '(': ')',
            '{': '}',
            '[': ']',
        }
        stack = []
        for c in s:
            if stack and P.get(stack[-1]) == c:
                stack.pop()
            else:
                stack.append(c)
        return not stack

class Solution:
    def mergeAlternately(self, w1: str, w2: str) -> str:
        L1, L2 = len(w1), len(w2)
        result = []
        for i in range(max(L1, L2)):
            if i < L1:
                result.append(w1[i])
            if i < L2:
                result.append(w2[i])
        return ''.join(result)

class Solution:
    def isHappy(self, n: int) -> bool:
        visiteds = set()
        while n not in visiteds:
            if n == 1:
                return True
            visiteds.add(n)
            n = sum(int(x) ** 2 for x in str(n))
        return False

import heapq


class Solution:
    def lastStoneWeight(self, stones: list[int]) -> int:
        stones.append(0)
        stones = list(map(lambda x: -x, stones))
        heapq.heapify(stones)
        while len(stones) > 1:
            y, x = -heapq.heappop(stones), -heapq.heappop(stones)
            if x != y:
                heapq.heappush(stones, -(y - x))
        return -heapq.heappop(stones)

class Solution1:
    def backspaceCompare(self, s: str, t: str) -> bool:
        S = '#'
        ss, st = [], []
        for c in s:
            if c != S:
                ss.append(c)
            elif ss:
                ss.pop()
        for c in t:
            if c != S:
                st.append(c)
            elif st:
                st.pop()
        return ss == st


class Solution:
    def backspaceCompare(self, s: str, t: str) -> bool:
        def go_left(string, pointer, backspace):
            S = '#'
            while pointer >= 0 and (backspace or string[pointer] == S):
                backspace += (-1) ** (string[pointer] != S)
                pointer -= 1
            return pointer, backspace

        ps, pt = len(s) - 1, len(t) - 1  # pointer
        bs, bt = 0, 0  # backspace
        while True:
            (ps, bs), (pt, bt) = go_left(s, ps, bs), go_left(t, pt, bt)
            if not (ps >= 0 and pt >= 0 and s[ps] == t[pt]):
                return ps == pt == -1
            ps -= 1
            pt -= 1

class Solution:
    def climbStairs(self, n: int) -> int:
        a, b = 1, 1
        for _ in range(n):
            a, b = b, a + b
        return a

class Solution:
    def fib(self, n: int) -> int:
        a, b = 0, 1
        for _ in range(n):
            a, b = b, a + b
        return a

class Solution:
    def minCostClimbingStairs(self, cost: list[int]) -> int:
        a = b = 0
        for c in cost:
            a, b = b, min(a, b) + c
        return min(a, b)

# The guess API is already defined for you.
# @param num, your guess
# @return -1 if num is higher than the picked number
#          1 if num is lower than the picked number
#          otherwise return 0
def guess(num: int) -> int:
    ...


class Solution:
    def guessNumber(self, n: int) -> int:
        l, r = 0, n
        while l < r:
            m = (l + r) // 2
            if not guess(m):
                return m
            l, r = (l, m) if guess(m) < 0 else (m + 1, r)
        return l

class Solution:
    def floodFill(
        self, image: list[list[int]], sr: int, sc: int, color: int
    ) -> list[list[int]]:
        COLOR, M, N = image[sr][sc], len(image), len(image[0])

        def dfs(m, n):
            if not all([0 <= m < M, 0 <= n < N]):
                return

            if not all([image[m][n] == COLOR, image[m][n] != color]):
                return

            image[m][n] = color
            list(map(dfs, (m + 1, m - 1, m, m), (n, n, n + 1, n - 1)))

        dfs(sr, sc)
        return image

class Solution:
    def longestCommonPrefix(self, strs: list[str]) -> str:
        result = []
        for i, c in enumerate(strs[0]):
            if not all([i < len(s) and c == s[i] for s in strs]):
                break
            result.append(c)
        return ''.join(result)

class Solution1:
    def removeDuplicates(self, nums: list[int]) -> int:
        v, p = -101, 0  # ng
        for i in range(len(nums)):
            if nums[i] > v:
                v = nums[p] = nums[i]
                p += 1
        return p


class Solution:
    def removeDuplicates(self, nums: list[int]) -> int:
        p = 1
        for i in range(1, len(nums)):
            if nums[p - 1] < nums[i]:
                nums[p], p = nums[i], p + 1
        return p

class Solution:
    def search(self, nums: list[int], target: int) -> int:
        l, r = 0, len(nums)
        while l < r:
            m = (l + r) // 2
            if nums[m] == target:
                return m
            l, r = (l, m) if nums[m] > target else (m + 1, r)
        return -1

class Solution:
    def maxProfit(self, prices) -> int:
        result, buy = 0, prices[0]
        for p in prices:
            result, buy = max(result, p - buy), min(buy, p)
        return result

class Solution:
    def longestPalindrome(self, s: str) -> int:
        r, pool = 0, set()
        for c in s:
            if c in pool:
                pool.remove(c)
                r += 1
            else:
                pool.add(c)
        return r * 2 + bool(pool)

class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children


class Solution:
    def preorder(self, root):
        return (
            (root.val,) + sum((self.preorder(x) for x in root.children), ())
            if root
            else ()
        )