We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Build Array Where You Can Find The Maximum Exactly K Comparisons

Number: 1535

Difficulty: Hard

Paid? No

Companies: Amazon, Dunzo

Problem Description

We are given three integers n, m, and k. We need to construct an array arr of length n where each element is between 1 and m (inclusive). An algorithm finds the maximum element by initializing the current maximum from the first element (counting as one comparison) and then scanning from left to right. Whenever an element is strictly greater than the current maximum, the maximum is updated and the search_cost increases by one. The task is to count the number of arrays such that the search_cost is exactly k. Since the answer can be very large, report it modulo 10^9+7.

Key Insights

  • We want to count arrays where exactly k “record‐breaking” updates (including the first element) occur.
  • A new record occurs when the current element is greater than all previous elements.
  • When inserting a new element into an array:
    • If it does not form a new record then it must be less than or equal to the current maximum.
    • If it is a new record then it must be chosen from numbers larger than the current maximum.
  • A 3D dynamic programming state can be defined as dp[i][j][r], where:
    • i: number of elements processed
    • j: cost (number of times we updated the maximum)
    • r: current maximum value of the array
  • Transitions:
    • “Not updating” the maximum: Choose any value from 1 to r (r choices).
    • “Updating” the maximum: Choose any value from r+1 to m.
  • Finally, the answer is the sum of all dp[n][k][r] for r from 1 to m.

Space and Time Complexity

Time Complexity: O(n * k * m), where n ≤ 50, k ≤ n and m ≤ 100. Space Complexity: O(n * k * m)

Solution

We use dynamic programming. Define a state dp[i][j][r] which represents the number of ways to form an array of length i, with exactly j comparisons (or cost) and having the current maximum equal to r. The base case is for a single element: dp[1][1][r] = 1 for each r from 1 to m because the first element is always a new maximum. For each subsequent element, we have two cases:

  1. The new element does not update the maximum. It may be any value from 1 up to the current maximum r. This contributes dp[i-1][j][r] * r.
  2. The new element updates the maximum. Its value can be any integer from r+1 to m. If we update, the new current maximum becomes that chosen number. This contributes dp[i-1][j-1][r] for each possible new value. We then sum over all possible current maximum values for the final answer.

Code Solutions

MOD = 10**9 + 7

def build_array(n, m, k):
    # dp[i][j][r]: ways to build an array of length i, with j comparisons and current max = r.
    dp = [[[0] * (m + 1) for _ in range(k + 1)] for _ in range(n + 1)]
    
    # Base case: for one element, the cost is 1 and current maximum is the element itself.
    for r in range(1, m + 1):
        dp[1][1][r] = 1

    # Fill the dp table.
    for i in range(1, n):
        for j in range(1, k + 1):  # current cost count
            for curr_max in range(1, m + 1):
                if dp[i][j][curr_max] == 0:
                    continue
                currWays = dp[i][j][curr_max]
                # Case 1: Without updating the maximum.
                # We can choose any number from 1 to curr_max.
                dp[i + 1][j][curr_max] = (dp[i + 1][j][curr_max] + currWays * curr_max) % MOD
                # Case 2: With updating the maximum.
                # Choose any number from curr_max+1 to m.
                # Each new number becomes the new current maximum.
                for new_max in range(curr_max + 1, m + 1):
                    dp[i + 1][j + 1][new_max] = (dp[i + 1][j + 1][new_max] + currWays) % MOD

    # Sum up all the ways where we have built an array of length n and exactly k comparisons.
    result = 0
    for r in range(1, m + 1):
        result = (result + dp[n][k][r]) % MOD
    return result

# Example usage:
print(build_array(2, 3, 1))  # Expected output: 6
print(build_array(5, 2, 3))  # Expected output: 0
print(build_array(9, 1, 1))  # Expected output: 1
← Back to All Questions