.png)
Longest Subarray with At Most K Distinct Elements
Problem Statement
You are given an integer array arr and an integer K.
Your task is to find the length of the longest contiguous subarray that contains at most K distinct elements.
Examples
Example 1
Input:
arr = [1,2,1,2,3]
K = 2
Output:
4
Explanation:
Subarray [1,2,1,2]
Example 2
Input:
arr = [1,2,3,4,5]
K = 1
Output:
1
Why This Problem Is Important
- Core sliding window + frequency map
- Foundation of:
- Longest substring with at most K distinct characters
- Fruit into baskets
- Minimum window substring
- Frequently asked in Amazon, Google, Microsoft
Approaches Overview
| Approach | Technique | Time | Space |
|---|---|---|---|
| 1 | Brute Force + Set | O(n²) | O(n) |
| 2 | Prefix Enumeration (HashMap reset) | O(n²) | O(n) |
| 3 | Sliding Window (Optimal) | O(n) | O(k) |
Approach 1: Brute Force
Idea
Check every subarray, count distinct elements using a set.
Time Complexity
- Outer loop for start index → O(n)
- Inner loop for end index → O(n)
- Distinct counting → O(1) (amortized)
Total: O(n²)
Space Complexity
- Set / frequency array → O(n)
Implementations
C
#include
int main(){
int arr[] = {1,2,1,2,3};
int n = 5, K = 2, ans = 0;
for(int i=0;i K) break;
if(j - i + 1 > ans) ans = j - i + 1;
}
}
printf("%d", ans);
}
C++
#include
using namespace std;
int main(){
vector arr = {1,2,1,2,3};
int K = 2, ans = 0;
for(int i=0;i st;
for(int j=i;j K) break;
ans = max(ans, j - i + 1);
}
}
cout << ans;
}
Java
import java.util.*;
class Brute {
public static void main(String[] args){
int[] arr = {1,2,1,2,3};
int K = 2, ans = 0;
for(int i=0;i set = new HashSet<>();
for(int j=i;j K) break;
ans = Math.max(ans, j - i + 1);
}
}
System.out.println(ans);
}
}
Python
arr = [1,2,1,2,3]
K = 2
ans = 0
for i in range(len(arr)):
s = set()
for j in range(i,len(arr)):
s.add(arr[j])
if len(s) > K:
break
ans = max(ans, j-i+1)
print(ans)
JavaScript
let arr = [1,2,1,2,3];
let K = 2, ans = 0;
for(let i=0;i K) break;
ans = Math.max(ans, j-i+1);
}
}
console.log(ans);
C#
using System;
using System.Collections.Generic;
class Program {
static void Main(){
int[] arr = {1,2,1,2,3};
int K = 2, ans = 0;
for(int i=0;i set = new HashSet();
for(int j=i;j K) break;
ans = Math.Max(ans, j - i + 1);
}
}
Console.WriteLine(ans);
}
}
Output
4Approach 2: Prefix Enumeration with Frequency Map
Idea
For each starting index, grow subarray and maintain frequency map.
Time Complexity
- Outer loop → O(n)
- Inner loop → O(n)
- HashMap operations → O(1) average
Total: O(n²)
Space Complexity
- Frequency map → O(n) (worst case)
Implementations
C++
#include
using namespace std;
int main(){
vector arr = {1,2,1,2,3};
int K = 2, ans = 0;
for(int i=0;i mp;
for(int j=i;j K) break;
ans = max(ans, j - i + 1);
}
}
cout << ans;
}
Java
import java.util.*;
class Prefix {
public static void main(String[] args){
int[] arr = {1,2,1,2,3};
int K = 2, ans = 0;
for(int i=0;i map = new HashMap<>();
for(int j=i;j K) break;
ans = Math.max(ans, j - i + 1);
}
}
System.out.println(ans);
}
}
Python
from collections import defaultdict
arr = [1,2,1,2,3]
K = 2
ans = 0
for i in range(len(arr)):
freq = defaultdict(int)
for j in range(i,len(arr)):
freq[arr[j]] += 1
if len(freq) > K:
break
ans = max(ans, j-i+1)
print(ans)
Output
4Approach 3: Sliding Window (Optimal )
Idea
- Expand window with right
- Shrink from left when distinct count exceeds K
- Track max window length
Time & Space
- Time: O(n)
- Space: O(k)
Implementations (Optimal)
C
#include
int main(){
int arr[] = {1,2,1,2,3};
int n = 5, K = 2;
int freq[1001] = {0};
int left = 0, distinct = 0, ans = 0;
for(int right=0;right K){
freq[arr[left]]--;
if(freq[arr[left]] == 0) distinct--;
left++;
}
if(right - left + 1 > ans)
ans = right - left + 1;
}
printf("%d", ans);
}
C++
#include
using namespace std;
int main(){
vector arr = {1,2,1,2,3};
int K = 2, l = 0, ans = 0;
unordered_map mp;
for(int r=0;r K){
mp[arr[l]]--;
if(mp[arr[l]] == 0) mp.erase(arr[l]);
l++;
}
ans = max(ans, r - l + 1);
}
cout << ans;
}
Java
import java.util.*;
class SlidingWindow {
public static void main(String[] args){
int[] arr = {1,2,1,2,3};
int K = 2, left = 0, ans = 0;
Map map = new HashMap<>();
for(int right=0;right K){
map.put(arr[left], map.get(arr[left])-1);
if(map.get(arr[left]) == 0) map.remove(arr[left]);
left++;
}
ans = Math.max(ans, right - left + 1);
}
System.out.println(ans);
}
}
Python
from collections import defaultdict
arr = [1,2,1,2,3]
K = 2
left = 0
freq = defaultdict(int)
ans = 0
for right in range(len(arr)):
freq[arr[right]] += 1
while len(freq) > K:
freq[arr[left]] -= 1
if freq[arr[left]] == 0:
del freq[arr[left]]
left += 1
ans = max(ans, right - left + 1)
print(ans)
JavaScript
let arr = [1,2,1,2,3];
let K = 2, left = 0, ans = 0;
let map = new Map();
for(let right=0; right K){
map.set(arr[left], map.get(arr[left]) - 1);
if(map.get(arr[left]) === 0) map.delete(arr[left]);
left++;
}
ans = Math.max(ans, right - left + 1);
}
console.log(ans);
C#
using System;
using System.Collections.Generic;
class Program {
static void Main(){
int[] arr = {1,2,1,2,3};
int K = 2, left = 0, ans = 0;
Dictionary map = new Dictionary();
for(int right=0; right K){
map[arr[left]]--;
if(map[arr[left]] == 0) map.Remove(arr[left]);
left++;
}
ans = Math.Max(ans, right - left + 1);
}
Console.WriteLine(ans);
}
}
Output
4.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.jpg)
.png)
.jpg)
.jpg)
.png)
