23.05.06 Today’s Leetcode

1498. Number of Subsequences That Satisfy the Given Sum Condition (medium)

TLE at 57/62

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:

        n = len(nums)
        nums = sorted(nums)

        d = {}

        def help(index, k):
            p = target - k
            if k in d:
                d[k] //= 2
                return d[k]
            if p < k:
                return 0
            count = 0
            for i in range(index + 1, n):
                temp = nums[i]
                if i == index:
                    continue
                if temp >= k and temp <= p:
                    count += 1
                else:
                    break
            d[k] = 2 ** count
            return d[k]

        res = 0
        for index, num in enumerate(nums):
            res += help(index, num)
            res %= 10 ** 9 + 7

        return res
            

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        res, mod = 0, 1000000007
        l, r = 0, len(nums) - 1
        pre = [1]
        for i in range(1, len(nums) + 1):
            pre.append((pre[-1] << 1) % mod)
                
        nums.sort()
        
        while l <= r:
            if nums[l] + nums[r] > target:
                r -= 1
            else:
                res = (res + pre[r - l]) % mod
                l += 1

        return res

1558. Minimum Numbers of Function Calls to Make Target Array (medium)

class Solution:
    def minOperations(self, nums: List[int]) -> int:
        def isAllEven(arr):
            for num in arr:
                if num % 2 == 1:
                    return False
            return True
        
        n = len(nums)
        end = [0] * n

        res = 0
        while sum(nums) != 0:
            # print(nums, res)
            if isAllEven(nums):
                for index, num in enumerate(nums):
                    nums[index] //= 2
                res += 1
            else:
                for index, num in enumerate(nums):
                    if num % 2 == 1:
                        nums[index] -= 1
                        res += 1
        
        return res

1559. Detect Cycles in 2D Grid (medium)

class Solution:
    def containsCycle(self, grid: List[List[str]]) -> bool:
        
        visited, visited_cur = set(), set()
        stack = deque()

        row_n = len(grid)
        col_n = len(grid[0])

        for row, row_g in enumerate(grid):
            for col, val in enumerate(row_g):
                if (row, col) not in visited:   # if new cell
                    
                    # add to stack current cell and previous cell
                    # we don't have previous cell, so replace it to -1, -1
                    stack.append([row, col, -1, -1]) 
                    visited_cur.clear()              
                    while stack:
                        
                        r, c, r_prv, c_prv = stack.pop()
                        if (r, c) in visited_cur:   return True   # we saw this cell before -> cycle
                        visited_cur.add((r, c))

                        for d_r, d_c in [[-1, 0], [0, -1], [1, 0], [0, 1]]:
                            # we exclude previous cell from addition to stack
                            if 0 <= r + d_r < row_n   and (r + d_r, c + d_c) != (r_prv, c_prv)  and   \
                               0 <= c + d_c < col_n   and grid[r + d_r][c + d_c] == val:
                                    stack.append([r + d_r, c + d_c, r, c])

                    visited.update(visited_cur) # add current set to general set

        return False