Problem

You are given three integers n, m and k. Consider the following algorithm to find the maximum element of an array of positive integers:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

maximum_value = -1
maximum_index = -1
search_cost = 0
n = arr. length
for (1 = 0; i < n; i++) {
	if (maximum_value ‹ arr[i]) {
		maximum_value = arr [1]
		maximum_index = i
		search_cost = search_cost + 1		
	}
} 
return maximum_index

You should build the array arr which has the following properties:

  • arr has exactly n integers.
  • 1 <= arr[i] <= m where (0 <= i < n).
  • After applying the mentioned algorithm to arr, the value search_cost is equal to k.

Return the number of ways to build the array arr under the mentioned conditions. As the answer may grow large, the answer must be computed modulo 10^9 + 7.

Examples

Example 1

1
2
3

Input: n = 2, m = 3, k = 1
Output: 6
Explanation: The possible arrays are [1, 1], [2, 1], [2, 2], [3, 1], [3, 2] [3, 3]

Example 2

1
2
3

Input: n = 5, m = 2, k = 3
Output: 0
Explanation: There are no possible arrays that satisfy the mentioned conditions.

Example 3

1
2
3

Input: n = 9, m = 1, k = 1
Output: 1
Explanation: The only possible array is [1, 1, 1, 1, 1, 1, 1, 1, 1]

Solution

Method 1 – Dynamic Programming with State Compression

Intuition

We use dynamic programming to count the number of ways to build the array. The key is to track, for each position, the current maximum and the number of times the maximum has changed (i.e., the search cost). For each new element, we either keep the current maximum or increase it, incrementing the search cost.

