07. Build Array Where You Can Find The Maximum Exactly K Comparisons
The problem can be found at the following link: Question Link
My Approach
Define a private function called "solve" with the following parameters:
n
: The remaining number of elements to be placed in the array.m
: The maximum value that can be used to fill an element in the array.k
: The remaining allowed changes to the previously placed value.prev
: The previously placed value in the array.dp
: A three-dimensional vector used for memoization.
Check if
n
is 0 andk
is 0, indicating that we have successfully constructed the array. Return 1 in this case.Check if
k
is less than 0 orn
is less than 0, indicating an invalid state. Return 0 in these cases.Check if the result for the current state (n, k, prev) is already calculated and stored in the memoization table
dp
. If yes, return the stored result.Initialize a variable
ans
to 0 to keep track of the number of valid arrays.Iterate through values from 1 to
m
(inclusive) representing the next element to be placed in the array.If
prev
is less than the current valuei
, recursively call the "solve" function with reducedn
,k
, andprev
updated toi
. Add the result toans
.If
prev
is greater than or equal to the current valuei
, recursively call the "solve" function with reducedn
andk
, keepingprev
unchanged. Add the result toans
.Calculate the final result as
ans % mod
, wheremod
is defined as 1e9+7.Store the calculated result in the memoization table
dp
for the current state (n, k, prev).In the public function "numOfArrays," check if
k
is greater thann
. If yes, return 0 because it's not possible to construct the array with more allowed changes than the remaining elements.Initialize a three-dimensional vector
dp
of size (n+1) x (k+1) x (m+1) with all values set to -1 for memoization.
Time and Auxiliary Space Complexity
Time Complexity:
O(n)
Auxiliary Space Complexity:
O(n)
Code (C++)
class Solution {
private:
int solve(int n, int m, int k, int prev, vector<vector<vector<int>>> &dp){
if(n == 0 && k == 0){
return 1;
}
if(k < 0 || n < 0)
return 0;
if(dp[n][k][prev] != -1)
return dp[n][k][prev];
int ans = 0;
for(int i = 1; i <= m; i++){
if(prev < i)
ans = (ans + solve(n - 1, m, k - 1, i, dp)) % mod;
else
ans = (ans + solve(n - 1, m, k, prev, dp)) % mod;
}
return dp[n][k][prev] = ans % mod;
}
public:
long long mod = 1e9+7;
int numOfArrays(int n, int m, int k) {
if(k > n)
return 0;
vector<vector<vector<int>>> dp(n + 1, vector<vector<int>> (k + 1, vector<int> (m + 1, -1)));
return solve(n, m, k, 0, dp);
}
};
Contribution and Support
For discussions, questions, or doubts related to this solution, please visit our discussion section. We welcome your input and aim to foster a collaborative learning environment.
If you find this solution helpful, consider supporting us by giving a ⭐ star
to the rishabhv12/Daily-Leetcode-Solution repository.
Last updated
Was this helpful?