Count the Number of Arrays with K Matching Adjacent Elements

Hard

Asked by:

26 views

Topics:

Dynamic Programming

You are given three integers n, m, k. A good array arr of size n is defined as follows:

Each element in arr is in the inclusive range [1, m].
Exactly k indices i (where 1 <= i < n) satisfy the condition arr[i - 1] == arr[i].

Return the number of good arrays that can be formed.

Since the answer may be very large, return it modulo 10⁹+ 7.

Example 1:

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

Output: 4

Explanation:

There are 4 good arrays. They are [1, 1, 2], [1, 2, 2], [2, 1, 1] and [2, 2, 1].
Hence, the answer is 4.

Example 2:

Input: n = 4, m = 2, k = 2

Output: 6

Explanation:

The good arrays are [1, 1, 1, 2], [1, 1, 2, 2], [1, 2, 2, 2], [2, 1, 1, 1], [2, 2, 1, 1] and [2, 2, 2, 1].
Hence, the answer is 6.

Example 3:

Input: n = 5, m = 2, k = 0

Output: 2

Explanation:

The good arrays are [1, 2, 1, 2, 1] and [2, 1, 2, 1, 2]. Hence, the answer is 2.

Constraints:

1 <= n <= 10⁵
1 <= m <= 10⁵
0 <= k <= n - 1

Try coding it in LeetCode

Count the Number of Arrays with K Matching Adjacent Elements

Hard

Asked by:

26 views

Topics:

Dynamic Programming

You are given three integers n, m, k. A good array arr of size n is defined as follows:

Each element in arr is in the inclusive range [1, m].
Exactly k indices i (where 1 <= i < n) satisfy the condition arr[i - 1] == arr[i].

Return the number of good arrays that can be formed.

Since the answer may be very large, return it modulo 10⁹+ 7.

Example 1:

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

Output: 4

Explanation:

There are 4 good arrays. They are [1, 1, 2], [1, 2, 2], [2, 1, 1] and [2, 2, 1].
Hence, the answer is 4.

Example 2:

Input: n = 4, m = 2, k = 2

Output: 6

Explanation:

The good arrays are [1, 1, 1, 2], [1, 1, 2, 2], [1, 2, 2, 2], [2, 1, 1, 1], [2, 2, 1, 1] and [2, 2, 2, 1].
Hence, the answer is 6.

Example 3:

Input: n = 5, m = 2, k = 0

Output: 2

Explanation:

The good arrays are [1, 2, 1, 2, 1] and [2, 1, 2, 1, 2]. Hence, the answer is 2.

Constraints:

1 <= n <= 10⁵
1 <= m <= 10⁵
0 <= k <= n - 1

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the range of values within the array, and are negative numbers or zero allowed?
What is the maximum size of the input array `arr` and the value of `k`?
If no arrays with exactly `k` matching adjacent elements exist, what value should I return?
Can you provide a more formal definition of 'matching adjacent elements'? Specifically, are we looking for equality (arr[i] == arr[i+1])?
Does the problem statement require me to count the *number* of arrays given the ability to construct arrays, or is `arr` the array I should evaluate and count the existing adjacent matching elements?

Brute Force Solution

Approach

The brute force method for this array problem is all about trying every possible array and checking if it meets the criteria. We will generate every single possible array combination based on the given inputs. If a created array meets the condition of having exactly 'K' matching adjacent elements, we will increment our count.

Here's how the algorithm would work step-by-step:

First, create all possible arrays using the allowed numbers.
For each array, go through it and check pairs of neighboring numbers.
Count how many pairs of neighboring numbers are identical within that array.
If the count of identical neighboring pairs is exactly equal to 'K', then this array is one of the solutions.
Add one to the total count of solutions if the number of matching adjacent elements is equal to 'K'.
Repeat for every possible array that can be created.
Finally, return the total count of arrays that meet the required condition (having exactly 'K' matching adjacent elements).

Code Implementation

def count_arrays_with_k_matching_adjacent(array_length, allowed_number, target_matches):

    total_arrays = 0

    def generate_all_possible_arrays(current_array):
        nonlocal total_arrays

        if len(current_array) == array_length:
            # Check for the required number of matching adjacent elements

            adjacent_matches_count = 0

            for index in range(len(current_array) - 1):
                if current_array[index] == current_array[index + 1]:
                    adjacent_matches_count += 1

            if adjacent_matches_count == target_matches:
                total_arrays += 1

            return

        # This is where we build out the array
        for number in range(1, allowed_number + 1):
            generate_all_possible_arrays(current_array + [number])

    # Initiate the array generation
    generate_all_possible_arrays([])

    return total_arrays

Big(O) Analysis

Time Complexity