Approach

  1. Define a DP table dp[i][j][c]:
    • i: current length of the array (from 0 to n)
    • j: current maximum value in the array (from 0 to m)
    • c: current search cost (from 0 to k)
  2. Initialize dp[0][0][0] = 1 (empty array, no max, no cost).
  3. For each position i from 0 to n-1:
    • For each possible current max j (0 to m):
      • For each possible cost c (0 to k):
        • For each possible next value x (1 to m):
          • If x > j, increment cost (c+1) and set new max to x.
          • Else, keep cost and max.
  4. The answer is the sum of all dp[n][j][k] for j in 1 to m.
  5. Use modulo 10^9 + 7 for all operations.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {
public:
	 int numOfArrays(int n, int m, int k) {
		  const int MOD = 1e9 + 7;
		  vector<vector<vector<int>>> dp(n+1, vector<vector<int>>(m+1, vector<int>(k+1, 0)));
		  dp[0][0][0] = 1;
		  for (int i = 0; i < n; ++i) {
				for (int mx = 0; mx <= m; ++mx) {
					 for (int c = 0; c <= k; ++c) {
						  if (dp[i][mx][c] == 0) continue;
						  for (int x = 1; x <= m; ++x) {
								if (x > mx && c+1 <= k)
									 dp[i+1][x][c+1] = (dp[i+1][x][c+1] + dp[i][mx][c]) % MOD;
								else if (x <= mx)
									 dp[i+1][mx][c] = (dp[i+1][mx][c] + dp[i][mx][c]) % MOD;
						  }
					 }
				}
		  }
		  int ans = 0;
		  for (int mx = 1; mx <= m; ++mx)
				ans = (ans + dp[n][mx][k]) % MOD;
		  return ans;
	 }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

func numOfArrays(n int, m int, k int) int {
	 MOD := int(1e9 + 7)
	 dp := make([][][]int, n+1)
	 for i := range dp {
		  dp[i] = make([][]int, m+1)
		  for j := range dp[i] {
				dp[i][j] = make([]int, k+1)
		  }
	 }
	 dp[0][0][0] = 1
	 for i := 0; i < n; i++ {
		  for mx := 0; mx <= m; mx++ {
				for c := 0; c <= k; c++ {
					 if dp[i][mx][c] == 0 {
						  continue
					 }
					 for x := 1; x <= m; x++ {
						  if x > mx && c+1 <= k {
								dp[i+1][x][c+1] = (dp[i+1][x][c+1] + dp[i][mx][c]) % MOD
						  } else if x <= mx {
								dp[i+1][mx][c] = (dp[i+1][mx][c] + dp[i][mx][c]) % MOD
						  }
					 }
				}
		  }
	 }
	 ans := 0
	 for mx := 1; mx <= m; mx++ {
		  ans = (ans + dp[n][mx][k]) % MOD
	 }
	 return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
	 public int numOfArrays(int n, int m, int k) {
		  int MOD = 1_000_000_007;
		  int[][][] dp = new int[n+1][m+1][k+1];
		  dp[0][0][0] = 1;
		  for (int i = 0; i < n; i++) {
				for (int mx = 0; mx <= m; mx++) {
					 for (int c = 0; c <= k; c++) {
						  if (dp[i][mx][c] == 0) continue;
						  for (int x = 1; x <= m; x++) {
								if (x > mx && c+1 <= k)
									 dp[i+1][x][c+1] = (dp[i+1][x][c+1] + dp[i][mx][c]) % MOD;
								else if (x <= mx)
									 dp[i+1][mx][c] = (dp[i+1][mx][c] + dp[i][mx][c]) % MOD;
						  }
					 }
				}
		  }
		  int ans = 0;
		  for (int mx = 1; mx <= m; mx++)
				ans = (ans + dp[n][mx][k]) % MOD;
		  return ans;
	 }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
	 fun numOfArrays(n: Int, m: Int, k: Int): Int {
		  val MOD = 1_000_000_007
		  val dp = Array(n+1) { Array(m+1) { IntArray(k+1) } }
		  dp[0][0][0] = 1
		  for (i in 0 until n) {
				for (mx in 0..m) {
					 for (c in 0..k) {
						  if (dp[i][mx][c] == 0) continue
						  for (x in 1..m) {
								if (x > mx && c+1 <= k)
									 dp[i+1][x][c+1] = (dp[i+1][x][c+1] + dp[i][mx][c]) % MOD
								else if (x <= mx)
									 dp[i+1][mx][c] = (dp[i+1][mx][c] + dp[i][mx][c]) % MOD
						  }
					 }
				}
		  }
		  var ans = 0
		  for (mx in 1..m)
				ans = (ans + dp[n][mx][k]) % MOD
		  return ans
	 }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution:
	 def numOfArrays(self, n: int, m: int, k: int) -> int:
		  MOD = 10**9 + 7
		  dp: list[list[list[int]]] = [[[0] * (k+1) for _ in range(m+1)] for _ in range(n+1)]
		  dp[0][0][0] = 1
		  for i in range(n):
				for mx in range(m+1):
					 for c in range(k+1):
						  if dp[i][mx][c] == 0:
								continue
						  for x in range(1, m+1):
								if x > mx and c+1 <= k:
									 dp[i+1][x][c+1] = (dp[i+1][x][c+1] + dp[i][mx][c]) % MOD
								elif x <= mx:
									 dp[i+1][mx][c] = (dp[i+1][mx][c] + dp[i][mx][c]) % MOD
		  ans = 0
		  for mx in range(1, m+1):
				ans = (ans + dp[n][mx][k]) % MOD
		  return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

impl Solution {
	 pub fn num_of_arrays(n: i32, m: i32, k: i32) -> i32 {
		  const MOD: i32 = 1_000_000_007;
		  let (n, m, k) = (n as usize, m as usize, k as usize);
		  let mut dp = vec![vec![vec![0; k+1]; m+1]; n+1];
		  dp[0][0][0] = 1;
		  for i in 0..n {
				for mx in 0..=m {
					 for c in 0..=k {
						  let val = dp[i][mx][c];
						  if val == 0 { continue; }
						  for x in 1..=m {
								if x > mx && c+1 <= k {
									 dp[i+1][x][c+1] = (dp[i+1][x][c+1] + val) % MOD;
								} else if x <= mx {
									 dp[i+1][mx][c] = (dp[i+1][mx][c] + val) % MOD;
								}
						  }
					 }
				}
		  }
		  let mut ans = 0;
		  for mx in 1..=m {
				ans = (ans + dp[n][mx][k]) % MOD;
		  }
		  ans
	 }
}

Complexity

  • ⏰ Time complexity: O(n * m * m * k) (can be optimized to O(n * m * k) with prefix sums)
  • 🧺 Space complexity: O(n * m * k)