LeetCode 3339 - Find the Number of K-Even Arrays

We are given three integers: - n, the length of the array. - m, the maximum value allowed in the array. - k, the exact number of special adjacent positions we want. Every element of the array must be chosen from the range [1, m].

leetcodemediumdynamic-programming

LeetCode Problem 3339

Difficulty: 🟡 Medium
Topics: Dynamic Programming

Solution

LeetCode 3339 - Find the Number of K-Even Arrays

Problem Understanding

We are given three integers:

  • n, the length of the array.
  • m, the maximum value allowed in the array.
  • k, the exact number of special adjacent positions we want.

Every element of the array must be chosen from the range [1, m].

For every adjacent pair (arr[i], arr[i + 1]), we evaluate:

$$(arr[i] \times arr[i+1]) - arr[i] - arr[i+1]$$

If this value is even, then index i contributes toward the count.

An array is called k-even if exactly k adjacent indices satisfy this property.

Our task is to count how many arrays of length n are k-even, and return the result modulo:

$$10^9 + 7$$

Key Observation About Parity

Only the parity of the numbers matters.

Let:

  • a = arr[i] mod 2
  • b = arr[i+1] mod 2

Modulo 2,

$$ab - a - b \equiv ab + a + b$$

Checking all parity combinations:

a b ab + a + b (mod 2)
0 0 0
0 1 1
1 0 1
1 1 1

The expression is even only when both numbers are even.

Therefore, the problem becomes:

Count arrays of length n where exactly k adjacent pairs consist of two even numbers.

What the Constraints Tell Us

  • n ≤ 750
  • k ≤ n - 1 ≤ 749
  • m ≤ 1000

A brute force enumeration would require examining m^n arrays, which is completely infeasible.

The constraints strongly suggest a dynamic programming solution with complexity around O(nk).

Important Edge Cases

When m = 1, only the value 1 is available, which is odd. No adjacent pair can ever be an even-even pair.

When k = 0, we count arrays that avoid every even-even adjacency.

When k = n - 1, every adjacent pair must be even-even, which forces every element in the array to be even.

When there are no even numbers in [1, m], every valid array automatically has zero even-even pairs.

Approaches

Brute Force

A straightforward approach is to generate every possible array of length n.

For each array, we would inspect all n - 1 adjacent pairs and count how many satisfy the condition.

If the count equals k, we include the array in the answer.

This approach is correct because it explicitly checks every possible array. However, it is far too slow.

There are m^n possible arrays, which becomes astronomically large even for small inputs.

Optimal Dynamic Programming

The crucial observation is that only parity matters.

Let:

  • E = number of even values in [1, m]
  • O = number of odd values in [1, m]

We do not care which even number was chosen, only whether the chosen number is even or odd.

While building the array from left to right, we need to know:

  • how many even-even pairs have been created so far,
  • whether the last element is even or odd.

This naturally leads to a dynamic programming state.

For every new element:

  • Odd after odd creates no new even-even pair.
  • Odd after even creates no new even-even pair.
  • Even after odd creates no new even-even pair.
  • Even after even creates exactly one new even-even pair.

This gives an O(nk) solution.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(m^n · n) O(n) Enumerates every array
Optimal DP O(nk) O(k) Tracks parity and number of even-even pairs

Algorithm Walkthrough

Step 1: Count Even and Odd Values

Let:

evenCount = m // 2
oddCount = m - evenCount

These are the numbers of available even and odd values.

Step 2: Define DP States

Maintain two arrays:

  • dpEven[j] = number of arrays built so far that end with an even number and contain exactly j even-even pairs.
  • dpOdd[j] = number of arrays built so far that end with an odd number and contain exactly j even-even pairs.

Step 3: Initialize Length 1

For arrays of length 1:

  • Any even value creates an array ending in even.
  • Any odd value creates an array ending in odd.

Therefore:

dpEven[0] = evenCount
dpOdd[0] = oddCount

Step 4: Extend the Array

For every new position:

  1. Even → Even

