Longest Subarray With At Most Two Distinct Values

Medium15–20 min

Topics

ArraySliding WindowHash Table

Companies

AmazonGoogleMicrosoftFacebook

Given an array nums, return the length of the longest contiguous subarray that contains at most 2 distinct values. Checking every starting index and re-scanning forward works, but it forgets everything the previous start already learned about the array. The sliding window technique keeps a frequency map of the values currently in view: grow the window by moving the right edge forward, and whenever a 3rd distinct value sneaks in, shrink from the left — dropping counts back to zero — until the window is valid again. Every element enters and leaves the window at most once, so the whole scan runs in O(n).

Test Case 1:

Input:nums = [1, 2, 3, 2, 2]

Output:4

Explanation:The subarray [2, 3, 2, 2] (indices 1-4) holds only 2 distinct values and has length 4.

Test Case 2:

Input:nums = [1, 2, 1]

Output:3

Explanation:The whole array already has only 2 distinct values, so the answer is its full length.

Test Case 3:

Input:nums = [0, 1, 2, 2]

Output:3

Explanation:The subarray [1, 2, 2] (indices 1-3) holds only 2 distinct values and has length 3.

Constraints

◆1 ≤ nums.length ≤ 10⁵
◆0 ≤ nums[i] ≤ 10⁴

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

🧪Try your own test case

nums (comma-separated) — 2-12 integers, 0-9

1	class Solution {
2	public int longestSubarrayWithAtMostTwoDistinct(int[] nums) {
3	Map<Integer, Integer> count = new HashMap<>();
4	int left = 0, maxLen = 0;
5	for (int right = 0; right < nums.length; right++) {
6	count.put(nums[right], count.getOrDefault(nums[right], 0) + 1);
7	while (count.size() > 2) {
8	count.put(nums[left], count.get(nums[left]) - 1);
9	if (count.get(nums[left]) == 0) count.remove(nums[left]);
10	left++;
11	}
12	maxLen = Math.max(maxLen, right - left + 1);
13	}
14	return maxLen;
15	}
16	}
17

Variables

left0

maxLen0

INITIALIZE

Start left at 0, maxLen at 0, and an empty frequency map of the values currently inside the window.

Step 1 / 13

Approach & Solutions

Brute Force

Brute

For every possible starting index, grow the window to the right — tracking the set of distinct values seen — until a 3rd distinct value would enter, then record the window's length. Correct, but every start re-scans from scratch, throwing away everything the previous start already discovered about the array.

TimeO(n²)

SpaceO(1)

Java

Try it out

class Solution {
    public int longestSubarrayWithAtMostTwoDistinct(int[] nums) {
        int maxLen = 0;
        for (int i = 0; i < nums.length; i++) {
            Set<Integer> seen = new HashSet<>();
            int j = i;
            while (j < nums.length) {
                seen.add(nums[j]);
                if (seen.size() > 2) break;
                j++;
            }
            maxLen = Math.max(maxLen, j - i);
        }
        return maxLen;
    }
}

Optimal — Sliding Window

Optimal

Grow the window by moving right and tracking a frequency map of the values inside it. Whenever the map holds more than 2 distinct keys, shrink from the left — decrementing counts and dropping keys that hit 0 — until it's valid again. Every value enters and leaves the window at most once, so the whole scan is O(n).

TimeO(n)