18 posts tagged with "list - Blind 75"

import heapq
from collections import Counter
from itertools import chain, islice


class Solution:  # O(n) / O(n)
    def topKFrequent(self, nums: list[int], k: int) -> list[int]:
        buckets = [[] for _ in nums]
        for n, c in Counter(nums).items():
            buckets[-c].append(n)
        return list(islice(chain.from_iterable(buckets), k))


class Solution1:  # O(nlogn) / O(n)
    def topKFrequent(self, nums: list[int], k: int) -> list[int]:
        heap = []
        for n, c in Counter(nums).items():
            heapq.heappush(heap, (-c, n))
        return [heapq.heappop(heap)[1] for _ in range(k)]


class Solution2:  # O(nlogn) / O(n)
    def topKFrequent(self, nums: list[int], k: int) -> list[int]:
        heap = []
        for n, c in Counter(nums).items():
            heapq.heappush(heap, (-c, n))
        return [x[1] for x in heapq.nsmallest(k, heap)]


class Solution3:  # O(nlogn) / O(n)
    def topKFrequent(self, nums: list[int], k: int) -> list[int]:
        return [n for n, _ in Counter(nums).most_common(k)]

class Solution:
    def groupAnagrams(self, strs: list[str]) -> list[list[str]]:
        ht: dict[str, list[str]] = {}
        for s in strs:
            key = ''.join(sorted((s)))
            ht[key] = ht.get(key, [])
            ht[key].append(s)
        return list(ht.values())

class SolutionR1:  # O(n*n) / O(n) ? str slice
    def numDecodings(self, s: str) -> int:
        m = {'': 1}

        def recur(s=s):
            if s in m:
                return m[s]
            m[s] = 0
            if s[0] != '0':
                m[s] += recur(s[1:])
            if 10 <= int(s[:2]) <= 26:
                m[s] += recur(s[2:])
            return m[s]

        return recur()


class SolutionR2:  # O(n) / O(n)
    def numDecodings(self, s: str) -> int:
        m = {len(s): 1}

        def recur(i=0):
            if i in m:
                return m[i]
            m[i] = 0
            if s[i] != '0':
                m[i] += recur(i + 1)
            if 10 <= int(s[i : i + 2]) <= 26:
                m[i] += recur(i + 2)
            return m[i]

        return recur()


class Solution1:  # O(n) / O(n)
    def numDecodings(self, s: str) -> int:
        dp = [0] * (len(s) + 1)
        dp[0], dp[1] = 1, int(s[0] != '0')
        for i in range(len(s) - 1):
            if s[i + 1] != '0':
                dp[i + 2] += dp[i + 1]
            if 10 <= int(s[i : i + 2]) <= 26:
                dp[i + 2] += dp[i]
        return dp[-1]


class Solution2:  # O(n) / O(1)
    def numDecodings(self, s: str) -> int:
        a, b = 1, int(s[0] != '0')
        for i in range(len(s) - 1):
            c = 0
            if s[i + 1] != '0':
                c += b
            if 10 <= int(s[i : i + 2]) <= 26:
                c += a
            a, b = b, c
        return b


class Solution3:  # O(n) / O(1)
    def numDecodings(self, s: str) -> int:
        a, b = 1, int(s[0] != '0')
        for i in range(len(s) - 1):
            one, two = s[i + 1] != '0', 10 <= int(s[i : i + 2]) <= 26
            a, b = b, b * one + a * two
        return b


class Solution4:  # O(n) / O(1)
    def numDecodings(self, s: str) -> int:
        a, b, p = 0, int(bool(s)), ''
        for c in s:
            tmp = b
            if c == '0':
                b = 0
            if 10 <= int(p + c) <= 26:
                b += a
            a, p = tmp, c
        return b


class Solution:  # O(n) / O(1)
    def numDecodings(self, s: str) -> int:
        a, b, p = 0, int(bool(s)), ''
        for c in s:
            one, two = c != '0', 10 <= int(p + c) <= 26
            a, b, p = b, b * one + a * two, c
        return b

