Count Arrays with Zigzag Comparisons
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Other
### Problem
Given integers `n`, `l`, and `r`, count arrays of length `n` satisfying all three conditions:
- Every element is an integer in the inclusive range `[l,r]`.
- Adjacent elements are different.
- No three consecutive elements are strictly increasing or strictly decreasing.
Return the number of valid arrays modulo `1000000007`.
```cpp
class Solution {
public:
int zigZagArrays(int n, int l, int r);
};
```
### Examples
**Example 1:**
```text
Input: n = 4, l = 2, r = 3
Output: 2
Explanation: The only valid arrays are [2,3,2,3] and [3,2,3,2].
```
**Example 2:**
```text
Input: n = 4, l = 1, r = 3
Output: 16
Explanation: There are sixteen valid arrays over these three values. For example, [1,2,1,3] and [3,1,3,2] satisfy all conditions. Equal neighbors and any strictly monotone consecutive triple are excluded.
```
### Constraints
- `3 <= n <= 2000`.
- `1 <= l < r <= 2000`.
### Clarifying Questions
- Are values at distance two allowed to be equal? Yes; only adjacent equality is forbidden.
- Are the range endpoints included? Yes.
- Are only arrays beginning with an increase counted? No; any array satisfying the three conditions counts.
- Are arrays different when they differ at any position? Yes.
### What a Strong Answer Covers
- All allowed values, strict adjacent inequality, and both forbidden kinds of consecutive triple.
- Counting every valid array exactly once.
- Correct modular arithmetic and handling of the smallest allowed value range.
- A completeness argument and bounds for the full length and value-range constraints.
### Follow-up Questions
- Can an array with all elements equal satisfy the conditions?
- What numeric representation issues would arise if the exact count were requested without a modulus?
```hint Keep the last comparison
With equal neighbors excluded, the two adjacent comparisons in any triple must have opposite directions. Count sequences by their last value and last comparison direction. Prefix and suffix sums can aggregate the strict smaller-value and larger-value transitions.
```
Overview: Count arrays with unequal neighbors and no strictly monotone consecutive triple. Includes fresh examples, modular counting, proof, and a complete C++ solution.