Introduction

This problem is a constrained sliding-window problem: find the longest contiguous region that contains at most two distinct numbers, and if there are two numbers, their difference must be at most 1. The important part is that the answer depends on contiguity, so sorting or counting the whole array is not enough.

Why a Sliding Window Fits

For any ending index right, we want the longest valid window ending there. If adding a new value breaks the rules, we do not restart from scratch. We shrink the left side until the window becomes valid again.

The window is valid when both conditions hold:

1. the number of distinct values is at most 2
2. if there are two values, max_value - min_value <= 1

Because the window never moves backward, a two-pointer approach gives linear time.

Python Implementation

The nice detail here is that the map of frequencies never has more than a few keys. That makes checking min and max cheap enough in practice, and still clearly expresses the idea.

1from collections import defaultdict
2
3
4def longest_subarray(nums):
5    counts = defaultdict(int)
6    left = 0
7    best = 0
8
9    for right, value in enumerate(nums):
10        counts[value] += 1
11
12        while len(counts) > 2 or (len(counts) == 2 and max(counts) - min(counts) > 1):
13            left_value = nums[left]
14            counts[left_value] -= 1
15            if counts[left_value] == 0:
16                del counts[left_value]
17            left += 1
18
19        best = max(best, right - left + 1)
20
21    return best
22
23
24print(longest_subarray([1, 2, 2, 3, 2, 2, 1]))
25print(longest_subarray([4, 4, 4, 5, 5, 6]))

Output:

4
5

In the first example, the best window is [2, 3, 2, 2]. It contains two distinct values and their difference is 1.

Why the Algorithm Is Linear

Each element enters the window once when right advances and leaves the window once when left advances. That means the total number of pointer moves is O(n).

The frequency map only tracks the current window, so memory usage is O(1) in the practical sense for this problem, because the map can never grow beyond the number of distinct values temporarily present while we shrink.

Edge Cases to Think About

Arrays with one repeated value are easy. The answer is the full length because one distinct value is always valid.

Arrays with large jumps, such as [1, 1, 3, 3], are more interesting. Even though there are only two distinct values, the window is invalid because 3 - 1 = 2.

Negative numbers do not change the logic. The only thing that matters is the absolute spread between the two distinct values, which max - min already captures.

Related Problems

This looks similar to "at most two distinct characters" or "fruit into baskets," but it is stricter. Those problems only care about the count of distinct values. This one adds a value-difference constraint, so [1, 3] is invalid here even though it contains only two distinct numbers.

That extra rule is why a plain two-distinct sliding window is not enough by itself.

Common Pitfalls

The biggest mistake is solving a different problem by counting values globally. A valid answer must be contiguous, so frequency counts over the whole array do not help.

Another mistake is checking only len(counts) <= 2 and forgetting the difference condition. That accepts windows like [1, 1, 3], which should be rejected.

A third issue is trying to rebuild the frequency map from scratch every time the window becomes invalid. That turns a linear problem into a much slower one.

Summary

• Use a sliding window with a frequency map.
• Keep shrinking the left side until the window has at most two distinct values whose spread is at most 1.
• The algorithm runs in O(n) time because each pointer only moves forward.
• This problem is stricter than the classic "at most two distinct values" window problem.
• The main implementation risk is forgetting the max - min <= 1 condition.