☕ DSA Java Articles

Topics › Sliding Window and Two Pointers › Medium Problems

Distinct Numbers in Each Subarray

Medium TUF ID 279 SDE

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given an integer array nums of length n and a window size k. For every contiguous window of length k, count how many distinct values it contains. Return the counts as an array ans of length n - k + 1, where ans[i] is the number of distinct values in nums[i..i+k-1]. This is also known as “count distinct elements in every window of size k”.

Constraints (LeetCode): 1 ≤ k ≤ n ≤ 10^5 and 1 ≤ nums[i] ≤ 10^5. The code here also accepts negative values, and returns an empty array when k > n (there is no window) or k ≤ 0.

Example 1

nums = [1, 2, 3, 2, 2, 1, 3], k = 3
ans  = [3, 2, 2, 2, 3]

The windows are [1,2,3], [2,3,2], [3,2,2], [2,2,1] and [2,1,3], with 3, 2, 2, 2 and 3 distinct values.

Example 2

nums = [1, 1, 1, 1, 2, 3, 4], k = 4
ans  = [1, 2, 3, 4]

Each step to the right swaps one 1 for a new value, so the count grows by one per window.

Approach 1: Brute force, a fresh set per window

Intuition. Treat each window as its own small problem: put its k values into a hash set and read the set’s size, because a set keeps exactly one copy of each value. It is obviously correct, but neighbouring windows share k - 1 elements and we re-insert all of them every time.

Algorithm.

  1. If k is not in 1..n, return an empty array.
  2. For each start i from 0 to n - k: insert nums[i..i+k-1] into a new HashSet and store its size in ans[i].
static int[] bruteForce(int[] nums, int k) {
    int n = nums.length;
    if (k <= 0 || k > n) return new int[0];
    int[] ans = new int[n - k + 1];
    for (int i = 0; i + k <= n; i++) {
        Set<Integer> seen = new HashSet<>();
        for (int j = i; j < i + k; j++) seen.add(nums[j]);
        ans[i] = seen.size();
    }
    return ans;
}

Complexity. Time O((n - k + 1) · k), which peaks at about n^2 / 4 when k ≈ n / 2: roughly 2.5 · 10^9 set operations for n = 10^5. Space O(k) for the set.

Approach 2: Optimal, sliding window with a frequency map

Intuition. Moving the window one step to the right changes it by exactly two elements: nums[l] leaves on the left and nums[r] enters on the right. If we can update the distinct count in O(1) for each of those two events, the whole scan is linear.

A plain set is not enough. When nums[l] leaves, we cannot simply remove it from the set, because another copy of the same value may still be inside the window (window [2, 3, 2] losing its first 2 still contains a 2). What we need is how many copies of each value the window holds. So we keep a map from value to count:

Because zero-count keys are always removed, the number of keys in the map is exactly the number of distinct values in the window.

Algorithm.

  1. For r from 0 to n - 1, add nums[r] to the map (merge with Integer::sum).
  2. Let l = r - k + 1. If l < 0, the first window is not complete yet, so continue.
  3. Record ans[l] = map.size(). This must happen before removing nums[l], because [l..r] is the window being answered.
  4. Decrement nums[l]. computeIfPresent deletes the key when the remapping function returns null, which handles the “count reached zero” case in one call.
static int[] optimal(int[] nums, int k) {
    int n = nums.length;
    if (k <= 0 || k > n) return new int[0];
    int[] ans = new int[n - k + 1];
    Map<Integer, Integer> freq = new HashMap<>();
    for (int r = 0; r < n; r++) {
        freq.merge(nums[r], 1, Integer::sum);               // nums[r] enters the window
        int l = r - k + 1;                                  // left end of the window ending at r
        if (l < 0) continue;                                // window not full yet
        ans[l] = freq.size();
        freq.computeIfPresent(nums[l], (v, c) -> c == 1 ? null : c - 1);   // nums[l] leaves; null removes the key
    }
    return ans;
}

Dry run on Example 1 (k = 3):

r enters map after entering l ans[l] leaves map after leaving
0 1 {1:1} -2      
1 2 {1:1, 2:1} -1      
2 3 {1:1, 2:1, 3:1} 0 3 1 {2:1, 3:1}
3 2 {2:2, 3:1} 1 2 2 {2:1, 3:1}
4 2 {2:2, 3:1} 2 2 3 {2:2}
5 1 {2:2, 1:1} 3 2 2 {2:1, 1:1}
6 3 {2:1, 1:1, 3:1} 4 3 2 {1:1, 3:1}

Row r = 3 shows why counts matter: the 2 leaving at index 1 does not remove 2 from the window, because index 3 holds another copy.

Complexity. Time O(n) on average: each element enters once and leaves once, and each map operation is expected O(1). Space O(k): the map never holds more than k keys.

Approach 3: Same window, plain count array

Intuition. When the values come from a small range, as in LeetCode’s 1..10^5, a hash map is overkill. An int array indexed by value - min gives the same counts with no hashing and no Integer boxing. Since an array has no “size” of live keys, we maintain the distinct count ourselves by watching the transitions: a count going from 0 to 1 means a new distinct value has appeared, and a count going from 1 to 0 means one has disappeared.

The array has max - min + 1 slots. If that range is huge (say values span the whole int range), allocating it would be absurd, so the method falls back to the map version. The range is computed in long because max - min + 1 can overflow int.

Algorithm.

  1. Find min and max. If the range exceeds 10^7, delegate to approach 2.
  2. For each r: if count[nums[r] - min] was 0 before incrementing, increment distinct.
  3. Once the window is full, store ans[l] = distinct; then decrement the count of nums[l] and decrement distinct if it fell to 0.
static int[] optimalCountArray(int[] nums, int k) {
    int n = nums.length;
    if (k <= 0 || k > n) return new int[0];
    int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
    for (int x : nums) { min = Math.min(min, x); max = Math.max(max, x); }
    if ((long) max - min + 1 > 10_000_000) return optimal(nums, k);   // range too wide for an array
    int[] count = new int[max - min + 1];                 // count[x - min] = copies of x in the window
    int[] ans = new int[n - k + 1];
    int distinct = 0;
    for (int r = 0; r < n; r++) {
        if (count[nums[r] - min]++ == 0) distinct++;        // first copy entering
        int l = r - k + 1;
        if (l < 0) continue;
        ans[l] = distinct;
        if (--count[nums[l] - min] == 0) distinct--;        // last copy leaving
    }
    return ans;
}

Complexity. Time O(n + R) where R = max - min + 1 (allocating the array is the R part). Space O(R) for the counts plus the output. With bounded values this is the fastest of the three in practice.

Edge cases and pitfalls