How do you solve Construct the Array using the Two-Bucket Counting DP (Optimal) approach?

When to use it: The answer they want. Phrase it as 'count ends-at-x vs ends-elsewhere with combinatorial transitions'. Bucket the end-value into two equivalence classes and count each class in bulk. **States.** After fixing the first `i` elements, let `same` be the number of valid arrays whose `i`-th element equals `x`, and `diff` the number whose `i`-th element is some value other than `x`. Every array of length `i` falls into exactly one bucket, so `same + diff` is the total count of valid length-`i` prefixes. **Transition to length i+1.** - *Landing on x* (`new_same`): the next element is `x`, which must differ from the current one, so the current element cannot be `x`. Only `diff` arrays qualify, and there's exactly one value (`x`) to place → `new_same = diff`. - *Landing on a non-x value* (`new_diff`): - From a `same` array (current element is `x`): any value except `x` is both legal (differs from `x`) and non-x → `k − 1` choices. - From a `diff` array (current element is some `y ≠ x`): the next value must differ from `y` and must not be `x`, so we exclude two values (`y` and `x`) → `k − 2` choices. - Total: `new_diff = same·(k−1) + diff·(k−2)`. **Base case.** The array starts at `a[0] = 1`. So the length-1 array is `[1]`: it ends at `x` iff `x == 1`. Set `same = (x == 1 ? 1 : 0)`, `diff = (x == 1 ? 0 : 1)`. **Modular discipline.** Counts blow up like `(k−1)ⁿ`. Apply `% MOD` after the addition *and* keep the multiplications in 64-bit (`long`) before reducing, since `same·(k−1)` with both near `10⁹` reaches `~10¹⁸` — fine for `long`, overflow for `int`. Add the two terms, then reduce. **Answer.** After iterating up to length `n`, `same` holds the number of arrays ending at `x` — exactly what the problem asks. Time complexity: O(n). Space complexity: O(1).

Loading…

mediumDynamic ProgrammingSometimes asked

Construct the Array

Q: How do you solve Construct the Array using the Brute Force — Recurse over Every Next Value approach?

When to use it: State it to expose the branching and the overlapping subproblems, then bucket and memoize. The literal interpretation: grow the array one slot at a time, branching on every legal next value. **The recursion.** Define `f(i, prev)` = the number of ways to complete the array from position `i` given that position `i−1` holds value `prev`. At position `i` try every value `v ≠ prev` in `[1, k]` and sum `f(i+1, v)`. The base case at `i = n` returns 1 if `prev == x`, else 0. Start with `f(1, 1)` since `a[0] = 1` is fixed. **Why it counts correctly.** Each root-to-leaf path is a distinct valid array (consecutive-different is enforced by `v ≠ prev`), and we tally only those ending at `x`. No array is counted twice because the choices at each position are disjoint. **Why it's hopeless at scale.** Each position fans out to `k−1` children, so the tree has `(k−1)ⁿ` leaves — for `n = k = 10⁵` this is beyond astronomical. Yet `f(i, prev)` depends only on `i` and on *whether `prev` equals `x`* (all non-x previous values give the identical count). That means there are really only `2n` distinct subproblems hiding behind exponentially many calls — the cue to bucket and memoize. Time complexity: O(kⁿ). Space complexity: O(n).

Q: How do you solve Construct the Array using the Closed Form via Modular Inverse — O(log n) approach?

When to use it: Mention for very large n: a direct formula using fast exponentiation and Fermat's inverse. The two-bucket recurrence is linear, so it has a closed form — useful when `n` is enormous and even O(n) is too slow. **The formula.** Building the array is equivalent to counting walks of length `n−1` on the complete graph `K_k` (every value adjacent to every *other* value) starting at the vertex `1`: - Ending at a vertex different from the start (`x ≠ 1`): `((k−1)^(n−1) − (−1)^(n−1)) / k`. - Ending back at the start (`x = 1`): `((k−1)^(n−1) + (k−1)·(−1)^(n−1)) / k`. **Why a sign term.** The number of closed vs open walks oscillates with parity; the `(−1)^(n−1)` correction captures that the simple `(k−1)^(n−1)` over-counts or under-counts depending on whether `n−1` is even or odd. **Dividing under a modulus.** You can't just divide by `k` in modular arithmetic — instead multiply by `k`'s modular inverse. Since `MOD = 1e9+7` is prime, Fermat's little theorem gives `k⁻¹ ≡ k^(MOD−2) (mod MOD)`. Compute `(k−1)^(n−1) mod MOD` and `k^(MOD−2) mod MOD` with fast exponentiation, combine, and normalise any negative intermediate by adding `MOD`. **When to prefer it.** The two-bucket DP is simpler and plenty fast for `n ≤ 10⁵`. Reach for the closed form only when `n` can be astronomically large (e.g. given as an exponent) and you need sub-linear time. The trade-off is the subtlety of the parity sign and the modular-inverse machinery. Time complexity: O(log n). Space complexity: O(1).

Dynamic Programming · 33 of 44 · 11 min

Consider an array of n integers, where each element is between 1 and k (inclusive). You must build such an array subject to:

1
The first element is 1 (a[0] = 1).
2
The last element is x (a[n−1] = x).
3
Every pair of consecutive elements is different (a[i] ≠ a[i−1]).

