Introduction

In this blog post, we will explore how to solve the LeetCode problem "907" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

Given an array of integers arr, find the sum of min(b), where b ranges over every (contiguous) subarray of arr. Since the answer may be large, return the answer modulo 109 + 7. Example 1: Input: arr = [3,1,2,4] Output: 17 Explanation: Subarrays are [3], [1], [2], [4], [3,1], [1,2], [2,4], [3,1,2], [1,2,4], [3,1,2,4]. Minimums are 3, 1, 2, 4, 1, 1, 2, 1, 1, 1. Sum is 17. Example 2: Input: arr = [11,81,94,43,3] Output: 444 Constraints: 1 <= arr.length <= 3 104 1 <= arr[i] <= 3 104

Explanation

Here's the solution:

• Monotonic Stack Approach: The core idea is to use two monotonic stacks (one increasing, one decreasing) to efficiently determine the range for each element arr[i] where it is the minimum value in the subarray.
• Left and Right Boundaries: For each element, the stacks will help find the indices left and right such that arr[i] is the minimum element in all subarrays starting from left + 1 and ending at right - 1.

• Contribution Calculation: Knowing the range, we can determine the number of subarrays for which arr[i] is the minimum and add its contribution ( arr[i] * number of such subarrays) to the total sum.

• Time Complexity: O(N), Space Complexity: O(N)

Code

    def sumSubarrayMins(arr: list[int]) -> int:
    """
    Calculates the sum of minimums of all contiguous subarrays of arr.

    Args:
        arr: A list of integers.

    Returns:
        The sum of minimums of all subarrays modulo 10^9 + 7.
    """
    n = len(arr)
    left = [0] * n
    right = [0] * n
    stack = []
    MOD = 10**9 + 7

    # Calculate left boundaries
    for i in range(n):
        while stack and arr[stack[-1]] > arr[i]:
            stack.pop()
        if stack:
            left[i] = i - stack[-1]
        else:
            left[i] = i + 1
        stack.append(i)

    stack = []  # Reset stack

    # Calculate right boundaries
    for i in range(n - 1, -1, -1):
        while stack and arr[stack[-1]] >= arr[i]:
            stack.pop()
        if stack:
            right[i] = stack[-1] - i
        else:
            right[i] = n - i
        stack.append(i)

    ans = 0
    for i in range(n):
        ans = (ans + arr[i] * left[i] * right[i]) % MOD

    return ans