Creates one new even-even pair. 2. Even → Odd

Creates no new even-even pair. 3. Odd → Even

Creates no new even-even pair. 4. Odd → Odd

Creates no new even-even pair.

The transition formulas are:

newEven[j] += dpOdd[j] * evenCount
newEven[j+1] += dpEven[j] * evenCount

newOdd[j] += dpOdd[j] * oddCount
newOdd[j] += dpEven[j] * oddCount

All operations are performed modulo 1e9+7.

Step 5: Repeat Until Length n

Perform the transition n - 1 times.

Step 6: Return the Answer

The final answer is:

dpEven[k] + dpOdd[k]

modulo 1e9+7.

Why it Works

The DP maintains a complete description of every partial array using two pieces of information:

  • the number of even-even pairs already formed,
  • the parity of the last element.

Any future contribution depends only on the parity of the last element and the parity of the newly added element. Therefore no additional information is needed.

Since every valid extension is counted exactly once, and every possible array corresponds to exactly one sequence of transitions, the DP counts all k-even arrays correctly.

Python Solution

class Solution:
    def countOfArrays(self, n: int, m: int, k: int) -> int:
        MOD = 1_000_000_007

        even_count = m // 2
        odd_count = m - even_count

        dp_even = [0] * (k + 1)
        dp_odd = [0] * (k + 1)

        dp_even[0] = even_count
        dp_odd[0] = odd_count

        for _ in range(1, n):
            next_even = [0] * (k + 1)
            next_odd = [0] * (k + 1)

            for pairs in range(k + 1):
                even_ways = dp_even[pairs]
                odd_ways = dp_odd[pairs]

                if even_ways:
                    next_odd[pairs] = (
                        next_odd[pairs]
                        + even_ways * odd_count
                    ) % MOD

                    if pairs < k:
                        next_even[pairs + 1] = (
                            next_even[pairs + 1]
                            + even_ways * even_count
                        ) % MOD

                if odd_ways:
                    next_even[pairs] = (
                        next_even[pairs]
                        + odd_ways * even_count
                    ) % MOD

                    next_odd[pairs] = (
                        next_odd[pairs]
                        + odd_ways * odd_count
                    ) % MOD

            dp_even = next_even
            dp_odd = next_odd

        return (dp_even[k] + dp_odd[k]) % MOD

Implementation Explanation

The code first computes how many even and odd values are available in the range [1, m].

Two DP arrays are maintained. One tracks arrays ending with an even value, while the other tracks arrays ending with an odd value.

For every new position, fresh arrays next_even and next_odd are constructed. The four possible parity transitions are applied. The only transition that increases the number of even-even pairs is the even-to-even transition.

After processing all positions, the answer is obtained by summing the states ending in either parity with exactly k even-even pairs.

Go Solution

func countOfArrays(n int, m int, k int) int {
	const MOD int64 = 1_000_000_007

	evenCount := m / 2
	oddCount := m - evenCount

	dpEven := make([]int64, k+1)
	dpOdd := make([]int64, k+1)

	dpEven[0] = int64(evenCount)
	dpOdd[0] = int64(oddCount)

	for pos := 1; pos < n; pos++ {
		nextEven := make([]int64, k+1)
		nextOdd := make([]int64, k+1)

		for pairs := 0; pairs <= k; pairs++ {
			evenWays := dpEven[pairs]
			oddWays := dpOdd[pairs]

			if evenWays != 0 {
				nextOdd[pairs] = (nextOdd[pairs] +
					evenWays*int64(oddCount)) % MOD

				if pairs < k {
					nextEven[pairs+1] = (nextEven[pairs+1] +
						evenWays*int64(evenCount)) % MOD
				}
			}

			if oddWays != 0 {
				nextEven[pairs] = (nextEven[pairs] +
					oddWays*int64(evenCount)) % MOD

				nextOdd[pairs] = (nextOdd[pairs] +
					oddWays*int64(oddCount)) % MOD
			}
		}

		dpEven = nextEven
		dpOdd = nextOdd
	}

	return int((dpEven[k] + dpOdd[k]) % MOD)
}