Return the number of such arrays, modulo 1e9 + 7.

In plain English

Picture building the array left to right. Each new element just has to differ from the one before it — nothing else couples positions. So at every step the only thing about the past that matters is whether the current element is the target value x or not. That two-way distinction is enough to count all continuations, and the counts multiply by how many legal next-values each class has.

Examples

Example 1

Input: n = 4, k = 3, x = 2
Output: 3
Note: Arrays of length 4 starting at 1, ending at 2, no equal neighbours: [1,2,1,2], [1,2,3,2], [1,3,1,2]. Exactly 3.

Example 2

Input: n = 5, k = 4, x = 2
Output: 20
Note: The two-bucket recurrence yields same = 20 after 5 steps (verified by direct enumeration).

Example 3

Input: n = 3, k = 3, x = 1
Output: 2
Note: Ending back at 1: [1,2,1] and [1,3,1]. Two arrays.

Constraints

1 ≤ n ≤ 10⁵
1 ≤ k ≤ 10⁵
1 ≤ x ≤ k
Answer is taken modulo 1 000 000 007

Clarifying questions4First question: Can the first element be something other than 1?Explore questions

Q1.Can the first element be something other than 1?
No — a[0] is fixed at 1. That fixes the base case: a length-1 array is just [1], which 'ends at x' only if x = 1.
Q2.Must every value 1..k actually appear?
No. Values may repeat (as long as not adjacent) and some may never appear. We're counting all arrays satisfying the three rules.
Q3.Why only two states instead of k?
Because all values except x are interchangeable for counting purposes — the number of ways to continue from any non-x value is identical. Collapsing them into one bucket gives O(n) instead of O(n·k).
Q4.Why is the modulus applied so aggressively?
Counts grow like (k−1)ⁿ, astronomically large. The product same·(k−1) can exceed 10¹⁴, so reduce after every add and multiply to stay in range and keep the answer exact mod 1e9+7.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Count arrays of length n with values in [1, k], where a[0] = 1, a[n−1] = x, and consecutive elements differ. Track two counts: `same` = number of valid prefixes whose current element equals the target x, and `diff` = number whose current element is anything except x. The transitions are pure combinatorics: to land on x next you must come from a non-x element (diff ways), and to land on a non-x element you can come from an x-element via any of (k−1) choices or from a non-x element via (k−2) choices (excluding both x and the current value). Take everything mod 1e9+7. Answer = same after n steps. O(n) time, O(1) space.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you bucket the k possible end-values into two equivalence classes (x vs not-x) and write a correct combinatorial recurrence, applying the modulus at every step.

Where candidates slip

Tracking k separate counts (O(n·k) and unnecessary), getting the (k−1) vs (k−2) multipliers backwards, or forgetting to mod the multiplications and overflowing.

How to stand out

Derive the two-class recurrence from first principles (why k−1 and why k−2), then mention the O(log n) closed form via modular inverse for huge n.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Recurse over Every Next Value	`O(kⁿ)`	`O(n)`	State it to expose the branching and the overlapping subproblems, then bucket and memoize.	Read
2	Two-Bucket Counting DP (Optimal)Optimal	`O(n)`	`O(1)`	The answer they want. Phrase it as 'count ends-at-x vs ends-elsewhere with combinatorial transitions'.	Read
3	Closed Form via Modular Inverse — O(log n)	`O(log n)`	`O(1)`	Mention for very large n: a direct formula using fast exponentiation and Fermat's inverse.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.Explore the full tree

Two value-classes and their transitions

How to read it:All non-x values collapse into one bucket; arrows carry the combinatorial multipliers.

Rendering diagram…

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 3

Brute Force — Recurse over Every Next Value

TimeO(kⁿ)SpaceO(n)

State it to expose the branching and the overlapping subproblems, then bucket and memoize.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Build the array position by position. At each step, try every value 1..k that differs from the previous element, and recurse.

2Hint 2Explore hint

Count an array only when you reach length n with the last value equal to x.

3Hint 3Explore hint

There are up to (k−1) choices per step → (k−1)ⁿ leaves. But the count of continuations depends only on (position, previous value) — heavily overlapping.

A · Core idea

The literal interpretation: grow the array one slot at a time, branching on every legal next value.

The recursion. Define f(i, prev) = the number of ways to complete the array from position i given that position i−1 holds value prev. At position i try every value v ≠ prev in [1, k] and sum f(i+1, v). The base case at i = n returns 1 if prev == x, else 0. Start with f(1, 1) since a[0] = 1 is fixed.

Why it counts correctly. Each root-to-leaf path is a distinct valid array (consecutive-different is enforced by v ≠ prev), and we tally only those ending at x. No array is counted twice because the choices at each position are disjoint.

Why it's hopeless at scale. Each position fans out to k−1 children, so the tree has (k−1)ⁿ leaves — for n = k = 10⁵ this is beyond astronomical. Yet f(i, prev) depends only on i and on whether `prev` equals `x` (all non-x previous values give the identical count). That means there are really only 2n distinct subproblems hiding behind exponentially many calls — the cue to bucket and memoize.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

n = 3, k = 3, x = 1

Interactive diagram

