Skip to main content
Talentd

Build Array Where You Can Find The Maximum Exactly K Comparisons - Solution & Explanation

HardDynamic ProgrammingPrefix Sum11 min readAsked at: Google, Dunzo
Practice this problem

Problem Statement

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

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 109 + 7.

 

Example 1:

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:

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

Example 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]

 

Constraints:

  • 1 <= n <= 50
  • 1 <= m <= 100
  • 0 <= k <= n

Approach Overview

Problem Overview: You need to build an array of length n with values from 1 to m. While scanning the array from left to right, every time a new element becomes the maximum, the search cost increases by one. The task is to count how many arrays produce exactly k such maximum updates.

Approach 1: Recursion with Memoization (Top-Down DP) (Time: O(n * m * k), Space: O(n * m * k))

This approach models the problem as a recursive state. At position i, you track the current maximum value maxSoFar and how many comparisons (cost) have already been used. From this state, try placing every number from 1 to m. If the chosen value is greater than maxSoFar, the cost increases and the new maximum updates. Otherwise, the cost stays the same. Memoization stores results for the state (i, maxSoFar, cost) so repeated subproblems are avoided. This converts exponential recursion into polynomial dynamic programming. The state space has at most n * m * k combinations.

Approach 2: Dynamic Programming with 3D Table + Prefix Sum Optimization (Time: O(n * m * k), Space: O(n * m * k))

The bottom-up DP solution builds results iteratively. Define dp[i][j][c] as the number of arrays of length i where the maximum value is j and the search cost is c. Two transitions exist when extending the array:

1) Append a value ≤ j, which keeps the maximum unchanged. There are j choices, so multiply by j.

2) Append value j as a new maximum. This means the previous maximum was smaller, so sum all states with maximum < j and cost c-1.

The second transition would normally require iterating over all smaller maxima, but a running prefix sum speeds this up. Instead of scanning repeatedly, maintain cumulative sums across the j dimension. This reduces an extra loop and keeps the overall complexity at O(n * m * k). The method is deterministic, iterative, and typically faster in practice than recursion.

Both approaches rely on classic Dynamic Programming state modeling. The optimized transition uses cumulative sums similar to techniques in Prefix Sum problems. Thinking in terms of "current maximum" and "cost so far" is the key observation that unlocks the DP formulation.

Recommended for interviews: The 3D dynamic programming solution with prefix-sum optimization. Interviewers expect you to define the DP state (index, currentMax, cost) and derive the transitions clearly. Starting with a memoized recursive formulation shows strong problem decomposition skills, while converting it to an iterative DP demonstrates optimization awareness.

Approach 1: Dynamic Programming with 3D Table

We can use dynamic programming to solve this problem by maintaining a 3D array where dp[i][j][k] represents the number of ways to construct an array of length i, with values up to j and exactly k comparisons.

Recurrence relations can be defined by considering whether you want to extend the array by a value that does or doesn't increase the number of comparisons. Use modulo operations to manage large numbers.

The initial step is to set the dp array for arrays of length 1 with exactly one comparison. It can also reach up to any value from 1 to m. As you build arrays, you either keep the maximum unchanged or increase it with a new maximum. The complexity arises from trying to keep a 3D table of results for all possible combinations of parameters and then aggregating those results.

Code

PythonC++

Python

C++

Complexity

Time Complexity: O(n * m^2 * k). Space Complexity: O(n * m * k).

Try this approach in the editor →

Approach 2: Recursion with Memoization

This approach uses recursion with memoization to avoid recomputing the solutions for subproblems. The recursive function attempts to build the array incrementally by deciding, step by step, which value to add, and whether it will increase the maximum so far. By caching previously computed results, it reduces repeated calculations.

The Java solution initializes a 3D memoization table filled with -1 (uncomputed states) and recursively defines valid states for the dynamic structure of the array. It traverses through not only possible values to append but also considers whether adding the value modifies the comparison metric used (k comparisons).

Code

JavaJavaScript

Java

JavaScript

Complexity

Time Complexity: O(n * m * k). Space Complexity: O(n * m * k) due to recursion stack and memoization storage.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Dynamic Programming with 3D Table

Time Complexity: O(n * m^2 * k). Space Complexity: O(n * m * k).

Recursion with Memoization

Time Complexity: O(n * m * k). Space Complexity: O(n * m * k) due to recursion stack and memoization storage.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Recursion with MemoizationO(n * m * k)O(n * m * k)Good for understanding the state transition and building intuition before converting to iterative DP
3D Dynamic ProgrammingO(n * m * k * m)O(n * m * k)Straightforward implementation but slower due to iterating over smaller maxima
3D DP with Prefix Sum OptimizationO(n * m * k)O(n * m * k)Best practical solution when m is large; avoids repeated summation using prefix sums

Video Solution

Build Array Where You Can Find The Maximum Exactly K Comparisons | DP Concepts 15 | Leetcode 1420 • codestorywithMIK • 23,941 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Build Array Where You Can Find The Maximum Exactly K Comparisons easy or hard?
LeetCode classifies this problem as Hard because it requires designing a three-dimensional dynamic programming state and optimizing transitions using prefix sums. Candidates must carefully reason about how the maximum value evolves while building the array and how the search cost changes.
Build Array Where You Can Find The Maximum Exactly K Comparisons Python/Java solution
Python and Java implementations typically follow the same DP formulation. Python solutions often use recursion with functools.lru_cache for memoization, while Java implementations commonly use iterative 3D arrays for bottom-up DP. Both approaches maintain states defined by index, current maximum, and search cost.
How to solve Build Array Where You Can Find The Maximum Exactly K Comparisons in O(n)?
Solving this problem strictly in O(n) is not feasible because the state depends on three parameters: array length n, value range m, and cost k. The optimal practical complexity is O(n * m * k) using dynamic programming with prefix sums. Each state transition is computed in constant time after prefix precomputation.
What is the best approach for Build Array Where You Can Find The Maximum Exactly K Comparisons?
The most efficient approach uses dynamic programming with a 3D state and prefix sum optimization. The state dp[i][j][c] represents arrays of length i where j is the current maximum and c is the search cost. Prefix sums allow fast computation of transitions where a new maximum is introduced. This reduces the complexity to O(n * m * k) time and O(n * m * k) space.
Is Build Array Where You Can Find The Maximum Exactly K Comparisons asked at Google/Amazon/Meta?
Dynamic programming problems involving state transitions and counting combinations appear frequently in interviews at companies like Google, Amazon, and Meta. Variants of this problem test the ability to define multi-dimensional DP states and optimize transitions using prefix sums or cumulative aggregates.
What data structure is used in Build Array Where You Can Find The Maximum Exactly K Comparisons?
The core data structure is a 3D dynamic programming table, typically implemented as a nested array or vector. Prefix sum arrays are used to accelerate transitions that sum values across ranges of maximums. Hash maps may also be used in memoized recursion to cache computed states.
What is the time complexity of Build Array Where You Can Find The Maximum Exactly K Comparisons?
The optimized dynamic programming solution runs in O(n * m * k) time with O(n * m * k) space. A naive DP version that iterates through all smaller maximum values adds an extra factor of m, leading to O(n * m^2 * k). Memoized recursion also achieves O(n * m * k) because each state is computed once.

Ready to solve this problem?

Practice Build Array Where You Can Find The Maximum Exactly K Comparisons with our built-in code editor and test cases.

Practice on FleetCode
Previous

Longest Palindromic Substring

Next

Regular Expression Matching