O(m^n * n) – The algorithm generates all possible arrays of length n where each element can be one of m possible values. Therefore, there are m^n possible arrays. For each of these arrays, the algorithm iterates through the array to count the number of matching adjacent elements, which takes O(n) time. Thus, the overall time complexity is O(m^n * n).

Space Complexity

O(maxVal^N) – The brute force method generates all possible arrays of length N, where N is the length of the array and maxVal is the maximum possible value each element can have. To store each generated array, the algorithm needs space proportional to the length of the array (N). Because the number of possible arrays is maxVal^N, the space to store the generated array during evaluation is N, but overall the space for generating all combinations grows with O(maxVal^N). Thus the dominant space usage is driven by storing all generated arrays for processing.

Optimal Solution

Approach

The core idea is to use dynamic programming to avoid recomputing the same subproblems. We build solutions for smaller cases and then combine them to solve the larger problem efficiently. This avoids checking every possible array, significantly speeding up the process.

Here's how the algorithm would work step-by-step:

Imagine you are constructing valid arrays incrementally. Consider how the last element added affects the number of matching adjacent pairs.
We want to remember how many ways we can create valid arrays of a certain length, with a certain number of matching pairs, and ending with a particular value.
So, build a table where each entry represents the number of valid arrays for a given length, a given number of matching pairs, and a given last element.
When adding a new number, check if it matches the previous number. If it does, the number of matching pairs increases.
Sum up the possibilities for each ending number to get the total number of arrays with the desired length and matching pairs.
By storing these intermediate results, we never need to recalculate the same subproblem, which results in a much faster solution.

Code Implementation

def count_arrays_with_k_matching_adjacent(array_length, value_range, target_matches):
    modulo = 10**9 + 7
    # Initialize the dp table
    dp_table = [[[0] * (value_range + 1) for _ in range(target_matches + 1)] \
                for _ in range(array_length + 1)]

    # Base case: arrays of length 1 with no matches.
    for value in range(1, value_range + 1):
        dp_table[1][0][value] = 1

    # Iterate to build solutions for increasing array lengths.
    for current_length in range(2, array_length + 1):
        for current_matches in range(target_matches + 1):
            # Iterate through each possible ending value.
            for current_value in range(1, value_range + 1):
                # Iterate through previous ending values.
                for previous_value in range(1, value_range + 1):
                    if current_value == previous_value:
                        # If values match, matching pair count increases
                        if current_matches > 0:
                            dp_table[current_length][current_matches][current_value] = \
                                (dp_table[current_length][current_matches][current_value] + \
                                dp_table[current_length - 1][current_matches - 1][previous_value]) % modulo
                    else:
                        # Values don't match, matching pair count remains same
                        dp_table[current_length][current_matches][current_value] = \
                            (dp_table[current_length][current_matches][current_value] + \
                            dp_table[current_length - 1][current_matches][previous_value]) % modulo

    # Sum the counts for all possible ending values.
    total_arrays = 0
    for value in range(1, value_range + 1):
        total_arrays = (total_arrays + dp_table[array_length][target_matches][value]) % modulo

    # The result is the total number of valid arrays.
    return total_arrays

Big(O) Analysis

Time Complexity

O(n*k*m) – The dynamic programming solution involves iterating through array lengths up to n, the number of matching adjacent pairs up to k, and the possible values each element can have, up to m. We have a triple nested loop, where the outer loop runs 'n' times, the middle loop runs 'k' times, and the inner loop runs 'm' times (to account for the number of possible ending numbers or values from the array). Therefore, the total number of operations is proportional to n * k * m, resulting in a time complexity of O(n*k*m).

Space Complexity

O(N*K*M) – The dominant space usage comes from the dynamic programming table. According to the explanation, the table stores the number of valid arrays for a given length, a given number of matching pairs, and a given last element. Let N be the length of the array, K be the number of matching adjacent elements, and M be the range of possible values for array elements. The table thus requires space proportional to N * K * M. Therefore, the space complexity is O(N*K*M).

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 if the input array is null or has a length less than 2, as no adjacent pairs can exist.
k is negative	Return 0 or throw an exception, as the problem likely implies k should be a non-negative number of matching pairs.
Array with all identical elements and large k	The number of matching adjacent elements will be n-1, so if k > n-1 return 0, and if k=n-1 return 1.
Array with no matching adjacent elements and k > 0	Return 0, since it's impossible to find k matching adjacent pairs if there are none.
Integer overflow if array size is very large	Use appropriate data types (e.g., long) to store the count of matching pairs to prevent integer overflow.
Large array size impacting performance.	Consider algorithmic complexity; an O(n) solution is optimal but ensure it is efficient in practice by avoiding unnecessary operations.
k equals the size of the input array	Return 0 as it would imply checking past the boundaries of the array.
Very large value of k approaching maximum integer value	Implement checks to ensure k is within reasonable bounds for comparison and prevent potential issues.