Branching on every legal next value

pos 1 from prev=1

Active call / nodeSupporting contextReturned stateNot active

States differing only by a non-x previous value are identical — the redundancy memoization removes.

Final result2

C · Code with teaching comments

Reference implementation previewpublic int countArray(int n, int k, int x) { return f(1, 1, n, k, x); } private int f(int i, int prev, int n, int k, int x) {Explore the full code

solution.javaJava

Brute Force — Recurse over Every Next Value — reference

3 teaching notes

1
public int countArray(int n, int k, int x) {
2
    return f(1, 1, n, k, x);
3
}
4
 
5
private int f(int i, int prev, int n, int k, int x) {
6
    // Completed array: counts only if it ends at the target x.
7
    if (i == n) return prev == x ? 1 : 0;
8
    long ways = 0;
9
    for (int v = 1; v <= k; v++) {
10
        if (v != prev) ways += f(i + 1, v, n, k, x);
11
    }
12
    // Reduce mod the prime; exponential time means this never finishes for large n.
13
    return (int) (ways % 1_000_000_007L);
14
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.14 lines

D · Why it works and complexityO(kⁿ) timeO(n) spaceOpen the invariant and proofExplore the proof

The count of continuations from a position depends on the previous value only through 'is it x or not'. Recognising that all non-x values are interchangeable collapses k branches' worth of distinct states into just two — turning O(kⁿ) into O(n).

ComplexityO(kⁿ) time, O(n) space — Up to (k−1) branches at each of n positions gives O(kⁿ) leaves; recursion depth O(n).

E · Edge cases and pitfalls3Tracking the exact previous value as state — k× more states than needed.Explore edge cases

Pitfalls

Tracking the exact previous value as state — k× more states than needed.
Forgetting the modulus, overflowing the running sum.
Running it for n, k = 10⁵ — (k−1)ⁿ never returns.

03.2

Approach 2 of 3 · Optimal

Two-Bucket Counting DP (Optimal)

TimeO(n)SpaceO(1)

The answer they want. Phrase it as 'count ends-at-x vs ends-elsewhere with combinatorial transitions'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Collapse the k end-values into two classes: `same` = arrays whose current last element is x, `diff` = arrays whose last element is anything but x.

2Hint 2Explore hint

To extend onto x: the previous element must not be x → new_same = diff. To extend onto a non-x value: from an x-element you have (k−1) non-x targets; from a non-x element you exclude both x and the current value → (k−2). So new_diff = same·(k−1) + diff·(k−2).

3Hint 3Explore hint

Base case from a[0]=1: same = (x==1), diff = (x!=1). Iterate to length n, mod everything, answer = same.

A · Core idea

Bucket the end-value into two equivalence classes and count each class in bulk.

States. After fixing the first i elements, let same be the number of valid arrays whose i-th element equals x, and diff the number whose i-th element is some value other than x. Every array of length i falls into exactly one bucket, so same + diff is the total count of valid length-i prefixes.

Transition to length i+1.

Landing on x (new_same): the next element is x, which must differ from the current one, so the current element cannot be x. Only diff arrays qualify, and there's exactly one value (x) to place → new_same = diff.
Landing on a non-x value (new_diff):
- From a same array (current element is x): any value except x is both legal (differs from x) and non-x → k − 1 choices.
- From a diff array (current element is some y ≠ x): the next value must differ from y and must not be x, so we exclude two values (y and x) → k − 2 choices.
- Total: new_diff = same·(k−1) + diff·(k−2).

Base case. The array starts at a[0] = 1. So the length-1 array is [1]: it ends at x iff x == 1. Set same = (x == 1 ? 1 : 0), diff = (x == 1 ? 0 : 1).

Modular discipline. Counts blow up like (k−1)ⁿ. Apply % MOD after the addition and keep the multiplications in 64-bit (long) before reducing, since same·(k−1) with both near 10⁹ reaches ~10¹⁸ — fine for long, overflow for int. Add the two terms, then reduce.

Answer. After iterating up to length n, same holds the number of arrays ending at x — exactly what the problem asks.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

n = 4, k = 3, x = 2

Array state

len 1

same=0, diff=1

[0]

[1]

Current pointerResolved stateNot processed

Final result3

C · Code with teaching comments

solution.javaJava

Two-Bucket Counting DP (Optimal) — optimal

4 teaching notes

1
public int countArray(int n, int k, int x) {
2
    final long MOD = 1_000_000_007L;
3
    // Base case: the length-1 array [1] ends at x only when x is 1.
4
    long same = (x == 1) ? 1 : 0;
5
    long diff = (x == 1) ? 0 : 1;
6
    for (int i = 2; i <= n; i++) {
7
        // Only a non-x element can be followed by x.
8
        long newSame = diff % MOD;
9
        // (k−1) from an x-element, (k−2) from a non-x element; mod each product.
10
        long newDiff = (same * (k - 1) % MOD + diff * (k - 2) % MOD) % MOD;
11
        same = newSame;
12
        diff = newDiff;
13
    }
14
    // Arrays ending at x after n elements.
15
    return (int) (same % MOD);
16
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.16 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

The k values aren't all distinct for counting — only the target x is special. Splitting into 'is x' / 'is not x' is the equivalence-class reduction that powers the whole solution; the (k−1) vs (k−2) multipliers fall straight out of 'how many legal next values does each class have'.

ComplexityO(n) time, O(1) space — One loop of n−1 steps, each doing O(1) modular arithmetic → O(n) time. Two rolling counters → O(1) space.

E · Edge cases and pitfalls7n = 1, x = 1 — Loop never runs; same=1 → answer 1 (the array [1]).Explore edge cases

Edge cases handled

n = 1, x = 1Loop never runs; same=1 → answer 1 (the array [1]).
n = 1, x = 2same=0; answer 0 — a length-1 array can only end at 1.
n = 3, k = 3, x = 1same toggles back: len2 same=0 diff=2... ends same=2 → [1,2,1],[1,3,1].
k = 1k−2 = −1; only n=1,x=1 is valid → 1, all longer arrays impossible (no different neighbour).

Pitfalls

Swapping (k−1) and (k−2) — the x-element class has one more legal target than the non-x class.
Using int for the products — same·(k−1) overflows; use long and mod each factor.
Mis-seeding the base case (e.g. same=1 regardless of x) — a[0]=1 dictates it.

03.3

Approach 3 of 3

Closed Form via Modular Inverse — O(log n)

TimeO(log n)SpaceO(1)

Mention for very large n: a direct formula using fast exponentiation and Fermat's inverse.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The recurrence has a closed form. Walks of length n−1 on the complete graph Kₖ from a fixed start: the count splits by whether the end equals the start's value class.

2Hint 2Explore hint

If x ≠ 1: answer = ((k−1)^(n−1) − (−1)^(n−1)) / k. If x = 1: answer = ((k−1)^(n−1) + (k−1)·(−1)^(n−1)) / k.

3Hint 3Explore hint

Division mod a prime is multiplication by the modular inverse: divide by k using k^(MOD−2) (Fermat's little theorem).

A · Core idea

The two-bucket recurrence is linear, so it has a closed form — useful when n is enormous and even O(n) is too slow.

The formula. Building the array is equivalent to counting walks of length n−1 on the complete graph K_k (every value adjacent to every other value) starting at the vertex 1:

Ending at a vertex different from the start (x ≠ 1): ((k−1)^(n−1) − (−1)^(n−1)) / k.
Ending back at the start (x = 1): ((k−1)^(n−1) + (k−1)·(−1)^(n−1)) / k.

Why a sign term. The number of closed vs open walks oscillates with parity; the (−1)^(n−1) correction captures that the simple (k−1)^(n−1) over-counts or under-counts depending on whether n−1 is even or odd.

Dividing under a modulus. You can't just divide by k in modular arithmetic — instead multiply by k's modular inverse. Since MOD = 1e9+7 is prime, Fermat's little theorem gives k⁻¹ ≡ k^(MOD−2) (mod MOD). Compute (k−1)^(n−1) mod MOD and k^(MOD−2) mod MOD with fast exponentiation, combine, and normalise any negative intermediate by adding MOD.

When to prefer it. The two-bucket DP is simpler and plenty fast for n ≤ 10⁵. Reach for the closed form only when n can be astronomically large (e.g. given as an exponent) and you need sub-linear time. The trade-off is the subtlety of the parity sign and the modular-inverse machinery.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

n = 4, k = 3, x = 2 (x ≠ 1)

Interactive diagram

Closed form pipeline

power

Active call / nodeSupporting contextReturned stateNot active

Exponentiate, sign-correct, then divide by k via modular inverse.

Final result3

C · Code with teaching comments

Reference implementation previewpublic int countArray(int n, int k, int x) { final long MOD = 1_000_000_007L; long base = power(k - 1, n - 1, MOD); long sign = ((n - 1) % 2 == 0) ? 1 : MOD - 1; // +1 or -1 mod p long numerator;Explore the full code

solution.javaJava

Closed Form via Modular Inverse — O(log n) — reference

4 teaching notes

1
public int countArray(int n, int k, int x) {
2
    final long MOD = 1_000_000_007L;
3
    // (k−1)^(n−1) via fast modular exponentiation — O(log n).
4
    long base = power(k - 1, n - 1, MOD);
5
    long sign = ((n - 1) % 2 == 0) ? 1 : MOD - 1; // +1 or -1 mod p
6
    long numerator;
7
    if (x == 1) {
8
        numerator = (base + (long) (k - 1) % MOD * sign) % MOD;
9
    } else {
10
        numerator = (base - sign % MOD + MOD) % MOD;
11
    }
12
    long invK = power(k, MOD - 2, MOD); // Fermat inverse
13
    // Multiply by the inverse to 'divide by k' under the modulus.
14
    return (int) (numerator * invK % MOD);
15
}
16
 
17
private long power(long b, long e, long mod) {
18
    b %= mod;
19
    long r = 1;
20
    while (e > 0) {
21
        if ((e & 1) == 1) r = r * b % mod;
22
        b = b * b % mod;
23
        e >>= 1;
24
    }
25
    return r;
26
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.26 lines

D · Why it works and complexityO(log n) timeO(1) spaceOpen the invariant and proofExplore the proof

A linear two-state recurrence is a 2×2 matrix power, which always admits a closed form. Here the eigenstructure of K_k yields the clean (k−1)^(n−1) term plus a parity correction — and the modular inverse is just how you 'divide by k' inside a prime field.

ComplexityO(log n) time, O(1) space — Fast modular exponentiation for (k−1)^(n−1) and for the inverse of k each take O(log n) (or O(log MOD)) multiplications → O(log n) total.

E · Edge cases and pitfalls6n = 4, k = 3, x = 1 — ((2)³ + 2·(−1)) / 3 = (8−2)/3 = 2 — matches enumeration.Explore edge cases

Edge cases handled

n = 4, k = 3, x = 1((2)³ + 2·(−1)) / 3 = (8−2)/3 = 2 — matches enumeration.
n = 100, k = 100, x = 1Closed form gives 758049401, identical to the O(n) DP.
k = 1Modular inverse of 1 is 1; formula degenerates correctly for the trivial single-value case.

Pitfalls

Forgetting to add MOD before reducing a subtraction — produces a negative result.
Using floating-point division by k instead of the modular inverse — loses exactness.
Getting the parity sign or the x==1 vs x≠1 branch wrong — the two cases differ.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic int countArray(int n, int k, int x) { final long MOD = 1_000_000_007L; long same = (x == 1) ? 1 : 0; long diff = (x == 1) ? 0 : 1; for (int i = 2; i <= n; i++) {Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Tracking every value separately

All non-x values are interchangeable for counting. Keeping k counters is O(n·k) and needless; two buckets suffice.

Explore the code comparison

Don't write this

dp = [[0] * (k + 1) for _ in range(n + 1)]
# fills k columns per row — O(n*k)

Write this instead

same, diff = (x == 1), (x != 1)
for _ in range(2, n + 1):
    same, diff = diff, (same * (k - 1) + diff * (k - 2)) % MOD

Wrong multipliers

From an x-element there are k−1 non-x targets; from a non-x element you also exclude the current value, leaving k−2. Swapping them miscounts.

Explore the code comparison

Don't write this

newDiff = (same * (k - 2) + diff * (k - 1)) % MOD;  // swapped

Write this instead

newDiff = (same * (k - 1) % MOD + diff * (k - 2) % MOD) % MOD;

Overflow on the products

same and (k−1) can each be near 10⁹; their product is ~10¹⁸, overflowing int and risking overflow if you add two such products before reducing.

Explore the code comparison

Don't write this

int newDiff = same * (k - 1) + diff * (k - 2);  // int overflow

Write this instead

long newDiff = (same * (k - 1) % MOD + diff * (k - 2) % MOD) % MOD;

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Two-bucket counting DP (ends-at-x vs ends-elsewhere), modular

Code pattern to memorize

MOD = 1e9+7
same, diff = (1 if x==1 else 0), (0 if x==1 else 1)   # length-1: a[0]=1
for i in 2..n:
    new_same = diff                       # only a non-x can step onto x
    new_diff = same*(k-1) + diff*(k-2)     # step onto a non-x value
    same, diff = new_same % MOD, new_diff % MOD
answer = same

Rules to remember

1Bucket states by value class, not by value: 'equals x' vs 'not x'. All non-x values behave identically, so one count suffices for the whole bucket.
2new_same = diff: you can only arrive at x from something that isn't x (consecutive must differ), and there's exactly one value x to land on.
3new_diff = same·(k−1) + diff·(k−2): from an x-element any of the other (k−1) values is non-x; from a non-x element you exclude both the current value and x → (k−2).
4Reduce every arithmetic step mod 1e9+7, including the multiplications — products of two ~1e9 counts overflow 32-bit and even flirt with 64-bit if you batch them.
5Seed the base case from a[0] = 1: if x == 1 the length-1 array already ends at x (same=1), otherwise it ends elsewhere (diff=1).

Use this pattern when

Count sequences/arrays under adjacency constraints (consecutive differ, no two equal, etc.)
States collapse into a few equivalence classes you can count in bulk
Answer required modulo a large prime → modular counting DP
Walks on a complete-graph-like structure with fixed start and end

Choose another pattern when

You must enumerate or output the arrays, not count them → backtracking, not DP
Constraints couple non-adjacent positions arbitrarily → richer state needed
Values aren't interchangeable (each has distinct rules) → can't bucket into 2 classes
No modulus and n is tiny → a closed-form or direct formula may be simpler

Interview takeaway

When counting constrained sequences, group states into equivalence classes you can count together — here just 'ends at x' and 'ends elsewhere'. Two rolling counters and careful modular arithmetic turn an exponential enumeration into an O(n) recurrence.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternModular counting DP with equivalence-class state compression. When counting constrained sequences, bucket states into a few classes you can count in bulk (here ends-at-x vs ends-elsewhere). The linear recurrence also yields an O(log n) closed form via modular inverse. Same counting mindset as Climbing Stairs and Decode Ways.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Same pattern

←

Candies

Continue · Next problem

Equal

mediumDynamic ProgrammingSometimes asked

Construct the Array

Dynamic Programming · 33 of 44 · 11 min

Consider an array of n integers, where each element is between 1 and k (inclusive). You must build such an array subject to:

1
The first element is 1 (a[0] = 1).
2
The last element is x (a[n−1] = x).
3
Every pair of consecutive elements is different (a[i] ≠ a[i−1]).

Return the number of such arrays, modulo 1e9 + 7.

In plain English

Examples

Example 1

Input: n = 4, k = 3, x = 2
Output: 3
Note: Arrays of length 4 starting at 1, ending at 2, no equal neighbours: [1,2,1,2], [1,2,3,2], [1,3,1,2]. Exactly 3.

Example 2

Input: n = 5, k = 4, x = 2
Output: 20
Note: The two-bucket recurrence yields same = 20 after 5 steps (verified by direct enumeration).

Example 3

Input: n = 3, k = 3, x = 1
Output: 2
Note: Ending back at 1: [1,2,1] and [1,3,1]. Two arrays.

Constraints

1 ≤ n ≤ 10⁵
1 ≤ k ≤ 10⁵
1 ≤ x ≤ k
Answer is taken modulo 1 000 000 007

Clarifying questions4First question: Can the first element be something other than 1?Explore questions

Q1.Can the first element be something other than 1?
No — a[0] is fixed at 1. That fixes the base case: a length-1 array is just [1], which 'ends at x' only if x = 1.
Q2.Must every value 1..k actually appear?
No. Values may repeat (as long as not adjacent) and some may never appear. We're counting all arrays satisfying the three rules.
Q3.Why only two states instead of k?
Because all values except x are interchangeable for counting purposes — the number of ways to continue from any non-x value is identical. Collapsing them into one bucket gives O(n) instead of O(n·k).
Q4.Why is the modulus applied so aggressively?
Counts grow like (k−1)ⁿ, astronomically large. The product same·(k−1) can exceed 10¹⁴, so reduce after every add and multiply to stay in range and keep the answer exact mod 1e9+7.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you bucket the k possible end-values into two equivalence classes (x vs not-x) and write a correct combinatorial recurrence, applying the modulus at every step.

Where candidates slip

Tracking k separate counts (O(n·k) and unnecessary), getting the (k−1) vs (k−2) multipliers backwards, or forgetting to mod the multiplications and overflowing.

How to stand out

Derive the two-class recurrence from first principles (why k−1 and why k−2), then mention the O(log n) closed form via modular inverse for huge n.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Recurse over Every Next Value	`O(kⁿ)`	`O(n)`	State it to expose the branching and the overlapping subproblems, then bucket and memoize.	Read
2	Two-Bucket Counting DP (Optimal)Optimal	`O(n)`	`O(1)`	The answer they want. Phrase it as 'count ends-at-x vs ends-elsewhere with combinatorial transitions'.	Read
3	Closed Form via Modular Inverse — O(log n)	`O(log n)`	`O(1)`	Mention for very large n: a direct formula using fast exponentiation and Fermat's inverse.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.Explore the full tree

Two value-classes and their transitions

How to read it:All non-x values collapse into one bucket; arrows carry the combinatorial multipliers.

Rendering diagram…

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 3

Brute Force — Recurse over Every Next Value

TimeO(kⁿ)SpaceO(n)

State it to expose the branching and the overlapping subproblems, then bucket and memoize.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Build the array position by position. At each step, try every value 1..k that differs from the previous element, and recurse.

2Hint 2Explore hint

Count an array only when you reach length n with the last value equal to x.

3Hint 3Explore hint

There are up to (k−1) choices per step → (k−1)ⁿ leaves. But the count of continuations depends only on (position, previous value) — heavily overlapping.

A · Core idea

The literal interpretation: grow the array one slot at a time, branching on every legal next value.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

n = 3, k = 3, x = 1

Interactive diagram

Branching on every legal next value

pos 1 from prev=1

Active call / nodeSupporting contextReturned stateNot active

States differing only by a non-x previous value are identical — the redundancy memoization removes.

Final result2

C · Code with teaching comments

Reference implementation previewpublic int countArray(int n, int k, int x) { return f(1, 1, n, k, x); } private int f(int i, int prev, int n, int k, int x) {Explore the full code

solution.javaJava

Brute Force — Recurse over Every Next Value — reference

3 teaching notes

1
public int countArray(int n, int k, int x) {
2
    return f(1, 1, n, k, x);
3
}
4
 
5
private int f(int i, int prev, int n, int k, int x) {
6
    // Completed array: counts only if it ends at the target x.
7
    if (i == n) return prev == x ? 1 : 0;
8
    long ways = 0;
9
    for (int v = 1; v <= k; v++) {
10
        if (v != prev) ways += f(i + 1, v, n, k, x);
11
    }
12
    // Reduce mod the prime; exponential time means this never finishes for large n.
13
    return (int) (ways % 1_000_000_007L);
14
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.14 lines

D · Why it works and complexityO(kⁿ) timeO(n) spaceOpen the invariant and proofExplore the proof

ComplexityO(kⁿ) time, O(n) space — Up to (k−1) branches at each of n positions gives O(kⁿ) leaves; recursion depth O(n).

E · Edge cases and pitfalls3Tracking the exact previous value as state — k× more states than needed.Explore edge cases

Pitfalls

Tracking the exact previous value as state — k× more states than needed.
Forgetting the modulus, overflowing the running sum.
Running it for n, k = 10⁵ — (k−1)ⁿ never returns.

03.2

Approach 2 of 3 · Optimal

Two-Bucket Counting DP (Optimal)

TimeO(n)SpaceO(1)

The answer they want. Phrase it as 'count ends-at-x vs ends-elsewhere with combinatorial transitions'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Collapse the k end-values into two classes: `same` = arrays whose current last element is x, `diff` = arrays whose last element is anything but x.

2Hint 2Explore hint

3Hint 3Explore hint

Base case from a[0]=1: same = (x==1), diff = (x!=1). Iterate to length n, mod everything, answer = same.

A · Core idea

Bucket the end-value into two equivalence classes and count each class in bulk.

Transition to length i+1.

Landing on x (new_same): the next element is x, which must differ from the current one, so the current element cannot be x. Only diff arrays qualify, and there's exactly one value (x) to place → new_same = diff.
Landing on a non-x value (new_diff):
- From a same array (current element is x): any value except x is both legal (differs from x) and non-x → k − 1 choices.
- From a diff array (current element is some y ≠ x): the next value must differ from y and must not be x, so we exclude two values (y and x) → k − 2 choices.
- Total: new_diff = same·(k−1) + diff·(k−2).

Base case. The array starts at a[0] = 1. So the length-1 array is [1]: it ends at x iff x == 1. Set same = (x == 1 ? 1 : 0), diff = (x == 1 ? 0 : 1).

Answer. After iterating up to length n, same holds the number of arrays ending at x — exactly what the problem asks.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

n = 4, k = 3, x = 2

Array state

len 1

same=0, diff=1

[0]

[1]

Current pointerResolved stateNot processed

Final result3

C · Code with teaching comments

solution.javaJava

Two-Bucket Counting DP (Optimal) — optimal

4 teaching notes

1
public int countArray(int n, int k, int x) {
2
    final long MOD = 1_000_000_007L;
3
    // Base case: the length-1 array [1] ends at x only when x is 1.
4
    long same = (x == 1) ? 1 : 0;
5
    long diff = (x == 1) ? 0 : 1;
6
    for (int i = 2; i <= n; i++) {
7
        // Only a non-x element can be followed by x.
8
        long newSame = diff % MOD;
9
        // (k−1) from an x-element, (k−2) from a non-x element; mod each product.
10
        long newDiff = (same * (k - 1) % MOD + diff * (k - 2) % MOD) % MOD;
11
        same = newSame;
12
        diff = newDiff;
13
    }
14
    // Arrays ending at x after n elements.
15
    return (int) (same % MOD);
16
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.16 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

ComplexityO(n) time, O(1) space — One loop of n−1 steps, each doing O(1) modular arithmetic → O(n) time. Two rolling counters → O(1) space.

E · Edge cases and pitfalls7n = 1, x = 1 — Loop never runs; same=1 → answer 1 (the array [1]).Explore edge cases

Edge cases handled

n = 1, x = 1Loop never runs; same=1 → answer 1 (the array [1]).
n = 1, x = 2same=0; answer 0 — a length-1 array can only end at 1.
n = 3, k = 3, x = 1same toggles back: len2 same=0 diff=2... ends same=2 → [1,2,1],[1,3,1].
k = 1k−2 = −1; only n=1,x=1 is valid → 1, all longer arrays impossible (no different neighbour).

Pitfalls

Swapping (k−1) and (k−2) — the x-element class has one more legal target than the non-x class.
Using int for the products — same·(k−1) overflows; use long and mod each factor.
Mis-seeding the base case (e.g. same=1 regardless of x) — a[0]=1 dictates it.

03.3

Approach 3 of 3

Closed Form via Modular Inverse — O(log n)

TimeO(log n)SpaceO(1)

Mention for very large n: a direct formula using fast exponentiation and Fermat's inverse.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The recurrence has a closed form. Walks of length n−1 on the complete graph Kₖ from a fixed start: the count splits by whether the end equals the start's value class.

2Hint 2Explore hint

If x ≠ 1: answer = ((k−1)^(n−1) − (−1)^(n−1)) / k. If x = 1: answer = ((k−1)^(n−1) + (k−1)·(−1)^(n−1)) / k.

3Hint 3Explore hint

Division mod a prime is multiplication by the modular inverse: divide by k using k^(MOD−2) (Fermat's little theorem).

A · Core idea

The two-bucket recurrence is linear, so it has a closed form — useful when n is enormous and even O(n) is too slow.

The formula. Building the array is equivalent to counting walks of length n−1 on the complete graph K_k (every value adjacent to every other value) starting at the vertex 1:

Ending at a vertex different from the start (x ≠ 1): ((k−1)^(n−1) − (−1)^(n−1)) / k.
Ending back at the start (x = 1): ((k−1)^(n−1) + (k−1)·(−1)^(n−1)) / k.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

n = 4, k = 3, x = 2 (x ≠ 1)

Interactive diagram

Closed form pipeline

power

Active call / nodeSupporting contextReturned stateNot active

Exponentiate, sign-correct, then divide by k via modular inverse.

Final result3

C · Code with teaching comments

solution.javaJava

Closed Form via Modular Inverse — O(log n) — reference

4 teaching notes

1
public int countArray(int n, int k, int x) {
2
    final long MOD = 1_000_000_007L;
3
    // (k−1)^(n−1) via fast modular exponentiation — O(log n).
4
    long base = power(k - 1, n - 1, MOD);
5
    long sign = ((n - 1) % 2 == 0) ? 1 : MOD - 1; // +1 or -1 mod p
6
    long numerator;
7
    if (x == 1) {
8
        numerator = (base + (long) (k - 1) % MOD * sign) % MOD;
9
    } else {
10
        numerator = (base - sign % MOD + MOD) % MOD;
11
    }
12
    long invK = power(k, MOD - 2, MOD); // Fermat inverse
13
    // Multiply by the inverse to 'divide by k' under the modulus.
14
    return (int) (numerator * invK % MOD);
15
}
16
 
17
private long power(long b, long e, long mod) {
18
    b %= mod;
19
    long r = 1;
20
    while (e > 0) {
21
        if ((e & 1) == 1) r = r * b % mod;
22
        b = b * b % mod;
23
        e >>= 1;
24
    }
25
    return r;
26
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.26 lines

D · Why it works and complexityO(log n) timeO(1) spaceOpen the invariant and proofExplore the proof

ComplexityO(log n) time, O(1) space — Fast modular exponentiation for (k−1)^(n−1) and for the inverse of k each take O(log n) (or O(log MOD)) multiplications → O(log n) total.

E · Edge cases and pitfalls6n = 4, k = 3, x = 1 — ((2)³ + 2·(−1)) / 3 = (8−2)/3 = 2 — matches enumeration.Explore edge cases

Edge cases handled

n = 4, k = 3, x = 1((2)³ + 2·(−1)) / 3 = (8−2)/3 = 2 — matches enumeration.
n = 100, k = 100, x = 1Closed form gives 758049401, identical to the O(n) DP.
k = 1Modular inverse of 1 is 1; formula degenerates correctly for the trivial single-value case.

Pitfalls

Forgetting to add MOD before reducing a subtraction — produces a negative result.
Using floating-point division by k instead of the modular inverse — loses exactness.
Getting the parity sign or the x==1 vs x≠1 branch wrong — the two cases differ.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Tracking every value separately

All non-x values are interchangeable for counting. Keeping k counters is O(n·k) and needless; two buckets suffice.

Explore the code comparison

Don't write this

dp = [[0] * (k + 1) for _ in range(n + 1)]
# fills k columns per row — O(n*k)

Write this instead

same, diff = (x == 1), (x != 1)
for _ in range(2, n + 1):
    same, diff = diff, (same * (k - 1) + diff * (k - 2)) % MOD

Wrong multipliers

From an x-element there are k−1 non-x targets; from a non-x element you also exclude the current value, leaving k−2. Swapping them miscounts.

Explore the code comparison

Don't write this

newDiff = (same * (k - 2) + diff * (k - 1)) % MOD;  // swapped

Write this instead

newDiff = (same * (k - 1) % MOD + diff * (k - 2) % MOD) % MOD;

Overflow on the products

same and (k−1) can each be near 10⁹; their product is ~10¹⁸, overflowing int and risking overflow if you add two such products before reducing.

Explore the code comparison

Don't write this

int newDiff = same * (k - 1) + diff * (k - 2);  // int overflow

Write this instead

long newDiff = (same * (k - 1) % MOD + diff * (k - 2) % MOD) % MOD;

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Two-bucket counting DP (ends-at-x vs ends-elsewhere), modular

Code pattern to memorize

MOD = 1e9+7
same, diff = (1 if x==1 else 0), (0 if x==1 else 1)   # length-1: a[0]=1
for i in 2..n:
    new_same = diff                       # only a non-x can step onto x
    new_diff = same*(k-1) + diff*(k-2)     # step onto a non-x value
    same, diff = new_same % MOD, new_diff % MOD
answer = same

Rules to remember

1Bucket states by value class, not by value: 'equals x' vs 'not x'. All non-x values behave identically, so one count suffices for the whole bucket.
2new_same = diff: you can only arrive at x from something that isn't x (consecutive must differ), and there's exactly one value x to land on.
3new_diff = same·(k−1) + diff·(k−2): from an x-element any of the other (k−1) values is non-x; from a non-x element you exclude both the current value and x → (k−2).
4Reduce every arithmetic step mod 1e9+7, including the multiplications — products of two ~1e9 counts overflow 32-bit and even flirt with 64-bit if you batch them.
5Seed the base case from a[0] = 1: if x == 1 the length-1 array already ends at x (same=1), otherwise it ends elsewhere (diff=1).

Use this pattern when

Count sequences/arrays under adjacency constraints (consecutive differ, no two equal, etc.)
States collapse into a few equivalence classes you can count in bulk
Answer required modulo a large prime → modular counting DP
Walks on a complete-graph-like structure with fixed start and end

Choose another pattern when

You must enumerate or output the arrays, not count them → backtracking, not DP
Constraints couple non-adjacent positions arbitrarily → richer state needed
Values aren't interchangeable (each has distinct rules) → can't bucket into 2 classes
No modulus and n is tiny → a closed-form or direct formula may be simpler

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Same pattern

←

Candies

Continue · Next problem

Equal