class Solution:
    def rob(self, nums: list[int]) -> int:
        def _rob(start: int, stop: int):
            a, b = 0, 0
            for i in range(start, stop):
                a, b = b, max(a + nums[i], b)
            return b

        return max(_rob(0, len(nums) - 1), _rob(1, len(nums)))

class Solution:
    def rob(self, nums: list[int]) -> int:
        a, b = 0, 0
        for n in nums:
            a, b = b, max(a + n, b)
        return b

class Solution1:
    def lengthOfLongestSubstring(self, s: str) -> int:
        result, chars = 0, set()
        for j, c in enumerate(s):
            while c in chars:
                i = j - len(chars)
                chars.remove(s[i])
            chars.add(c)
            result = max(result, len(chars))
        return result


class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        result, i, chars = 0, 0, {}
        for j, char in enumerate(s):
            i = max(i, chars.get(char, -1) + 1)
            chars[char] = j
            result = max(result, j - i + 1)
        return result

from collections import Counter


class Solution:
    def minDeletions(self, s: str) -> int:
        result = 0
        used: set[int] = set()
        for c in Counter(s).values():
            while c and c in used:
                result += 1
                c -= 1
            used.add(c)
        return result

class Solution:
    def coinChange(self, coins: list[int], amount: int) -> int:
        dp = [0] + [0xFFFFFFFF] * (amount)
        for coin in coins:
            for i in range(coin, amount + 1):
                dp[i] = min(dp[i], dp[i - coin] + 1)
        return (dp[-1], -1)[dp[-1] == 0xFFFFFFFF]

class Solution1:
    def getSum(self, a: int, b: int) -> int:
        MASK, xor, carry = 1023, a ^ b, (a & b) << 1
        if carry & MASK:
            return self.getSum(xor, carry)
        return xor & MASK if carry else xor


class Solution:
    def getSum(self, a: int, b: int) -> int:
        MASK = 1023
        while b & MASK:
            a, b = a ^ b, (a & b) << 1
        return a & MASK if b else a

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        dp = [[0 for _ in range(len(text2) + 1)] for _ in range(len(text1) + 1)]
        for i in range(len(text1)):
            for j in range(len(text2)):
                if text1[i] == text2[j]:
                    dp[i + 1][j + 1] = dp[i][j] + 1
                else:
                    dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1])
        return dp[-1][-1]

class Solution:
    def maxArea(self, height: list[int]) -> int:
        result = 0
        l, r = 0, len(height) - 1
        while l != r:
            result = max(result, min(height[l], height[r]) * (r - l))
            if height[l] < height[r]:
                l += 1
            else:
                r -= 1
        return result

class Solution:
    def threeSum(self, nums: list[int]):
        result = set()
        zero, neg, pos = counters = {}, {}, {}
        for num in nums:
            counter = counters[(num > 0) + (num != 0)]
            counter[num] = counter.get(num, 0) + 1
        # 0,0,0
        if zero.get(0, 0) >= 3:
            result.add((0, 0, 0))
        # -,+,?
        for n in neg:
            for p in pos:
                target: int = -(n + p)
                counter = counters[(target > 0) + (target != 0)]
                if target in counter:
                    triplet = tuple(sorted([n, p, target]))
                    if target in (n, p):  # duplicate
                        if counter[target] >= 2:
                            result.add(triplet)
                    else:
                        result.add(triplet)
        return result

class Solution:
    def search(self, nums: list[int], target: int) -> int:
        lo, hi = 0, len(nums)
        target_is_rotated = target < nums[0]
        while lo < hi:
            mid = (lo + hi) // 2
            if nums[mid] == target:
                return mid
            mid_is_rotated = nums[mid] < nums[0]
            if (mid_is_rotated, target_is_rotated) == (True, False):  # [t] [m]
                hi = mid
            elif (mid_is_rotated, target_is_rotated) == (False, True):  # [m] [t]
                lo = mid + 1
            # same side
            elif nums[mid] > target:
                hi = mid
            else:
                lo = mid + 1
        return -1


