Build Array Where You Can Find The Maximum Exactly K Comparisons

Build Array Where You Can Find The Maximum Exactly K Comparisons - Problem

You are given three integers n, m, and k. You need to build an array arr of exactly n integers where each integer is between 1 and m (inclusive).

Consider an algorithm that finds the maximum element by scanning the array from left to right. The algorithm counts how many times it finds a new maximum (including the first element). This count is called the search cost.

Your task is to count how many different arrays have a search cost of exactly k. Since the answer can be very large, return it modulo 10^9 + 7.

Example: For array [3, 1, 4, 2], the search cost is 2 because we find new maximums at positions 0 (value 3) and 2 (value 4).

Input & Output

Example 1 — Basic Case

$ Input: n = 2, m = 3, k = 1

› Output: 6

💡 Note: Arrays with exactly 1 search cost: [1,1], [2,1], [2,2], [3,1], [3,2], [3,3]. Each has only the first element as a new maximum.

Example 2 — Multiple Peaks

$ Input: n = 3, m = 2, k = 2

› Output: 6

💡 Note: Arrays: [1,2,1], [1,2,2], [2,1,2] have cost 2. We need exactly 2 new maximums found during the scan.

Example 3 — Edge Case

$ Input: n = 1, m = 1, k = 1

› Output: 1

💡 Note: Only one array possible: [1]. It has exactly 1 search cost (the first element).

Constraints

1 ≤ n ≤ 50
1 ≤ m ≤ 100
1 ≤ k ≤ n

Visualization

Tap to expand

Understanding the Visualization

Input

Given n=4, m=3, k=2 (build array of length 4, values 1-3, exactly 2 peaks)

Process

Find arrays where scanning left-to-right finds exactly 2 new maximums

Output

Count all valid arrays (e.g., [1,3,2,1] has peaks at positions 0,1)

Key Takeaway

🎯 Key Insight: Use 3D DP to track position, current maximum, and remaining peaks needed

Asked in

G Google 15 M Microsoft 8

The key insight is to use dynamic programming with states tracking position, current maximum, and remaining peaks. The optimal approach uses 3D DP to count arrays efficiently. Time: O(n × m × k), Space: O(n × m × k).

Common Approaches

Approach	Time	Space	Notes
✓ Memoized Recursion	O(n × m × k)	O(n × m × k)	Use recursion with memoization to avoid recomputing subproblems
Brute Force Recursion	O(m^n × n)	O(n)	Generate all possible arrays and count those with exactly k search cost
2D Dynamic Programming	O(n × m × k)	O(n × k)	Use 2D DP table to build solution iteratively from bottom up

Memoized Recursion — Algorithm Steps

Define state: position in array, current maximum value, peaks left to achieve
Use memoization to cache subproblem results
For each position, try all possible values and recurse

Visualization

Tap to expand

Step-by-Step Walkthrough

State

Track (position, current_max, peaks_left)

Memoize

Cache results to avoid recomputation

Build

Build solution from cached subproblems

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

const int MOD = 1000000007;

typedef struct {
    int pos, maxVal, peaksLeft;
    long long result;
} MemoEntry;

MemoEntry memo[51][51][51]; // Assuming constraints
int memoInit[51][51][51];

long long dp(int pos, int maxVal, int peaksLeft, int n, int m) {
    if (peaksLeft < 0) return 0;
    if (pos == n) {
        return peaksLeft == 0 ? 1 : 0;
    }
    
    if (memoInit[pos][maxVal][peaksLeft]) {
        return memo[pos][maxVal][peaksLeft].result;
    }
    
    long long result = 0;
    
    // Try values from 1 to maxVal (no new peak)
    if (maxVal > 0) {
        result = (result + (long long) maxVal * dp(pos + 1, maxVal, peaksLeft, n, m)) % MOD;
    }
    
    // Try values greater than maxVal (new peak)
    for (int val = maxVal + 1; val <= m; val++) {
        result = (result + dp(pos + 1, val, peaksLeft - 1, n, m)) % MOD;
    }
    
    memo[pos][maxVal][peaksLeft].result = result;
    memoInit[pos][maxVal][peaksLeft] = 1;
    return result;
}

int solution(int n, int m, int k) {
    memset(memoInit, 0, sizeof(memoInit));
    return dp(0, 0, k, n, m);
}

int main() {
    int n, m, k;
    scanf("%d", &n);
    scanf("%d", &m);
    scanf("%d", &k);
    printf("%d\n", solution(n, m, k));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × m × k)

Three nested loops with memoization: n positions, m possible max values, k remaining peaks

✓ Linear Growth

Space Complexity

O(n × m × k)

Memoization table stores results for all state combinations plus recursion stack

⚡ Linearithmic Space

23.0K Views

Medium Frequency

~35 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Memoized Recursion — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler