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

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.