Home » leet code » LeetCode 1420: Build Array Where You Can Find The Maximum Exactly K Comparisons

LeetCode 1420: Build Array Where You Can Find The Maximum Exactly K Comparisons

Leave a Comment / By /

LeetCode 1420. Build Array Where You Can Find The Maximum Exactly K Comparisons :Hey there, coding enthusiasts! Welcome back to another exciting coding session. Today’s problem is a treat—literally! We’re going to solve the “Build Array Where You Can Find The Maximum Exactly K Comparisons” or “LeetCode 1420 ‘ 

Understanding the Challenge

Before we delve into the solution, let’s first understand the problem statement. In LeetCode 1420, we are given three integers: n, m, and k. Our goal is to construct an array of length n that contains integers from 1 to m and meets the following criteria:

  1. The maximum element in the array appears exactly k times.
  2. The remaining elements should be as small as possible.

Seems tricky, right? But don’t worry; we’ve got a powerful tool in our toolbox – dynamic programming!

Also Read:Leet Code 2612 Minimum Reverse Operations

The Dynamic Programming Approach

Dynamic programming is a versatile technique that can help us solve complex problems by breaking them down into smaller, more manageable subproblems. For this LeetCode challenge, dynamic programming will be our guiding star. Let’s break down the problem and create a dynamic programming table to help us visualize the process.

1: Create a Dynamic Programming Table

We’ll create a table with dimensions (n+1) x (m+1) x (k+1). Each cell in the table will store the number of valid sequences for that particular state. This table will be the backbone of our dynamic programming approach.

Here’s a visual representation of the table:

n\m\k012…k
0100…0
1111…1
21…
……
n1…

In the table, the rows represent the number of elements we are constructing in the array (n), the columns represent the range of integers we can use in the array (m), and the depth represents the number of times the maximum element has been used (k).

Leet code 206 Reverse Linked List

2: Fill in the Table

We start filling in the table from the top-left corner (when n=0, m=0, and k=0, there’s only one way – an empty array). We then iterate through the table, calculating the number of valid sequences for each state.

The formula for filling the table is as follows:

dp[i][j][k] = dp[i-1][j-1][k-1] + dp[i-1][j][k] * (k)
  • dp[i-1][j-1][k-1] represents the case where we add the maximum element to the array.
  • dp[i-1][j][k] * (k) represents the case where we add any element less than the maximum element to the array.

3: Find the Solution

Once the dynamic programming table is fully populated, we can easily find the solution. The number of valid sequences for n elements with the maximum element appearing exactly k times will be stored in dp[n][m][k].

Leet Code 420 Strong Password Checker 

Codes : Dyanamic Programming approach – LeetCode 1420

Certainly! Here’s the LeetCode 1420 problem solution implemented in C++, Java, Python 3, JavaScript, and Dart.

C++ :DP approach – LeetCode 1420

class Solution {
public:
    int numOfArrays(int n, int m, int k) {
        const int mod = 1e9 + 7;

        vector<vector<int>> dp(m+1, vector<int>(k+1, 0));
        vector<vector<int>> prefix(m+1, vector<int>(k+1, 0));
        vector<vector<int>> prevDp(m+1, vector<int>(k+1, 0));
        vector<vector<int>> prevPrefix(m+1, vector<int>(k+1, 0));

        for (int j = 1; j <= m; j++) {
            prevDp[j][1] = 1;
            prevPrefix[j][1] = j;
        }

        for (int _ = 2; _ <= n; _++) {
            dp.assign(m+1, vector<int>(k+1, 0));
            prefix.assign(m+1, vector<int>(k+1, 0));

            for (int maxNum = 1; maxNum <= m; maxNum++) {
                for (int cost = 1; cost <= k; cost++) {
                    dp[maxNum][cost] = (static_cast<long long>(maxNum) * prevDp[maxNum][cost]) % mod;
                    
                    if (maxNum > 1 && cost > 1) {
                        dp[maxNum][cost] = (dp[maxNum][cost] + prevPrefix[maxNum - 1][cost - 1]) % mod;
                    }
                    
                    prefix[maxNum][cost] = (prefix[maxNum - 1][cost] + dp[maxNum][cost]) % mod;
                }
            }

            prevDp = dp;
            prevPrefix = prefix;
        }

        return prefix[m][k];
    }
};