class Solution1:
    def search(self, nums: list[int], target: int) -> int:
        # https://leetcode.com/problems/search-in-rotated-sorted-array/solutions/14435/clever-idea-making-it-simple/
        lo, hi = 0, len(nums)
        target_is_rotated = target < nums[0]
        inf = (-1) ** target_is_rotated * float('inf')
        while lo < hi:
            mid = (lo + hi) // 2
            if nums[mid] == target:
                return mid
            mid_is_rotated = nums[mid] < nums[0]
            if (nums[mid], inf)[mid_is_rotated != target_is_rotated] > target:
                hi = mid
            else:
                lo = mid + 1
        return -1

class Solution:
    def findMin(self, nums: list[int]) -> int:
        lo, hi = 0, len(nums)
        while lo < hi:
            mid = (lo + hi) // 2
            if nums[mid] <= nums[-1]:
                hi = mid
            else:
                lo = mid + 1
        return nums[lo]

class Solution:
    def maxSubArray(self, nums: list[int]) -> int:
        result = acc = nums[0]
        for i in range(1, len(nums)):
            acc = max(nums[i], nums[i] + acc)
            result = max(result, acc)
        return result

class Solution:
    def maxProduct(self, nums: list[int]) -> int:
        result = acc_max = acc_min = nums[0]
        for i in range(1, len(nums)):
            cand = nums[i], nums[i] * acc_max, nums[i] * acc_min
            acc_max, acc_min = max(cand), min(cand)
            result = max(result, acc_max, acc_min)
        return result

class Solution:
    def productExceptSelf(self, nums: list[int]) -> list[int]:
        result = [1] * len(nums)
        l = r = 1
        for i in range(len(nums)):
            result[i] *= l
            l *= nums[i]
            result[-1 - i] *= r
            r *= nums[-1 - i]
        return result

class Solution:  # O(n) / O(n)
    # https://leetcode.com/problems/longest-repeating-character-replacement/solutions/278271/C++Python-Sliding-Window-O(N)-instead-of-O(26N)/
    def characterReplacement(self, s: str, k: int) -> int:
        c = {}  # counter
        mf = 0  # max_freq
        i = 0
        for j, char in enumerate(s):
            c[char] = c.get(char, 0) + 1
            mf = max(mf, c[char])
            if not ((j - i + 1) - mf <= k):  # shift right
                c[s[i]] -= 1
                i += 1
        return len(s) - i  # length


class Solution2:  # O(n) / O(n)
    # https://leetcode.com/problems/longest-repeating-character-replacement/solutions/278271/C++Python-Sliding-Window-O(N)-instead-of-O(26N)/
    def characterReplacement(self, s: str, k: int) -> int:
        c = {}
        mf, i = 0, 0
        for j, char in enumerate(s):
            c[char] = c.get(char, 0) + 1
            mf = max(mf, c[char])
            if i - mf >= k:
                c[s[j - i]] -= 1
            else:
                i += 1  # update when more
        return i


class SolutionBS:  # O(log(n)) / O(n)
    # TODO: review
    # https://leetcode.com/problems/longest-repeating-character-replacement/solutions/2805777
    def characterReplacement(self, s: str, k: int) -> int:
        def too_long(length: int):
            c = {}
            mf, i = 0, 0
            for j, char in enumerate(s):
                c[char] = c.get(char, 0) + 1
                mf = max(mf, c[char])
                if length - mf <= k:
                    return False
                if j - i + 1 > length:
                    c[s[i]] -= 1
                    i += 1
            return True

        l, r = 0, len(s)
        while l < r:
            m = (l + r) // 2
            l, r = (l, m) if too_long(length=m + 1) else (m + 1, r)
        return (l - 1) + 1