23.03.04 Today’s Leetcode

2444. Count Subarrays With Fixed Bounds (hard)

Brute Force Approach

class Solution:
    def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:
        def between(k):
            return minK <= k and k <= maxK
        
        n = len(nums)
        res = 0
        for i in range(n):
            minv, maxv = nums[i], nums[i]
            for j in range(i, n):
                minv = min(minv, nums[j])
                maxv = max(maxv, nums[j])
                if minv == minK and maxv == maxK:
                    res += 1
        return res

Two Pointer Approach

class Solution:
    def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:
        n = len(nums)
        leftBound = -1
        lastMin, lastMax = -1, -1
        count = 0
        
        for i in range(n):
            if nums[i] >= minK and nums[i] <= maxK:
                lastMin = i if nums[i] == minK else lastMin
                lastMax = i if nums[i] == maxK else lastMax
                count += max(0, min(lastMin, lastMax) - leftBound)
            else:
                leftBound = i
                lastMin = -1
                lastMax = -1
        
        return count

198. House Robber (medium)

class Solution:
    def rob(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [-1] * n

        def dfs(pos):
            if pos >= n:
                print("!!")
                return 0
            if dp[pos] >= 0:
                return dp[pos]
            temp = 0
            for i in range(pos + 2, n):
                temp = max(temp, dfs(i))
            dp[pos] = temp + nums[pos]
            return dp[pos]
        
        res = -1
        for i in range(n):
            res = max(res, dfs(i))
        return res

120. Triangle (medium)

DFS Approach

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        max_level = len(triangle)
        def dfs(level, pos):
            if pos >= level or pos < 0:
                return 0
            if level > max_level:
                return 0
            temp = math.inf
            temp = min(temp, dfs(level + 1, pos))
            temp = min(temp, dfs(level + 1, pos + 1))

            return temp + triangle[level - 1][pos]

        return dfs(1, 0)

Bottom-UP DP Approach

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        max_level = len(triangle)
        for level in range(max_level - 1, 0, -1):
            for i in range(level):
                triangle[level - 1][i] += min(triangle[level][i], triangle[level][i + 1])

        # print(triangle)
        return triangle[0][0]