Frontend School

Product Batch Minimums

DSA
medium

Product Batch Minimums

Medium
Arrays
Stack
Monotonic Stack

Overview

At Zepto, efficient inventory management and pricing strategies are crucial. We often receive products in batches, and the price of an item can fluctuate across different batches. To analyze potential pricing strategies or understand value depreciation, we need to calculate the aggregate value derived from the minimum prices within all possible contiguous sub-batches.

This problem asks you to calculate the sum of the minimums of all possible contiguous subarrays (sub-batches) of product prices. This metric can help identify pricing trends or inform dynamic pricing models by understanding the lowest price points within various segments of inventory.

What you need to do / Task

Implement a function sumOfBatchMinimums that takes an array of product prices and returns the sum of the minimum values of all its contiguous subarrays. Since the sum can be very large, you should return the result modulo 10^9 + 7.

Input & output

  • Input: prices: number[]
    • An array of positive integers representing the prices of products in a sequence.
  • Output: number
    • A single integer representing the total sum of minimums of all contiguous subarrays, modulo 10^9 + 7.

Clarifications

  • Empty Input: If the prices array is empty, the function should return 0.
  • Large Numbers: The sum of minimums can exceed standard integer limits. Ensure all intermediate calculations and the final result are handled with modulo 10^9 + 7 to prevent overflow.
  • Duplicates: If there are duplicate prices, ensure each price contributes to the sum correctly as the minimum for its unique set of subarrays. For example, in [2, 2, 2], the first 2 should be considered the minimum for [2], [2,2], [2,2,2] (starting at index 0), the second 2 for [2], [2,2] (starting at index 1), and so on, without double-counting a subarray's minimum.

Examples

1

Example 1

Input:

prices = [3,1,2,4]

Output:

17

Note:

The subarrays are: [3], min=3 [1], min=1 [2], min=2 [4], min=4 [3,1], min=1 [1,2], min=1 [2,4], min=2 [3,1,2], min=1 [1,2,4], min=1 [3,1,2,4], min=1 Sum = 3+1+2+4+1+1+2+1+1+1 = 17.

2

Example 2

Input:

prices = [1,2,3]

Output:

10

Note:

The subarrays are: [1], min=1 [2], min=2 [3], min=3 [1,2], min=1 [2,3], min=2 [1,2,3], min=1 Sum = 1+2+3+1+2+1 = 10.

3

Example 3

Input:

prices = [1]

Output:

1

Note:

The only subarray is [1], with minimum 1. Sum = 1.

Constraints

Constraints & assumptions

  • 1 <= prices.length <= 10^5
  • 1 <= prices[i] <= 10^9
  • The final result should be returned modulo 10^9 + 7.

Out of scope

  • Input validation for non-numeric values or negative prices.
  • Handling network latency or database interactions.

What interviewers evaluate

  • Correctness of the algorithm for summing subarray minimums using a monotonic stack.
  • Efficiency of the solution in terms of time and space complexity.
  • Ability to correctly handle edge cases, including empty arrays and arrays with identical elements.
  • Proper application of modulo arithmetic to manage large sums.

Loading editor...