Java : DP approach – LeetCode 1420

class Solution {
    public int numOfArrays(int n, int m, int k) {
        final int mod = 1_000_000_007;
        
        int[][] dp = new int[m+1][k+1];
        int[][] prefix = new int[m+1][k+1];
        int[][] prevDp = new int[m+1][k+1];
        int[][] prevPrefix = new int[m+1][k+1];

        for (int j = 1; j <= m; j++) {
            prevDp[j][1] = 1;
            prevPrefix[j][1] = j;
        }

        for (int i = 2; i <= n; i++) {
            dp = new int[m+1][k+1];
            prefix = new int[m+1][k+1];

            for (int maxNum = 1; maxNum <= m; maxNum++) {
                for (int cost = 1; cost <= k; cost++) {
                    dp[maxNum][cost] = (int)((long)maxNum * prevDp[maxNum][cost] % mod);
                    
                    if (maxNum > 1 && cost > 1) {
                        dp[maxNum][cost] = (dp[maxNum][cost] + prevPrefix[maxNum - 1][cost - 1]) % mod;
                    }
                    
                    prefix[maxNum][cost] = (prefix[maxNum - 1][cost] + dp[maxNum][cost]) % mod;
                }
            }

            prevDp = dp;
            prevPrefix = prefix;
        }

        return prefix[m][k];
    }
}

Leetcode 1359 Count All Valid Pickup and Delivery

Python 3 : DP approach – LeetCode 1420

class Solution:
    def numOfArrays(self, n: int, m: int, k: int) -> int:
        mod = 10**9 + 7

        dp = [[0] * (k + 1) for _ in range(m + 1)]
        prefix = [[0] * (k + 1) for _ in range(m + 1)]
        prev_dp = [[0] * (k + 1) for _ in range(m + 1)]
        prev_prefix = [[0] * (k + 1) for _ in range(m + 1)]

        for j in range(1, m + 1):
            prev_dp[j][1] = 1
            prev_prefix[j][1] = j

        for _ in range(2, n + 1):
            dp = [[0] * (k + 1) for _ in range(m + 1)]
            prefix = [[0] * (k + 1) for _ in range(m + 1)]

            for max_num in range(1, m + 1):
                for cost in range(1, k + 1):
                    dp[max_num][cost] = (max_num * prev_dp[max_num][cost]) % mod

                    if max_num > 1 and cost > 1:
                        dp[max_num][cost] = (dp[max_num][cost] + prev_prefix[max_num - 1][cost - 1]) % mod

                    prefix[max_num][cost] = (prefix[max_num - 1][cost] + dp[max_num][cost]) % mod

            prev_dp = dp
            prev_prefix = prefix

        return prefix[m][k]

LeetCode 343. Integer Break (Medium)

JavaScript : DP approach – LeetCode 1420

var numOfArrays = function(n, m, k) {
    const mod = 10 ** 9 + 7;

    let dp = new Array(m + 1).fill(0).map(() => new Array(k + 1).fill(0));
    let prefix = new Array(m + 1).fill(0).map(() => new Array(k + 1).fill(0));
    let prevDp = new Array(m + 1).fill(0).map(() => new Array(k + 1).fill(0));
    let prevPrefix = new Array(m + 1).fill(0).map(() => new Array(k + 1).fill(0));

    for (let j = 1; j <= m; j++) {
        prevDp[j][1] = 1;
        prevPrefix[j][1] = j;
    }

    for (let _ = 2; _ <= n; _++) {
        dp = new Array(m + 1).fill(0).map(() => new Array(k + 1).fill(0));
        prefix = new Array(m + 1).fill(0).map(() => new Array(k + 1).fill(0));

        for (let maxNum = 1; maxNum <= m; maxNum++) {
            for (let cost = 1; cost <= k; cost++) {
                dp[maxNum][cost] = (maxNum * prevDp[maxNum][cost]) % mod;

                if (maxNum > 1 && cost > 1) {
                    dp[maxNum][cost] = (dp[maxNum][cost] + prevPrefix[maxNum - 1][cost - 1]) % mod;
                }

                prefix[maxNum][cost] = (prefix[maxNum - 1][cost] + dp[maxNum][cost]) % mod;
            }
        }

        prevDp = dp;
        prevPrefix = prefix;
    }

    return prefix[m][k];
};

