Back to Questions

402. Distinct Array Cost

Fulltime•8/22/2025
Microsoft

Problem Description

You are given three arrays: `n`, `m`, and `totalCost`. The i-th element of `n` represents the length of an array, the i-th element of `m` represents the maximum possible value in the array (inclusive), and the i-th element of `totalCost` represents the desired cost of finding the maximum element in the array. The cost of finding the maximum element in an array is defined as the number of times the maximum value is updated when iterating through the array from left to right. For each i, you need to find the number of distinct arrays of length `n[i]` with values in the range `[1, m[i]]` such that the cost of finding the maximum element in the array is equal to `totalCost[i]`. Return an array containing the number of distinct arrays for each i.

Examples

Example 1:
Input: {"n":[2,3,4],"m":[3,3,3],"totalCost":[1,2,2]}
Output: 3, 1, 6
Explanation: For i=0, n=2, m=3, cost=1. Possible arrays: [1,2], [2,3], [1,3]. For i=1, n=3, m=3, cost=2. Possible arrays: [1,2,3]. For i=2, n=4, m=3, cost=2. Possible arrays: [1,1,2,3], [1,1,2,4], [1,1,3,4], [1,2,2,4], [1,3,3,4], [2,2,3,4]
Example 2:
Input: {"n":[1,2],"m":[5,2],"totalCost":[1,2]}
Output: 5, 0
Explanation: For i=0, n=1, m=5, cost=1. Possible arrays: [1], [2], [3], [4], [5]. For i=1, n=2, m=2, cost=2. No possible arrays.
Example 3:
Input: {"n":[3],"m":[2],"totalCost":[1]}
Output: 4
Explanation: For i=0, n=3, m=2, cost=1. Possible arrays: [2,2,2], [1,2,2], [2,1,2], [2,2,1]

Constraints

  • 1 ≤ n.length ≤ 100
  • 1 ≤ n[i] ≤ 10
  • 1 ≤ m[i] ≤ 10
  • 1 ≤ totalCost[i] ≤ n[i]

Source

View Original Question