02. Longest Subarray with At Most Two Distinct Integers
✅ GFG solution to the Longest Subarray with At Most Two Distinct Integers problem: find maximum length subarray containing at most 2 distinct elements using sliding window technique. 🚀
The problem can be found at the following link: 🔗 Question Link
🧩 Problem Description
You are given an array arr[] consisting of positive integers. Your task is to find the length of the longest subarray that contains at most two distinct integers.
A subarray is a contiguous sequence of elements within an array. The goal is to find the maximum possible length of such a subarray where the number of unique elements does not exceed 2.
📘 Examples
Example 1
Input: arr[] = [2,1,2]Output: 3Explanation: The entire array [2,1,2] contains at most two distinct integers (2and1).Hence, the length of the longest subarray is 3.
Example 2
Input: arr[] = [3,1,2,2,2,2]Output: 5Explanation: The longest subarray containing at most two distinct integers is [1,2,2,2,2],which has a length of 5.
Example 3
Input: arr[] = [1, 1, 1, 1]
Output: 4
Explanation: The entire array contains only one distinct integer (1), which satisfies
the condition of at most two distinct integers.
🔒 Constraints
$1 \le \text{arr.size()} \le 10^5$
$1 \le \text{arr}[i] \le 10^5$
✅ My Approach
The optimal approach uses the Sliding Window technique with a Hash Map to efficiently track distinct elements and their frequencies:
Sliding Window + Hash Map
Initialize Variables:
Use two pointers: left (start of window) and right (end of window).
Maintain a hash map to store frequency of elements in current window.
Track maxLength to store the result.
Expand Window:
Move right pointer and add arr[right] to the hash map.
Increment its frequency.
Contract Window:
If hash map size exceeds 2 (more than 2 distinct elements), shrink window from left.
Decrement frequency of arr[left] and remove it if frequency becomes 0.
Move left pointer forward.
Update Result:
After each valid window, update maxLength with current window size.
Continue Until End:
Repeat until right pointer reaches the end of array.
📝 Time and Auxiliary Space Complexity
Expected Time Complexity: O(n), where n is the size of the array. Each element is visited at most twice (once by right pointer and once by left pointer).
Expected Auxiliary Space Complexity: O(k), where k is the number of distinct elements in the current window. In the worst case, k ≤ 2, so effectively O(1) additional space.
🧑💻 Code (C++)
class Solution {
public:
int totalElements(vector<int> &arr) {
unordered_map<int, int> mp;
int i = 0, maxLen = 0;
for (int j = 0; j < arr.size(); j++) {
mp[arr[j]]++;
while (mp.size() > 2) {
if (--mp[arr[i]] == 0) mp.erase(arr[i]);
i++;
}
maxLen = max(maxLen, j - i + 1);
}
return maxLen;
}
};
⚡ View Alternative Approaches with Code and Analysis
📊 2️⃣ Two Variable Tracking Approach
💡 Algorithm Steps:
Initialize two variables first and second to represent the two distinct numbers allowed in the window, and firstIdx, secondIdx to store their most recent positions.
Traverse the array with a right pointer:
If the current element equals first or second, update the corresponding index.
If a third new element appears:
Determine which of the two existing numbers appeared earlier (minimum of firstIdx and secondIdx).
Move the left pointer just past that index to ensure only two distinct elements remain.
Replace the older number (first or second) with the new element and update its index.
Update the maximum length after each iteration.
class Solution {
public:
int totalElements(vector<int> &arr) {
int n = arr.size(), maxLen = 0, left = 0;
int first = -1, second = -1, firstIdx = -1, secondIdx = -1;
for (int right = 0; right < n; right++) {
if (arr[right] == first) firstIdx = right;
else if (arr[right] == second) secondIdx = right;
else if (first == -1) first = arr[right], firstIdx = right;
else if (second == -1) second = arr[right], secondIdx = right;
else {
left = min(firstIdx, secondIdx) + 1;
if (firstIdx < secondIdx) first = arr[right], firstIdx = right;
else second = arr[right], secondIdx = right;
}
maxLen = max(maxLen, right - left + 1);
}
return maxLen;
}
};
📝 Complexity Analysis:
Time: ⏱️ O(n)
Auxiliary Space: 💾 O(1) - Constant space
✅ Why This Approach?
Optimal space complexity with O(1) memory usage.
No hash map overhead, direct variable tracking.
Efficient for small distinct element tracking.
📊 3️⃣ Frequency Array Optimization
💡 Algorithm Steps:
Use a frequency array (e.g., freq[100001]) assuming all elements fall within a known small integer range.
If arr[right] is added to the window for the first time (freq[arr[right]] == 0), increment distinctCount.
Increase the count for arr[right].
If distinctCount > 2, shrink the window:
Decrease the count of arr[left].
If its count becomes 0, decrement distinctCount.
Move left forward.
At each iteration, update maxLen as the maximum valid window size.
class Solution {
public:
int totalElements(vector<int> &arr) {
vector<int> freq(100001, 0);
int distinctCount = 0, left = 0, maxLen = 0;
for (int right = 0; right < arr.size(); right++) {
if (freq[arr[right]]++ == 0) distinctCount++;
while (distinctCount > 2) {
if (--freq[arr[left]] == 0) distinctCount--;
left++;
}
maxLen = max(maxLen, right - left + 1);
}
return maxLen;
}
};
📝 Complexity Analysis:
Time: ⏱️ O(n)
Auxiliary Space: 💾 O(k) where k = range of elements
✅ Why This Approach?
Faster than hash map for known small ranges.
Cache-friendly array access pattern.
No need for key-value mapping—constant-time operations.
📊 4️⃣ STL Set-Based Tracking
💡 Algorithm Steps:
Use an unordered_map<int, int> to store frequency of elements and a unordered_set<int> to track the number of unique elements in the current window.
Initialize left = 0, maxLen = 0.
Traverse using a right pointer:
Add arr[right] to the map and insert into the set.
If the set size exceeds 2 (more than 2 distinct elements), shrink the window:
Decrease count of arr[left].
If the count becomes 0, remove it from the set.
Move the left pointer forward.
At each step, update maxLen with the current valid window size.
class Solution {
public:
int totalElements(vector<int> &arr) {
unordered_map<int, int> freq;
unordered_set<int> distinct;
int left = 0, maxLen = 0;
for (int right = 0; right < arr.size(); right++) {
freq[arr[right]]++;
distinct.insert(arr[right]);
while (distinct.size() > 2) {
if (--freq[arr[left]] == 0) {
distinct.erase(arr[left]);
}
left++;
}
maxLen = max(maxLen, right - left + 1);
}
return maxLen;
}
};
📝 Complexity Analysis:
Time: ⏱️ O(n)
Auxiliary Space: 💾 O(n)
✅ Why This Approach?
Clear separation of concerns with set and map.
Easy to trace which elements are currently active.
Good for debugging and understanding logic flow.
5️⃣ 📝 Ordered Map Sliding Window
💡 Algorithm Steps:
Use a std::map<int, int> (ordered map) to count the elements within the sliding window.
Expand the window to the right by moving pointer j; increase the count for a[j].
If the map contains more than 2 distinct elements, shrink the window from the left:
Decrement the count for a[i].
If the count becomes 0, erase the element from the map.
Track the maximum window size during each iteration.
class Solution {
public:
int totalElements(vector<int>& a) {
map<int,int> mp;
int i = 0, res = 0;
for (int j = 0; j < a.size(); ++j) {
++mp[a[j]];
while (mp.size() > 2) {
if (--mp[a[i]] == 0) mp.erase(a[i]);
++i;
}
res = max(res, j - i + 1);
}
return res;
}
};
📝 Complexity Analysis:
Time: ⏱️ O(n log k), where k ≤ 2 here
Auxiliary Space: 💾 O(k)
✅ Why This Approach?
Maintains ordering automatically with std::map.
Shrinks window cleanly using count + erase.
Good readability and debugging via sorted structure.
🆚 🔍 Comparison of Approaches
🚀 Approach
⏱️ Time Complexity
💾 Space Complexity
✅ Pros
⚠️ Cons
🔍 Hash Map Sliding Window
🟢 O(n)
🟡 O(k)
⚡ Clean code, general solution
💾 Hash map overhead
🔄 Two Variable Tracking
🟢 O(n)
🟢 O(1)
🚀 Optimal space, fastest runtime
🧮 Complex logic, harder to debug
🔺 Frequency Array
🟢 O(n)
🟡 O(range)
⚡ Cache-friendly, fast access
💾 Limited to known small ranges
🔑 STL Set-Based
🟢 O(n)
🟡 O(n)
🔧 Clear logic, STL optimized
💾 Extra space for set structure
⏰ Ordered Map Sliding Window
🟡 O(n log k)
🟢 O(1)
🚀 Predictable, no hash collisions
💾 Slightly slower per op
🏆 Best Choice Recommendation
🎯 Scenario
🎖️ Recommended Approach
🔥 Performance Rating
⚡ Maximum performance, competitive programming
🥇 Two Variable Tracking
★★★★★
🔧 Production code, readability important
🥈 Hash Map Sliding Window
★★★★☆
📊 Known small element range
🥉 Frequency Array
★★★★☆
🎯 Educational purposes, clear logic
🎖️ STL Set-Based
★★★☆☆
📚 Readability / simplicity
🏅 Ordered Map Sliding Window
★★★★☆
🧑💻 Code (Java)
class Solution {
public int totalElements(int[] arr) {
Map<Integer, Integer> map = new HashMap<>();
int i = 0, max = 0;
for (int j = 0; j < arr.length; j++) {
map.put(arr[j], map.getOrDefault(arr[j], 0) + 1);
while (map.size() > 2) {
map.put(arr[i], map.get(arr[i]) - 1);
if (map.get(arr[i]) == 0) map.remove(arr[i]);
i++;
}
max = Math.max(max, j - i + 1);
}
return max;
}
}
🐍 Code (Python)
class Solution:
def totalElements(self, arr):
mp = {}
i = maxLen = 0
for j in range(len(arr)):
mp[arr[j]] = mp.get(arr[j], 0) + 1
while len(mp) > 2:
mp[arr[i]] -= 1
if mp[arr[i]] == 0:
del mp[arr[i]]
i += 1
maxLen = max(maxLen, j - i + 1)
return maxLen
🧠 Contribution and Support
For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: 📬 Any Questions?. Let's make this learning journey more collaborative!
⭐ If you find this helpful, please give this repository a star! ⭐