Go Specific Notes

The Go implementation uses int64 for all DP values because intermediate multiplication can exceed the range of a 32-bit integer.

Slices are used for the rolling DP arrays. At each iteration, new slices are allocated and then replace the old ones, exactly mirroring the rolling-array approach used in Python.

Worked Examples

Example 1

Input:

n = 3
m = 4
k = 2

Available values:

Even: {2, 4} => E = 2
Odd:  {1, 3} => O = 2

Initial state:

EE Pairs End Even End Odd
0 2 2

After length 2:

EE Pairs End Even End Odd
0 4 8
1 4 0

After length 3:

EE Pairs End Even End Odd
0 16 24
1 16 8
2 8 0

Answer:

dpEven[2] + dpOdd[2]
= 8 + 0
= 8

Example 2

Input:

n = 5
m = 1
k = 0

We have:

E = 0
O = 1

Every element must be 1.

The only array is:

[1,1,1,1,1]

No even-even pair exists.

Answer:

1

Example 3

Input:

n = 7
m = 7
k = 5

We have:

E = 3
O = 4

Running the DP yields:

5832

which matches the expected output.

Complexity Analysis

Measure Complexity Explanation
Time O(nk) For each of n-1 positions we process all pair counts 0..k
Space O(k) Only two rolling DP arrays are stored

The algorithm never depends directly on m beyond counting how many even and odd numbers exist. Therefore the running time is determined solely by n and k. With n ≤ 750 and k ≤ 749, this is easily fast enough.

Test Cases

sol = Solution()

assert sol.countOfArrays(3, 4, 2) == 8          # example 1
assert sol.countOfArrays(5, 1, 0) == 1          # example 2
assert sol.countOfArrays(7, 7, 5) == 5832       # example 3

assert sol.countOfArrays(1, 1, 0) == 1          # single element
assert sol.countOfArrays(1, 10, 0) == 10        # any single value works

assert sol.countOfArrays(2, 2, 1) == 1          # only [2,2]
assert sol.countOfArrays(2, 2, 0) == 3          # all others

assert sol.countOfArrays(3, 2, 2) == 1          # [2,2,2]
assert sol.countOfArrays(3, 1, 1) == 0          # no even numbers

assert sol.countOfArrays(4, 3, 3) == 0          # impossible to get 3 EE pairs
                                                # with only one even value available

assert sol.countOfArrays(2, 1000, 0) > 0        # large m
assert sol.countOfArrays(750, 1, 0) == 1        # maximum n, only odd value

Test Summary

Test Why
(3,4,2) Official example
(5,1,0) Official example
(7,7,5) Official example
(1,1,0) Smallest input
(1,10,0) Length one, no adjacency
(2,2,1) Exactly one EE pair
(2,2,0) Complement of previous case
(3,2,2) Maximum possible EE count
(3,1,1) No even numbers available
(4,3,3) Impossible configuration
(2,1000,0) Large value range
(750,1,0) Maximum length edge case

Edge Cases

Length One Arrays

When n = 1, there are no adjacent pairs at all. Therefore every valid array automatically has zero even-even pairs. A common bug is to assume at least one transition exists. The DP initialization handles this correctly because the answer is read directly from the length-one states.

No Even Numbers Available

When m = 1, the only value is 1, which is odd. In this situation, an even-even pair can never occur. The transitions involving even values contribute zero because evenCount = 0. The DP naturally collapses to counting only odd-ending arrays.

Maximum Possible Pair Count

The largest possible number of even-even pairs is n - 1, achieved only when every element is even. A common mistake is to allow transitions beyond k. The implementation explicitly checks pairs < k before creating a new even-even pair, preventing out-of-range states and ensuring correctness.

Impossible Configurations

Some (n, m, k) combinations cannot produce the requested number of even-even pairs. For example, if there are no even numbers available but k > 0, the answer must be zero. The DP automatically returns zero because no state with positive pair count can ever be reached.