23.04.03 Today’s Leetcode

881. Boats to Save People (medium)

Two Pointer Approach, Failed at 71/76 Testcases

class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int:
        people.sort()
        n = len(people)
        count = 0
        i = 0
        j = n - 1
        print(people)
        while i <= j:
            a, b = people[i], people[j]
            print(i, j)
            if a + b > limit:
                j -= 1
                count += 1
            elif a + b == limit:
                i += 1
                j -= 1
                count += 1
            else:
                k = i + 1
                cur = a + b
                while k < n and cur + people[k] <= limit:
                    cur += people[k]
                    k += 1
                i = k
                j -= 1
                count += 1
        return count

But there is more clean solution

class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int:
        people.sort()
        i = 0
        j = len(people) - 1
        boats = 0
        while i <= j:
            if people[i] + people[j] <= limit:
                i += 1
                j -= 1
            else:
                j -= 1
            boats += 1
        return boats

907. Sum of Subarray Minimums (medium)

Failed at 71/76 testcases

class Solution:
    def sumSubarrayMins(self, arr: List[int]) -> int:
        n = len(arr)
        def help(i):
            a, b = i - 1, i + 1
            while a >= 0 and arr[a] > arr[i]:
                a -= 1
            while b < n and arr[b] >= arr[i]:
                b += 1
            return (i - a - 1, b - i - 1)

        res = 0
        for index, num in enumerate(arr):
            a, b = help(index)
            print(a, b)
            res += (a + 1) * (b + 1) * num
            res %= 10**9 + 7
        
        return res

Stack Approach

class Solution:
    def sumSubarrayMins(self, nums):
        MOD = 10**9 + 7
        stack = []
        res =  0
		prevsum = 0
		
        for index, value in enumerate(nums):
            count = 1
            while stack and stack[-1][0] >= value:
                v, c = stack.pop()
                count += c
                prevsum -= v * c
            stack.append((value, count))
            prevsum += value * count
            res += prevsum
            
        return res % MOD