23.04.25 Today’s Leetcode

2336. Smallest Number in Infinite Set (medium)

class SmallestInfiniteSet:

    def __init__(self):
        self.d = defaultdict(int)
        self.small = 1


    def popSmallest(self) -> int:
        cur = self.small
        self.d[self.small] -= 1
        while self.d[self.small] == -1:
            self.small += 1
        return cur

    def addBack(self, num: int) -> None:
        if num < self.small:
            self.small = num
        self.d[num] = 0


# Your SmallestInfiniteSet object will be instantiated and called as such:
# obj = SmallestInfiniteSet()
# param_1 = obj.popSmallest()
# obj.addBack(num)

862. Shortest Subarray with Sum at Least K (hard)

TLE at 82 / 97 testcases passed

class Solution:
    def shortestSubarray(self, nums: List[int], k: int) -> int:
        arr = [0]
        n = len(nums)
        for num in nums:
            arr.append(arr[-1] + num)
        
        # print(arr)
        res = math.inf
        for i in range(1, n + 1):
            for j in range(i):
                value = arr[i] - arr[j]
                if value >= k:
                    res = min(res, i - j)

        return -1 if res == math.inf else res

lee sensai’s Solution with deque

class Solution:
    def shortestSubarray(self, A, K):
        d = collections.deque([[0, 0]])
        res, cur = float('inf'), 0
        for i, a in enumerate(A):
            cur += a
            while d and cur - d[0][1] >= K:
                res = min(res, i + 1 - d.popleft()[0])
            while d and cur <= d[-1][1]:
                d.pop()
            d.append([i + 1, cur])
        return res if res < float('inf') else -1

2343. Query Kth Smallest Trimmed Number (medium)

class Solution:
    def smallestTrimmedNumbers(self, nums: List[str], queries: List[List[int]]) -> List[int]:
        nums = [int(num) for num in nums]
        n = len(nums)
        def get(k, trim_num):
            dec = 10 ** trim_num
            p = [num % dec for num in nums]
            d = sorted(p)
            tar = d[k - 1]
            index = -1
            for i in range(n):
                if p[i] == tar:
                    if index < 0:
                        index = i
                    elif nums[i] < nums[index]:
                        index = i 
            print(d, tar)
            return index
        
        arr = []
        for k, trim in queries:
            arr.append(get(k, trim))
    
        return arr

class Solution:
    def smallestTrimmedNumbers(self, nums: List[str], queries: List[List[int]]) -> List[int]:
        ans, trimmed = [], {}
        for k, trim in queries:
            trimmed.setdefault(trim, sorted([(num[-trim :], i) for i, num in enumerate(nums)]))
            ans.append(trimmed[trim][k - 1][1])
        return ans