19 posts tagged with "Hash Table"

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 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 groupThePeople(self, groupSizes: list[int]) -> list[list[int]]:
        ht: dict[int, list[int]] = {}
        for i, s in enumerate(groupSizes):
            ht[s] = ht.get(s, [])
            ht[s].append(i)
        result = []
        for s, l in ht.items():
            result.extend([l[i : i + s] for i in range(0, len(l), s)])
        return result

class Solution:
    def countCompleteSubarrays(self, nums: list[int]) -> int:
        amt, D, result, i = {}, len(set(nums)), 0, 0
        for num in nums:
            amt[num] = amt.get(num, 0) + 1
            while len(amt) == D:
                amt[nums[i]] -= 1
                if amt[nums[i]] == 0:
                    del amt[nums[i]]
                i += 1
            result += i
        return result

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

class Solution:
    def letterCombinations(self, digits: str):
        LETTERS = ['', '', 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz']
        letters = [LETTERS[i] for i in map(int, digits)]

        def backtracking(comb: str, i: int):
            if i == len(digits):
                yield comb
                return
            for char in letters[i]:
                yield from backtracking(comb + char, i + 1)

        yield from backtracking('', 0) if digits else []


class Solution1:
    def letterCombinations(self, digits: str) -> list[str]:
        result = []

        def backtracking(comb: str, letters: list[str]):
            if not letters:
                return result.append(comb)
            for char in letters[0]:
                backtracking(comb + char, letters[1:])

        LETTERS = ['', '', 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz']
        backtracking('', [LETTERS[i] for i in map(int, digits)])
        return result if digits else []


class Solution2:
    def letterCombinations(self, digits: str) -> list[str]:
        LETTERS = ['', '', 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz']
        letters = [LETTERS[i] for i in map(int, digits)]
        result = []

        def backtracking(comb: str, i: int):
            if i == len(digits):
                return result.append(comb)
            for char in letters[i]:
                backtracking(comb + char, i + 1)

        backtracking('', 0)
        return result if digits else []

from typing import Optional


class Node:
    def __init__(
        self,
        value=0,
        key=0,  # for eviction
        left: Optional['Node'] = None,
        right: Optional['Node'] = None,
    ):
        self.key = key
        self.value = value
        self.left = left
        self.right = right

    def append(self, node: 'Node'):
        node.left = self
        node.right = self.right
        if self.right:
            self.right.left = node
        self.right = node

    def isolate(self):
        if self.left:
            self.left.right = self.right
        if self.right:
            self.right.left = self.left


class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.dict: dict[int, Node] = {}
        self.fresh = Node()
        self.stale = Node()
        self.fresh.right = self.stale
        self.stale.left = self.fresh
        self.amount = 0

    def get(self, key: int) -> int:
        node = self.dict.get(key, Node(-1))
        if key in self.dict:
            node.isolate()
            self.fresh.append(node)
        return node.value

    def put(self, key: int, value: int) -> None:
        if key in self.dict:
            self.dict[key].isolate()
        else:
            if self.amount == self.capacity:
                evicted = self.stale.left
                if evicted:
                    evicted.isolate()
                    self.dict.pop(evicted.key)
            else:
                self.amount += 1
        node = self.dict.setdefault(key, Node(key=key))
        self.fresh.append(node)
        node.value = value

class SnapshotArray:
    def __init__(self, length: int):
        self._array: list[list[tuple[int, int]]] = [[(-1, 0)] for _ in range(length)]
        self._snap_id = -1

    def set(self, index: int, val: int) -> None:
        self._array[index].append((self._snap_id, val))

    def snap(self) -> int:
        self._snap_id += 1
        return self._snap_id

    @staticmethod
    def bs_r(a, t):
        l, r = 0, len(a)
        while l < r:
            m = (l + r) // 2
            if a[m] > t:
                r = m
            else:
                l = m + 1
        return l

    def get(self, index: int, snap_id: int) -> int:
        low = self.bs_r(self._array[index], (snap_id,))
        return self._array[index][low - 1][1]

from collections import defaultdict


class UndergroundSystem:
    def __init__(self):
        checkInStationNameT = checkOutStationNameT = str
        checkInTimeT = travelTimeT = int
        idT = countT = int
        self.check_in: dict[idT, tuple[checkInTimeT, checkInStationNameT]] = {}
        self.time: defaultdict[
            tuple[checkInStationNameT, checkOutStationNameT], tuple[travelTimeT, countT]
        ] = defaultdict(lambda: (0, 0))

    def checkIn(self, id: int, stationName: str, t: int) -> None:
        self.check_in[id] = (t, stationName)

    def checkOut(self, id: int, stationName: str, t: int) -> None:
        check_in_time, check_in_station_name = self.check_in.pop(id)
        _key = check_in_station_name, stationName
        _travel_time, _count = self.time[_key]
        self.time[_key] = _travel_time + (t - check_in_time), _count + 1

    def getAverageTime(self, startStation: str, endStation: str) -> float:
        _key = startStation, endStation
        travel_time, count = self.time[_key]
        return travel_time / count

import heapq


class SmallestInfiniteSet:
    def __init__(self):
        self.i = 0
        self.q = []

    def popSmallest(self) -> int:
        if self.q:
            return heapq.heappop(self.q)
        self.i += 1
        return self.i

    def addBack(self, num: int) -> None:
        if num <= self.i and num not in self.q:
            heapq.heappush(self.q, num)

from collections import deque


# Definition for a Node.
class Node:
    def __init__(self, val=0, neighbors=None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []


class Solution1:
    def cloneGraph(self, node: 'Node') -> 'Node':
        visited = {}

        def dfs(node):
            if node in visited:
                return visited[node]
            visited[node] = Node(val=node.val)
            # note: create new node first, then update the neighbors
            visited[node].neighbors = [dfs(x) for x in node.neighbors]
            return visited[node]

        return node and dfs(node)


class Solution2:
    def cloneGraph(self, node: 'Node') -> 'Node':
        def bfs(node):
            visited = {node: Node(val=node.val)}
            queue = [node]
            while queue:
                next_ = []
                for q in queue:
                    for n in q.neighbors:
                        if n not in visited:
                            visited[n] = Node(val=n.val)
                            next_.append(n)
                        visited[q].neighbors.append(visited[n])
                queue = next_
            return visited[node]

        return node and bfs(node)


class Solution:
    def cloneGraph(self, node: 'Node') -> 'Node':
        def bfs(node):
            visited = {node: Node(val=node.val)}
            queue = deque([node])
            while queue:
                q = queue.popleft()
                for n in q.neighbors:
                    if n not in visited:
                        visited[n] = Node(val=n.val)
                        queue.append(n)
                    visited[q].neighbors.append(visited[n])
            return visited[node]

        return node and bfs(node)

from typing import Optional


class Node:
    def __init__(self, is_end: bool = False):
        self.is_end = is_end
        self.children: dict[str, Node] = {}

    def __repr__(self):
        return f'''{'! ' if self.is_end else ''}{self.children}'''


class Trie:
    def __init__(self):
        self.root = Node()

    def insert(self, word: str) -> None:
        node = self.root
        for c in word:
            node.children[c] = node.children.get(c, Node())
            node = node.children[c]
        node.is_end = True

    def _last_node_same_with(self, word: str) -> Optional[Node]:
        node = self.root
        for c in word:
            if c not in node.children:
                return
            node = node.children[c]
        return node

    def search(self, word: str) -> bool:
        node = self._last_node_same_with(word)
        return bool(node) and node.is_end

    def startsWith(self, word: str) -> bool:
        node = self._last_node_same_with(word)
        return bool(node)

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
from collections import Counter


class Solution1:
    def topKFrequent(self, words: list[str], k: int) -> list[str]:
        c = Counter(words)
        return [x for x in sorted(c, key=lambda key: (-c[key], key))][:k]


class Solution:
    def topKFrequent(self, words: list[str], k: int) -> list[str]:
        c = Counter(words)
        return heapq.nsmallest(k, c, key=lambda key: (-c[key], key))

from collections import Counter


class Solution:
    def getHint(self, s: str, g: str) -> str:
        a, b = 0, 0
        cs, cg = Counter(), Counter()
        for i in range(len(s)):
            if s[i] == g[i]:
                a += 1
                continue
            if cg[s[i]]:
                cg[s[i]] -= 1
                b += 1
            else:
                cs[s[i]] += 1
            if cs[g[i]]:
                cs[g[i]] -= 1
                b += 1
            else:
                cg[g[i]] += 1
        return f'{a}A{b}B'

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

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)