Problem

Given n integers and a window size m (1 <= m <= n), consider every contiguous subarray (window) of size m. For each window compute the number of unique elements it contains, and return the maximum number of unique elements among all windows.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

Input: arr = [1, 2, 1, 3, 4, 2, 3, 5], m = 3
Output: 3
Explanation:
Windows of size 3 and their unique counts:
[1,2,1] -> 2
[2,1,3] -> 3
[1,3,4] -> 3
[3,4,2] -> 3
[4,2,3] -> 3
[2,3,5] -> 3

This is the HackerRank challenge “Java Dequeue”; there is no exact LeetCode problem with the same name, but it is a straightforward sliding-window frequency/count problem.

Solution

We need a sliding-window that counts distinct values in O(1) amortized time per step. A frequency map (value -> count) updated as the window slides suffices. Optionally a deque can be used to simulate streaming input.

Method 1 — Sliding window with frequency map (array input)

Intuition

Maintain a frequency map of elements inside the current window. The number of keys in the map (or a distinct counter) is the number of unique elements. Move the window by removing the left element’s count and adding the incoming right element’s count.

Approach

  1. Initialize a map freq and the first window by processing the first m elements, updating freq and distinct = freq.size().
  2. Set ans = distinct.
  3. For each subsequent index i from m to n-1:
    • Decrement count of out = arr[i-m] in freq; remove key if count becomes 0.
    • Increment count of in = arr[i] in freq.
    • Update ans = max(ans, freq.size()).
  4. Return ans.

Edge cases:

  • m == 0 -> return 0.
  • If m >= n, the answer is the number of distinct elements in arr.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

#include <vector>
#include <unordered_map>
#include <algorithm>

class Solution {
 public:
  static int maxUniqueInWindow(const std::vector<int>& arr, int m) {
    int n = arr.size();
    if (m == 0 || n == 0) return 0;
    if (m >= n) {
      std::unordered_map<int,int> tmp;
      for (int v : arr) ++tmp[v];
      return tmp.size();
    }
    std::unordered_map<int,int> freq;
    for (int i = 0; i < m; ++i) ++freq[arr[i]];
    int ans = freq.size();
    for (int i = m; i < n; ++i) {
      int out = arr[i - m];
      if (--freq[out] == 0) freq.erase(out);
      ++freq[arr[i]];
      ans = std::max(ans, (int)freq.size());
    }
    return ans;
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

package main

func MaxUniqueInWindow(arr []int, m int) int {
  n := len(arr)
  if m == 0 || n == 0 { return 0 }
  if m >= n {
    freq := make(map[int]int)
    for _, v := range arr { freq[v]++ }
    return len(freq)
  }
  freq := make(map[int]int)
  for i := 0; i < m; i++ { freq[arr[i]]++ }
  ans := len(freq)
  for i := m; i < n; i++ {
    out := arr[i-m]
    freq[out]--
    if freq[out] == 0 { delete(freq, out) }
    freq[arr[i]]++
    if len(freq) > ans { ans = len(freq) }
  }
  return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

import java.util.*;

class Solution {
  public static int maxUniqueInWindow(int[] arr, int m) {
    int n = arr.length;
    if (m == 0 || n == 0) return 0;
    if (m >= n) {
      Set<Integer> s = new HashSet<>();
      for (int v : arr) s.add(v);
      return s.size();
    }
    Map<Integer,Integer> freq = new HashMap<>();
    for (int i = 0; i < m; ++i) freq.merge(arr[i], 1, Integer::sum);
    int ans = freq.size();
    for (int i = m; i < n; ++i) {
      int out = arr[i - m];
      freq.put(out, freq.get(out) - 1);
      if (freq.get(out) == 0) freq.remove(out);
      freq.merge(arr[i], 1, Integer::sum);
      ans = Math.max(ans, freq.size());
    }
    return ans;
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution:
    @staticmethod
    def max_unique_in_window(arr: list[int], m: int) -> int:
        n = len(arr)
        if m == 0 or n == 0:
            return 0
        if m >= n:
            return len(set(arr))
        from collections import Counter
        freq = Counter(arr[:m])
        ans = len(freq)
        for i in range(m, n):
            out = arr[i-m]
            freq[out] -= 1
            if freq[out] == 0:
                del freq[out]
            freq[arr[i]] += 1
            ans = max(ans, len(freq))
        return ans

Complexity

  • ⏰ Time complexity: O(n) — each element is inserted and removed from the frequency map at most once.
  • 🧺 Space complexity: O(k) where k is the number of distinct elements in the current window (at most min(m, alphabet)).

Method 2 — Streaming input using a deque + map

Intuition

If input arrives as a stream (e.g., from stdin), maintain a sliding deque of the last m elements and a frequency map. When a new element arrives, pop from the left, update counts, push the new element on the right, update counts, and track the maximum distinct count.

Code (Java streaming version)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

import java.io.InputStream;
import java.util.*;

class DequeueSolution {
  public static int solution(InputStream is) {
    try (Scanner scanner = new Scanner(is)) {
      int n = scanner.nextInt();
      int m = scanner.nextInt();
      Deque<Integer> window = new ArrayDeque<>();
      Map<Integer,Integer> freq = new HashMap<>();
      for (int i = 0; i < m; ++i) {
        int v = scanner.nextInt();
        window.addLast(v);
        freq.merge(v, 1, Integer::sum);
      }
      int ans = freq.size();
      for (int i = m; i < n; ++i) {
        int out = window.removeFirst();
        int in = scanner.nextInt();
        // remove out
        freq.put(out, freq.get(out) - 1);
        if (freq.get(out) == 0) freq.remove(out);
        // add in
        window.addLast(in);
        freq.merge(in, 1, Integer::sum);
        ans = Math.max(ans, freq.size());
        if (ans == m) break; // early exit: can't exceed m
      }
      return ans;
    }
  }
}

Complexity

  • ⏰ Time complexity: O(n) streaming updates.
  • 🧺 Space complexity: O(m) for the deque and O(k) for the frequency map.