Count Subarrays Whose Values Stay Within Two
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
# Count Subarrays Whose Values Stay Within Two
You are given a 0-indexed integer array `nums`. Call a subarray continuous if every pair of its elements differs by at most `2`: for all indices `i1` and `i2` inside that subarray,
`0 <= |nums[i1] - nums[i2]| <= 2`.
Return the total number of continuous subarrays. A subarray is a contiguous, nonempty sequence of array elements.
### Examples
**Example 1**
```text
Input: nums = [4,6,5,8]
Output: 7
```
All four single-element subarrays qualify. The qualifying length-two subarrays are `[4,6]` and `[6,5]`; the qualifying length-three subarray is `[4,6,5]`. No other subarray qualifies, for a total of `4 + 2 + 1 = 7`.
**Example 2**
```text
Input: nums = [9,9,12,10]
Output: 6
```
There are four qualifying singletons and two qualifying adjacent pairs: `[9,9]` and `[12,10]`. Every longer subarray contains both a `9` and a `12`, so its range is too large. The two occurrences of singleton `[9]` count separately because they occupy different positions.
### Constraints
- `1 <= nums.length <= 10^5`.
- `1 <= nums[i] <= 10^9`.
### Clarifying Questions
- Is checking only neighboring values enough? The condition applies to every pair of elements in the subarray.
- Is a difference of exactly `2` allowed? Yes; the bound is inclusive.
- Can a subarray skip elements? No; its elements must occupy consecutive indices.
- Are equal-valued subarrays at different positions counted separately? Yes; subarrays are identified by their index intervals.
### C++ Interface
```cpp
class Solution {
public:
long long continuousSubarrays(vector<int>& nums) {
}
};
```
### Reasoning Checkpoints
- Represent the all-pairs requirement without enumerating every pair.
- Count all qualifying intervals, including repeated values at different indices.
- Explain when a discarded starting index can safely stay discarded as the right endpoint advances.
```hint Extremes inside an interval
Which two values inside a subarray determine its largest pairwise absolute difference?
```
Overview: Count every nonempty contiguous subarray in which all pairs of values differ by at most two, including intervals with repeated values.