Dart : DP approach – LeetCode 1420

class Solution {
  int numOfArrays(int n, int m, int k) {
    final mod = 1000000007;

    var dp = List.generate(m + 1, (i) => List.generate(k + 1, (j) => 0));
    var prefix = List.generate(m + 1, (i) => List.generate(k + 1, (j) => 0));
    var prevDp = List.generate(m + 1, (i) => List.generate(k + 1, (j) => 0));
    var prevPrefix = List.generate(m + 1, (i) => List.generate(k + 1, (j) => 0));

    for (var j = 1; j <= m; j++) {
      prevDp[j][1] = 1;
      prevPrefix[j][1] = j;
    }

    for (var _ = 2; _ <= n; _++) {
      dp = List.generate(m + 1, (i) => List.generate(k + 1, (j) => 0));
      prefix = List.generate(m + 1, (i) => List.generate(k + 1, (j) => 0));

      for (var maxNum = 1; maxNum <= m; maxNum++) {
        for (var cost = 1; cost <= k; cost++) {
          dp[maxNum][cost] = (maxNum * prevDp[maxNum][cost]) % mod;

          if (maxNum > 1 && cost > 1) {
            dp[maxNum][cost] = (dp[maxNum][cost] + prevPrefix[maxNum - 1][cost - 1]) % mod;
          }

          prefix[maxNum][cost] = (prefix[maxNum - 1][cost] + dp[maxNum][cost]) % mod;
        }
      }

      prevDp = dp;
      prevPrefix = prefix;
    }

    return prefix[m][k];
  }
}

Example

Let’s walk through a simple example to solidify our understanding of this dynamic programming approach.

Suppose we have n=3, m=3, and k=2.

  1. We create a dynamic programming table as shown earlier.
  2. We start filling the table, and after populating it, we find that dp[3][3][2] = 3.

So, there are three different valid sequences that meet our criteria for this example.

Conclusion

In this blog post, we’ve tackled the LeetCode 1420 problem by applying a dynamic programming approach. We’ve learned how to construct a dynamic programming table and how to fill it in to find the number of valid sequences. Dynamic programming is a powerful tool in our coding arsenal, and it can be a game-changer in solving complex problems like this one.

So, the next time you encounter a tricky coding challenge, remember to break it down into smaller subproblems, create a dynamic programming table, and conquer it step by step. Happy coding!

FAQs

What is LeetCode 1420?

LeetCode 1420 is a coding challenge that asks you to construct an array of length n with integers from 1 to m, where the maximum element appears exactly k times.

Why is dynamic programming used to solve this problem?

Dynamic programming is used because it allows us to break down the problem into smaller subproblems and build a table to visualize the solution. This approach makes it easier to calculate the number of valid sequences that meet the given criteria.

Can you explain the formula dp[i][j][k] = dp[i-1][j-1][k-1] + dp[i-1][j][k] * (k) in more detail?

Certainly! The formula dp[i][j][k] represents the number of valid sequences for i elements, where the maximum element appears exactly k times, and the range of integers to choose from is [1, j].

  • dp[i-1][j-1][k-1] accounts for the case where we add the maximum element (j) to the array, decreasing i by 1 and k by 1.
  • dp[i-1][j][k] * (k) accounts for the case where we add any element less than the maximum (j) to the array, decreasing only i by 1. We multiply by k because we have k choices for which element to add in this case.

These two cases cover all possibilities, and by summing them up, we get the number of valid sequences for the current state.

Are there other ways to solve this problem?

Yes, there are multiple approaches to solving this problem, including recursion with memoization and mathematical formulas. The dynamic programming approach is one of the most structured and efficient ways to tackle it.

Thank you for joining us on this coding adventure, and we hope this blog post has shed some light on how to tackle LeetCode 1420 with a dynamic programming approach. Happy coding, and may your coding challenges be ever in your favor!

List of Some important Leet code Questions:

Leave a Reply