Longest subarray with Atmost two distinct integers

JavaView on GFG

Time: O(n)

Space: O(1)

Intuition

Sliding window: maintain window with at most 2 distinct values.

Algorithm

1HashMap counts. When distinct count > 2: shrink from left. Track max window size.

Common Pitfalls

•Same as LC 159. Generalized to k distinct: LC 340. O(n) sliding window.

Longest subarray with Atmost two distinct integers.java

Java

// Approach: Sliding window. Shrink left when distinct count exceeds 2, tracking max window size.
// Time: O(n) Space: O(1)
import java.util.*;

class Solution {
    public int totalElements(int[] arr) {
        int n = arr.length;
        int start = 0;
        int maxLength = 0;
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            map.put(arr[i], map.getOrDefault(arr[i], 0) + 1);
            while (map.size() > 2) {
                map.put(arr[start], map.get(arr[start]) - 1);
                if (map.get(arr[start]) == 0)
                    map.remove(arr[start]);

                start++;
            }
            maxLength = Math.max(maxLength, i - start + 1);
        }
        return maxLength;
    }
}

Was this solution helpful?