Definition
- Longest subarray with at most K distinct – find the longest contiguous subarray containing at most K different values.
- Fruit Into Baskets – the special case where K=2, framed as two baskets each holding one fruit type.
- HashMap tracking – a map counts occurrences of each value in the window; the map size equals the distinct count.
- Zero-count removal – remove a key when its count drops to zero so the map size stays accurate.
- Complexity – O(n) time amortized, O(K) space for the map.
The National Bank of India wants the longest run of consecutive card transactions that touches at most K different merchant categories, as a loyalty-pattern signal. Rajesh grows a window and tallies how many distinct categories it holds. When a new category pushes the count past K, he shrinks from the left, removing categories until only K remain.
Understanding the Concepts
What is the Longest Subarray with At Most K Distinct problem?
Given an array of values and an integer K, find the length of the longest contiguous subarray that contains at most K distinct values. The Fruit Into Baskets problem on LeetCode is the K=2 special case, where each fruit type maps to one of two baskets.
package com.bank.service;
import java.util.HashMap;
import java.util.Map;
public class LongestAtMostKDistinct {
public static int longestWithKDistinct(int[] arr, int k) {
Map<Integer, Integer> countMap = new HashMap<>();
int left = 0, best = 0;
for (int right = 0; right < arr.length; right++) {
countMap.merge(arr[right], 1, Integer::sum); // add entering element
while (countMap.size() > k) { // too many distinct
int leftVal = arr[left];
countMap.merge(leftVal, -1, Integer::sum); // decrement leaving
if (countMap.get(leftVal) == 0) {
countMap.remove(leftVal); // critical: remove zero-count
}
left++;
}
best = Math.max(best, right - left + 1);
}
return best;
}
public static void main(String[] args) {
// Merchant categories: 3=food, 5=travel, 3=food, 7=retail, 3=food, 5=travel
int[] categories = {3, 5, 3, 7, 3, 5};
System.out.println("Longest with at most 2 distinct: "
+ longestWithKDistinct(categories, 2));
}
}
Longest with at most 2 distinct: 3
Why must you remove keys when count reaches zero?
The map's size is how you measure distinctness. If you leave a zero-count key in the map, the size overstates the number of distinct values in the window. This causes the shrink loop to trigger when it should not, making the window shrink more than necessary and producing a wrong answer.
// WRONG: leaving zero-count key in map
countMap.merge(leftVal, -1, Integer::sum);
// countMap.size() still counts leftVal, even though it is gone from the window
// This overstates distinct count and shrinks the window too much
// CORRECT: remove key when count reaches zero
countMap.merge(leftVal, -1, Integer::sum);
if (countMap.get(leftVal) == 0) {
countMap.remove(leftVal); // keeps the size accurate
}
How is Fruit Into Baskets the K=2 case?
Fruit Into Baskets says you walk through a row of fruit trees and have two baskets, each holding one type of fruit. You want the longest contiguous stretch you can pick from. This is exactly the longest subarray with at most 2 distinct values.
package com.bank.service;
public class FruitIntoBaskets {
public static int totalFruit(int[] tree) {
return LongestAtMostKDistinct.longestWithKDistinct(tree, 2);
}
public static void main(String[] args) {
int[] trees = {1, 2, 1, 2, 3, 3, 1};
System.out.println("Max fruits: " + totalFruit(trees)); // 4 (subarray [1,2,1,2])
}
}
Max fruits: 4
How does the shrink loop maintain the invariant?
The inner while loop shrinks only as much as needed to restore the at-most-K condition. It never over-shrinks, which preserves the longest valid window ending at the current right position.
// Walkthrough: arr = [3, 5, 3, 7, 3, 5], K=2
// right=0: map={3:1}, size=1 <= 2, best=1
// right=1: map={3:1,5:1}, size=2 <= 2, best=2
// right=2: map={3:2,5:1}, size=2 <= 2, best=3
// right=3: map={3:2,5:1,7:1}, size=3 > 2
// shrink: remove arr[0]=3 -> map={3:1,5:1,7:1} size=3 > 2
// shrink: remove arr[1]=5 -> count=0, remove key -> map={3:1,7:1} size=2
// left=2, best=max(3, 3-2+1)=max(3,2)=3
// right=4: map={3:2,7:1}, size=2 <= 2, best=3
// right=5: map={3:2,7:1,5:1}, size=3 > 2
// shrink: remove arr[2]=3 -> map={3:1,7:1,5:1} size=3 > 2
// shrink: remove arr[3]=7 -> count=0, remove key -> map={3:1,5:1} size=2
// left=4, best=max(3, 5-4+1)=max(3,2)=3
// Final best=3
Why is the time linear despite the nested loop?
The left pointer only ever advances. Each element enters the window once when right moves over it and leaves the window once when left moves past it. The total number of left-pointer advances across all iterations of the outer loop is bounded by n. So the total work is O(n), not O(n^2).
// Amortized analysis:
// right advances n times (outer for loop)
// left advances at most n times total (inner while loop, summed across all right)
// Each element enters and leaves the window exactly once
// Total operations: at most 2n = O(n)
What are the edge cases?
If K is zero, no elements are allowed, so the answer is zero. If K is greater than or equal to the number of distinct values in the entire array, the answer is the full array length. An empty array returns zero.
package com.bank.service;
public class KDistinctEdgeCases {
public static void main(String[] args) {
System.out.println(LongestAtMostKDistinct.longestWithKDistinct(new int[]{}, 2)); // 0
System.out.println(LongestAtMostKDistinct.longestWithKDistinct(new int[]{1,2,3}, 0)); // 0
System.out.println(LongestAtMostKDistinct.longestWithKDistinct(new int[]{1,2,3}, 5)); // 3
}
}
0
0
3
What are common mistakes?
The most critical mistake is not removing zero-count keys from the map, which overstates distinctness. Another mistake is using countMap.size() > k with strict inequality when it should be strict (it should be: shrink while size > k, which is correct).
// WRONG: not removing zero-count key
// Map: {A:0, B:2, C:1} -> size=3 even though A is not in the window
// This causes unnecessary shrinking
// CORRECT: always remove keys at zero count
if (countMap.get(leftVal) == 0) countMap.remove(leftVal);
When should you use this technique?
Use this whenever you need the longest contiguous subrange with a constraint on distinct elements. In banking, this applies to finding the longest run of transactions touching at most K merchant categories, or the longest period where an account interacts with at most K counterparties.
package com.bank.service;
public class LoyaltyAnalytics {
public static void main(String[] args) {
// Merchant IDs for recent transactions
int[] merchants = {101, 202, 101, 303, 202, 101, 303};
int maxCategories = 2;
int longestRun = LongestAtMostKDistinct.longestWithKDistinct(merchants, maxCategories);
System.out.println("Longest concentrated spending streak: " + longestRun);
}
}
Longest concentrated spending streak: 4
What should a senior engineer know?
A senior engineer should understand the zero-count removal detail, the amortized linear analysis, and the generalization from K=2 (Fruit Into Baskets) to arbitrary K. Using merge for count updates keeps the code concise and correct, and the map size as the distinct measure is the idiomatic approach.
What are common interview follow-up questions?
- Interviewers commonly ask:
- Why remove zero-count keys? (Map size is the distinct measure; leaving stale keys overstates it.)
- What is the time complexity? (O(n) amortized because left only advances.)
- What if K=2? (Fruit Into Baskets, same algorithm.)
- What if you need the actual subarray, not just the length? (Track the left and right indices of the best window.)
Visual Overview
Variable window with K=2 distinct:
Input: [3, 5, 3, 7, 3, 5]
┌─────────────────────────────┐
│ right=0: [3] │
│ map: {3:1}, best=1 │
│ right=1: [3,5] │
│ map: {3:1,5:1}, best=2 │
│ right=2: [3,5,3] │
│ map: {3:2,5:1}, best=3 │
│ right=3: [3,5,3,7] │
│ map: {3:2,5:1,7:1} > K │
│ shrink → [5,3,7] │
│ shrink → [3,7] │
│ map: {3:1,7:1}, best=3 │
│ right=4: [3,7,3] │
│ map: {3:2,7:1}, best=3 │
│ right=5: [3,7,3,5] │
│ map: {3:2,7:1,5:1} > K │
│ shrink → [7,3,5] │
│ shrink → [3,5] │
│ map: {3:1,5:1}, best=3 │
└─────────────────────────────┘
Answer: 3
Key Takeaway
The longest subarray with at most K distinct values is a variable-size sliding window problem backed by a count map. You grow the window on the right, incrementing the count of each entering value. Whenever the number of distinct values in the window (the map size) exceeds K, you shrink from the left by decrementing counts and advancing the left pointer.
The one detail that must not be forgotten is removing a key from the map when its count drops to zero. The map's size is the distinct measure, so a stale zero-count key overstates distinctness and causes the window to shrink incorrectly. Removing the key keeps the measure exact.
The Fruit Into Baskets problem is literally this with K=2, framed as two baskets each holding one fruit type. Recognizing that specialization shows the interviewer you understand the general pattern rather than memorizing a specific solution.
In the analytics service at the National Bank of India, Rajesh finds the longest run of consecutive card transactions that stay within at most K distinct merchant categories, as a signal of concentrated spending for a targeted reward program. The zero-count key removal keeps the distinct count accurate, and the amortized linear time handles long transaction histories efficiently.
Remember one sentence: expand right tracking distinct counts in a map, shrink left when distinct exceeds K, and always remove zero-count keys to keep the measure accurate.
---