3934. Smallest Unique Subarray

HardArrayHash TableBinary SearchSuffix ArrayHash FunctionRolling Hash

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

You are given an integer array nums.

Your task is to look at all the possible subarrays of nums and find one special subarray: a subarray whose exact sequence of elements does not appear anywhere else in nums as another subarray. Among all such "one-of-a-kind" subarrays, you want the one with the smallest length.

Return an integer denoting the minimum possible length of such a subarray.

A subarray is a contiguous (non-empty) part of the array. Two subarrays are considered identical if they meet both of these conditions:

They have the same length, and
They have the same elements in the same corresponding positions.

In other words, a subarray is unique if there is no other subarray (sitting at a different starting position) that has the same length and matches it element by element. You need to find the shortest length at which at least one unique subarray exists.

Example walkthrough of the idea:

For a length L, slide a window of size L across nums and collect every subarray of that length.
If some subarray of length L shows up only once across the whole array, then a unique subarray of length L exists.
The answer is the smallest such L.

A useful observation: if a unique subarray exists at some length L, then a unique subarray is also guaranteed to exist at every length greater than L. This means the property of "a unique subarray exists" is monotonic with respect to the length, which makes the answer searchable in an efficient, ordered way.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Binary Search?

This problem maps to Binary Search through a short path in the full flowchart.

Binary search works because the feasibility condition is monotonic.

Open in Flowchart

Intuition

The first thing to notice is the relationship between subarray lengths. Suppose we found a unique subarray of length L — meaning no other subarray of length L matches it. If we now extend that subarray by one element (making it length L + 1), the new, longer subarray must also be unique. Why? Because if two longer subarrays were identical, then their shorter inner pieces would have to be identical too, which would contradict the uniqueness we already had. So once uniqueness appears at some length, it never disappears for larger lengths.

This gives us a clean monotonic picture:

For small lengths, there might be no unique subarray (everything has a duplicate).
Past some threshold length, a unique subarray always exists.

The answer is exactly that threshold — the smallest length where uniqueness first kicks in. Whenever a problem has this "false, false, ..., false, true, true, ..., true" structure, it is a strong signal that we can binary search on the answer instead of checking every length one by one. We just need a way to test a single length: "Does a unique subarray of length L exist?" If yes, we try smaller lengths; if no, we try larger ones.

Now the question becomes: how do we efficiently check whether any subarray of a fixed length L is unique? The straightforward idea is to grab every subarray of length L and count how many times each one appears. If any of them appears exactly once, the answer for this length is "yes."

But directly comparing subarrays element by element is slow, because each comparison costs up to L operations. To speed this up, we represent each subarray by a single number — a hash — so that comparing subarrays becomes comparing numbers. To make sliding the window fast, we use a rolling hash: when the window moves one step to the right, we don't recompute everything. Instead, we subtract the contribution of the element leaving on the left and add the contribution of the element entering on the right. This keeps each window update at O(1) time.

Putting it together: we slide the rolling hash across all windows of length L, store each hash in a dictionary, and tally the counts. If any hash value has a count of exactly 1, a unique subarray of that length exists. Binary search then narrows down to the smallest length where this happens, giving an efficient overall solution.

Pattern Learn more about Binary Search patterns.

Solution Approach

Solution 1: Rolling Hash + Binary Search

We combine two ideas: binary search on the answer (the subarray length), and a rolling hash to test each candidate length quickly.

Step 1: Binary search on the length

We search for the smallest length at which a unique subarray exists. We set up two bounds:

min_len = 1 (the shortest possible subarray)
max_len = len(nums) (the whole array)

We also keep min_possible_len = len(nums) as a fallback answer.

At each step, we take the middle length mid_len = (min_len + max_len) // 2 and ask: "Does a unique subarray of length mid_len exist?"

If yes, this length works, so we record it (min_possible_len = mid_len if it's smaller) and try to do better by searching the smaller half: max_len = mid_len - 1.
If no, no unique subarray is that short, so we search the larger half: min_len = mid_len + 1.

This loop runs O(log n) times.

Step 2: Checking a fixed length with rolling hash

The helper _check_uniqueness(subarray_len) answers whether any subarray of length subarray_len appears exactly once.

Precompute the powers. We treat each subarray as a number in base base = 19, taken modulo modulo = 10**9 + 7 to keep values small. The array powers[i] stores base^i % modulo, built bottom-up:

self.powers[idx] = (self.powers[idx - 1] * self.base) % self.modulo

These powers let us remove the leftmost element when the window slides.

Compute the first window's hash. We build the hash of the first subarray_len elements by treating them as digits:

current_hash = current_hash * base + nums[idx]

This forms a single number representing that subarray, reduced modulo modulo.

Slide the window. For each subsequent window, we update the hash in O(1):

Remove the leftmost element's contribution. The element nums[idx - 1] sits at the highest place value, so we subtract powers[subarray_len - 1] * nums[idx - 1].
Shift left and add the new element. Multiply by base (to shift all remaining digits up one place) and add the new rightmost element nums[idx + subarray_len - 1], then take modulo.

current_hash -= self.powers[subarray_len - 1] * self.nums[idx - 1]
current_hash *= self.base
current_hash += self.nums[idx + subarray_len - 1]
current_hash %= self.modulo

Count the hashes. We use a dictionary hash_values mapping each hash to how many times it appears. We clear it before each check, then increment the count for every window's hash.

Decide uniqueness. After sliding through all windows, if any hash value has a count of exactly 1, a unique subarray of this length exists:

return 1 in self.hash_values.values()

Data structures and patterns used

Binary search on the answer — exploits the monotonic property that uniqueness, once present, persists at larger lengths.
Rolling (polynomial) hash — represents each subarray as one number and updates in O(1) as the window slides.
Hash map — counts occurrences of each subarray's hash so we can detect a count of exactly 1.

Complexity

Time complexity: O(n log n). There are O(log n) binary search iterations, and each call to _check_uniqueness does an O(n) pass over the array.
Space complexity: O(n), for the powers array and the hash_values dictionary, where n is the length of nums.

Example Walkthrough

Let's trace through the solution approach with a small example.

Input: nums = [1, 2, 3, 2, 1] (length n = 5)

We want the minimum length at which some subarray appears exactly once.

Setting up the binary search

min_len = 1, max_len = 5, min_possible_len = 5
We binary search on the length, testing each mid_len with _check_uniqueness.

The constants for the rolling hash: base = 19, modulo = 10**9 + 7.

Iteration 1: `mid_len = (1 + 5) // 2 = 3`

We check if any length-3 subarray is unique. Slide a window of size 3:

Window (start idx)	Subarray	Rolling hash (conceptually)
0	`[1, 2, 3]`	`1·19² + 2·19 + 3 = 402`
1	`[2, 3, 2]`	`2·19² + 3·19 + 2 = 781`
2	`[3, 2, 1]`	`3·19² + 2·19 + 1 = 1122`

Sliding update example (window 0 → window 1):

Remove leftmost nums[0] = 1: 402 − powers[2]·1 = 402 − 361 = 41
Shift left: 41 · 19 = 779
Add new element nums[3] = 2: 779 + 2 = 781 ✓ (matches direct computation)

Counts: {402: 1, 781: 1, 1122: 1} — all appear once.

Since 1 in counts.values() → yes, a unique length-3 subarray exists.

Record min_possible_len = 3.
Try smaller: max_len = mid_len - 1 = 2.

Iteration 2: `mid_len = (1 + 2) // 2 = 1`

We check if any length-1 subarray is unique. Each window is a single element:

Window (start idx)	Subarray	Hash
0	`[1]`	1
1	`[2]`	2
2	`[3]`	3
3	`[2]`	2
4	`[1]`	1

Counts: {1: 2, 2: 2, 3: 1}

The value 3 appears exactly once, so 1 in counts.values() → yes.

Record min_possible_len = 1.
Try smaller: max_len = mid_len - 1 = 0.

Loop ends

Now min_len = 1 > max_len = 0, so the binary search stops.

Answer: min_possible_len = 1.

The element 3 (at index 2) is the unique subarray of minimum length — it never repeats anywhere else in the array.

Why binary search was safe here

Notice the monotonic pattern across lengths:

Length `L`	Unique subarray exists?
1	✅ yes (`[3]`)
2	✅ yes
3	✅ yes
4	✅ yes
5	✅ yes (whole array)

Once uniqueness appears, it persists for all larger lengths — the classic ... false, true, true ... shape — so binary search correctly homes in on the smallest valid length while skipping a linear scan over every length.

Solution Implementation

1from typing import Dict, List
2
3
4class Solution:
5    def smallestUniqueSubarray(self, nums: List[int]) -> int:
6        n = len(nums)
7
8        base = 19
9        modulo = 10**9 + 7
10
11        # Precompute base powers once: powers[i] = base^i mod modulo.
12        powers = [1] * (n + 1)
13        for idx in range(1, n + 1):
14            powers[idx] = (powers[idx - 1] * base) % modulo
15
16        # Try every possible window length, smallest first, and return
17        # the first length that has at least one uniquely-occurring window.
18        for window_len in range(1, n + 1):
19            if self._has_unique_window(nums, window_len, base, modulo, powers):
20                return window_len
21
22        return n  # Fallback (every element distinct trivially gives length 1).
23
24    def _has_unique_window(
25        self,
26        nums: List[int],
27        window_len: int,
28        base: int,
29        modulo: int,
30        powers: List[int],
31    ) -> bool:
32        n = len(nums)
33
34        # Count occurrences of each window hash.
35        hash_counts: Dict[int, int] = {}
36
37        # Build the hash of the first window [0, window_len).
38        current_hash = 0
39        for idx in range(window_len):
40            current_hash = (current_hash * base + nums[idx]) % modulo
41        hash_counts[current_hash] = 1
42
43        # Slide the window across the array.
44        for idx in range(1, n - window_len + 1):
45            # Remove the contribution of the element leaving the window.
46            leftmost_contribution = (powers[window_len - 1] * nums[idx - 1]) % modulo
47            current_hash = (current_hash - leftmost_contribution) % modulo
48
49            # Shift remaining elements up one power, then add the new element.
50            current_hash = (current_hash * base + nums[idx + window_len - 1]) % modulo
51
52            hash_counts[current_hash] = hash_counts.get(current_hash, 0) + 1
53
54        # A unique window exists if any hash was seen exactly once.
55        return 1 in hash_counts.values()
56```
57
58## Faithful Rewrite (preserving original structure)
59
60If instead you want the original logic preserved (binary search + same flow) just cleaned up with `python3` typing, standardized naming, and fixed obvious bugs (modulo after subtraction, single power precompute):
61
62```python3
63from typing import Dict, List
64
65
66class Solution:
67    def smallestUniqueSubarray(self, nums: List[int]) -> int:
68        self.nums = nums
69        self.base = 19
70        self.modulo = 10**9 + 7
71
72        # Precompute base powers: powers[i] = base^i mod modulo.
73        self.powers = [1] * (len(nums) + 1)
74        for idx in range(1, len(nums) + 1):
75            self.powers[idx] = (self.powers[idx - 1] * self.base) % self.modulo
76
77        self.hash_values: Dict[int, int] = {}
78
79        min_possible_len = len(nums)            # Base/default answer.
80        min_len, max_len = 1, len(nums)         # Binary search bounds.
81
82        # NOTE: binary search assumes a monotonic predicate, which is not
83        # guaranteed for this problem; kept here to mirror the original code.
84        while min_len <= max_len:
85            mid_len = (min_len + max_len) // 2
86
87            if self._check_uniqueness(mid_len):
88                min_possible_len = min(min_possible_len, mid_len)
89                max_len = mid_len - 1
90            else:
91                min_len = mid_len + 1
92
93        return min_possible_len
94
95    def _check_uniqueness(self, subarray_len: int) -> bool:
96        # Build the hash for the first window.
97        current_hash = 0
98        for idx in range(subarray_len):
99            current_hash = (current_hash * self.base + self.nums[idx]) % self.modulo
100
101        self.hash_values.clear()
102        self.hash_values[current_hash] = 1
103
104        # Slide the window one position at a time.
105        for idx in range(1, len(self.nums) - subarray_len + 1):
106            # Drop the leftmost element's contribution.
107            leftmost = (self.powers[subarray_len - 1] * self.nums[idx - 1]) % self.modulo
108            current_hash = (current_hash - leftmost) % self.modulo
109
110            # Shift and add the new rightmost element.
111            current_hash = (current_hash * self.base + self.nums[idx + subarray_len - 1]) % self.modulo
112
113            self.hash_values[current_hash] = self.hash_values.get(current_hash, 0) + 1
114
115        # True if any window appears exactly once.
116        return 1 in self.hash_values.values()
117

1import java.util.HashMap;
2import java.util.Map;
3
4class Solution {
5    // Primary (correct) approach: try each window length from smallest to largest.
6    public int smallestUniqueSubarray(int[] nums) {
7        int n = nums.length;
8
9        long base = 19;
10        long modulo = 1_000_000_007L;
11
12        // Precompute base powers once: powers[i] = base^i mod modulo.
13        long[] powers = new long[n + 1];
14        powers[0] = 1;
15        for (int idx = 1; idx <= n; idx++) {
16            powers[idx] = (powers[idx - 1] * base) % modulo;
17        }
18
19        // Try every possible window length, smallest first, and return
20        // the first length that has at least one uniquely-occurring window.
21        for (int windowLen = 1; windowLen <= n; windowLen++) {
22            if (hasUniqueWindow(nums, windowLen, base, modulo, powers)) {
23                return windowLen;
24            }
25        }
26
27        return n; // Fallback (every element distinct trivially gives length 1).
28    }
29
30    private boolean hasUniqueWindow(
31            int[] nums,
32            int windowLen,
33            long base,
34            long modulo,
35            long[] powers) {
36        int n = nums.length;
37
38        // Count occurrences of each window hash.
39        Map<Long, Integer> hashCounts = new HashMap<>();
40
41        // Build the hash of the first window [0, windowLen).
42        long currentHash = 0;
43        for (int idx = 0; idx < windowLen; idx++) {
44            currentHash = (currentHash * base + nums[idx]) % modulo;
45        }
46        hashCounts.put(currentHash, 1);
47
48        // Slide the window across the array.
49        for (int idx = 1; idx <= n - windowLen; idx++) {
50            // Remove the contribution of the element leaving the window.
51            long leftmostContribution = (powers[windowLen - 1] * nums[idx - 1]) % modulo;
52            // Add modulo before taking modulo again to avoid negative values.
53            currentHash = ((currentHash - leftmostContribution) % modulo + modulo) % modulo;
54
55            // Shift remaining elements up one power, then add the new element.
56            currentHash = (currentHash * base + nums[idx + windowLen - 1]) % modulo;
57
58            hashCounts.merge(currentHash, 1, Integer::sum);
59        }
60
61        // A unique window exists if any hash was seen exactly once.
62        return hashCounts.containsValue(1);
63    }
64}
65```
66
67And here is the **faithful rewrite** preserving the original binary-search structure:
68
69```java
70import java.util.HashMap;
71import java.util.Map;
72
73class Solution {
74    private int[] nums;
75    private long base;
76    private long modulo;
77    private long[] powers;
78    private Map<Long, Integer> hashValues;
79
80    public int smallestUniqueSubarray(int[] nums) {
81        this.nums = nums;
82        this.base = 19;
83        this.modulo = 1_000_000_007L;
84
85        // Precompute base powers: powers[i] = base^i mod modulo.
86        this.powers = new long[nums.length + 1];
87        this.powers[0] = 1;
88        for (int idx = 1; idx <= nums.length; idx++) {
89            this.powers[idx] = (this.powers[idx - 1] * this.base) % this.modulo;
90        }
91
92        this.hashValues = new HashMap<>();
93
94        int minPossibleLen = nums.length;        // Base/default answer.
95        int minLen = 1, maxLen = nums.length;    // Binary search bounds.
96
97        // NOTE: binary search assumes a monotonic predicate, which is not
98        // guaranteed for this problem; kept here to mirror the original code.
99        while (minLen <= maxLen) {
100            int midLen = (minLen + maxLen) / 2;
101
102            if (checkUniqueness(midLen)) {
103                minPossibleLen = Math.min(minPossibleLen, midLen);
104                maxLen = midLen - 1;
105            } else {
106                minLen = midLen + 1;
107            }
108        }
109
110        return minPossibleLen;
111    }
112
113    private boolean checkUniqueness(int subarrayLen) {
114        // Build the hash for the first window.
115        long currentHash = 0;
116        for (int idx = 0; idx < subarrayLen; idx++) {
117            currentHash = (currentHash * this.base + this.nums[idx]) % this.modulo;
118        }
119
120        this.hashValues.clear();
121        this.hashValues.put(currentHash, 1);
122
123        // Slide the window one position at a time.
124        for (int idx = 1; idx <= this.nums.length - subarrayLen; idx++) {
125            // Drop the leftmost element's contribution.
126            long leftmost = (this.powers[subarrayLen - 1] * this.nums[idx - 1]) % this.modulo;
127            // Add modulo before re-taking modulo to keep the value non-negative.
128            currentHash = ((currentHash - leftmost) % this.modulo + this.modulo) % this.modulo;
129
130            // Shift and add the new rightmost element.
131            currentHash = (currentHash * this.base + this.nums[idx + subarrayLen - 1]) % this.modulo;
132
133            this.hashValues.merge(currentHash, 1, Integer::sum);
134        }
135
136        // True if any window appears exactly once.
137        return this.hashValues.containsValue(1);
138    }
139}
140

1#include <vector>
2#include <unordered_map>
3using namespace std;
4
5class Solution {
6public:
7    int smallestUniqueSubarray(vector<int>& nums) {
8        int n = static_cast<int>(nums.size());
9
10        const long long base = 19;
11        const long long modulo = 1000000007LL;
12
13        // Precompute base powers once: powers[i] = base^i mod modulo.
14        vector<long long> powers(n + 1, 1);
15        for (int idx = 1; idx <= n; ++idx) {
16            powers[idx] = (powers[idx - 1] * base) % modulo;
17        }
18
19        // Try every possible window length, smallest first, and return
20        // the first length that has at least one uniquely-occurring window.
21        for (int window_len = 1; window_len <= n; ++window_len) {
22            if (has_unique_window(nums, window_len, base, modulo, powers)) {
23                return window_len;
24            }
25        }
26
27        return n; // Fallback (every element distinct trivially gives length 1).
28    }
29
30private:
31    bool has_unique_window(
32        const vector<int>& nums,
33        int window_len,
34        long long base,
35        long long modulo,
36        const vector<long long>& powers
37    ) {
38        int n = static_cast<int>(nums.size());
39
40        // Count occurrences of each window hash.
41        unordered_map<long long, int> hash_counts;
42
43        // Build the hash of the first window [0, window_len).
44        long long current_hash = 0;
45        for (int idx = 0; idx < window_len; ++idx) {
46            current_hash = (current_hash * base + nums[idx]) % modulo;
47        }
48        hash_counts[current_hash] = 1;
49
50        // Slide the window across the array.
51        for (int idx = 1; idx <= n - window_len; ++idx) {
52            // Remove the contribution of the element leaving the window.
53            long long leftmost_contribution =
54                (powers[window_len - 1] * nums[idx - 1]) % modulo;
55            current_hash = (current_hash - leftmost_contribution) % modulo;
56
57            // Keep the value non-negative after subtraction under modulo.
58            if (current_hash < 0) {
59                current_hash += modulo;
60            }
61
62            // Shift remaining elements up one power, then add the new element.
63            current_hash = (current_hash * base + nums[idx + window_len - 1]) % modulo;
64
65            ++hash_counts[current_hash];
66        }
67
68        // A unique window exists if any hash was seen exactly once.
69        for (const auto& entry : hash_counts) {
70            if (entry.second == 1) {
71                return true;
72            }
73        }
74        return false;
75    }
76};
77

1// Rolling-hash configuration shared across helper functions.
2const BASE = 19;
3// Use BigInt for the modulo to avoid precision loss in hash arithmetic.
4const MODULO = 1_000_000_007n;
5
6/**
7 * Finds the smallest window length such that at least one window of that
8 * length has a uniquely-occurring hash (appears exactly once).
9 */
10function smallestUniqueSubarray(nums: number[]): number {
11    const n = nums.length;
12
13    // Precompute base powers once: powers[i] = BASE^i mod MODULO.
14    const powers: bigint[] = new Array(n + 1).fill(1n);
15    for (let idx = 1; idx <= n; idx++) {
16        powers[idx] = (powers[idx - 1] * BigInt(BASE)) % MODULO;
17    }
18
19    // Try every possible window length, smallest first, and return the first
20    // length that has at least one uniquely-occurring window.
21    for (let windowLen = 1; windowLen <= n; windowLen++) {
22        if (hasUniqueWindow(nums, windowLen, powers)) {
23            return windowLen;
24        }
25    }
26
27    // Fallback (every element distinct trivially gives length 1).
28    return n;
29}
30
31/**
32 * Checks whether any window of the given length occurs exactly once,
33 * using a rolling hash to compare windows efficiently.
34 */
35function hasUniqueWindow(
36    nums: number[],
37    windowLen: number,
38    powers: bigint[],
39): boolean {
40    const n = nums.length;
41    const baseBig = BigInt(BASE);
42
43    // Count occurrences of each window hash.
44    const hashCounts = new Map<bigint, number>();
45
46    // Build the hash of the first window [0, windowLen).
47    let currentHash = 0n;
48    for (let idx = 0; idx < windowLen; idx++) {
49        currentHash = (currentHash * baseBig + BigInt(nums[idx])) % MODULO;
50    }
51    hashCounts.set(currentHash, 1);
52
53    // Slide the window across the array.
54    for (let idx = 1; idx <= n - windowLen; idx++) {
55        // Remove the contribution of the element leaving the window.
56        const leftmostContribution =
57            (powers[windowLen - 1] * BigInt(nums[idx - 1])) % MODULO;
58        currentHash = (currentHash - leftmostContribution) % MODULO;
59
60        // Normalize to keep the hash non-negative after subtraction.
61        if (currentHash < 0n) {
62            currentHash += MODULO;
63        }
64
65        // Shift remaining elements up one power, then add the new element.
66        currentHash =
67            (currentHash * baseBig + BigInt(nums[idx + windowLen - 1])) % MODULO;
68
69        hashCounts.set(currentHash, (hashCounts.get(currentHash) ?? 0) + 1);
70    }
71
72    // A unique window exists if any hash was seen exactly once.
73    for (const count of hashCounts.values()) {
74        if (count === 1) {
75            return true;
76        }
77    }
78    return false;
79}
80

Time and Space Complexity

Time Complexity: O(n log n)

The algorithm uses binary search on the subarray length combined with a rolling-hash sliding window check.

The outer while loop performs binary search over the range [1, n] of possible subarray lengths, so it runs O(log n) iterations.
For each iteration, _check_uniqueness is invoked, which does the following:
- Recomputes the powers array in O(n) time.
- Computes the initial window hash in O(subarray_len) time, which is at most O(n).
- Slides the window across the array in O(n - subarray_len) iterations, each doing O(1) work (the hash update and dictionary operations are average O(1)).
Therefore each call to _check_uniqueness is O(n).

Combining the O(log n) binary search iterations with the O(n) check yields a total time complexity of O(n log n).

Space Complexity: O(n)

The powers array stores n + 1 precomputed values, contributing O(n).
The hash_values dictionary can hold up to O(n) distinct window hashes in the worst case.
The reference self.nums stores n elements.

Thus the overall auxiliary space complexity is O(n).

Note: This approach relies on the binary search assumption that uniqueness is monotonic with respect to subarray length, and uses a single rolling hash (which is susceptible to hash collisions, potentially affecting correctness rather than complexity).

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Assuming the uniqueness predicate is monotonic and using binary search

The problem description claims that "if a unique subarray exists at some length L, then a unique subarray is also guaranteed to exist at every length greater than L." This sounds reasonable, but it is the single most dangerous trap in this problem, because the claim is false.

The intuition behind the claim is that a longer window "contains" a shorter unique one, so it should inherit uniqueness. But uniqueness is about whether two windows of the same length collide, not about containment. Extending every window by the same amount can actually create new collisions or, more subtly, the monotonicity can break in the other direction.

Concrete counterexample where monotonicity fails:

Consider:

nums = [1, 2, 1, 2, 1]

Length 1: windows are [1], [2], [1], [2], [1]. Counts: 1 appears 3 times, 2 appears 2 times. No unique window.
Length 2: windows are [1,2], [2,1], [1,2], [2,1]. Counts: [1,2] twice, [2,1] twice. No unique window.
Length 3: windows are [1,2,1], [2,1,2], [1,2,1]. Counts: [1,2,1] twice, [2,1,2] once. A unique window exists!

So far the answer is 3. But now look at what monotonicity would require: it should hold for all lengths > 3. Length 4 ([1,2,1,2], [2,1,2,1]) and length 5 ([1,2,1,2,1]) are each automatically unique because there is at most one window — so here it happens to hold.

The real danger is that binary search does not test every length. With n = 5, binary search probes mid = 3 first. If _check_uniqueness(3) returns True, it sets max_len = 2 and then probes mid = 1, then mid = 2 — both False — and returns 3. That happens to be correct here only because the predicate is monotone on this particular input.

Where it genuinely breaks: construct an array where length L is unique but length L+1 is not (this is possible when extending windows merges previously-distinct windows into matching pairs only at some lengths). Binary search may probe a non-unique mid, conclude "search higher," and skip over the smaller valid length entirely — or probe a unique mid and shrink past a smaller answer it never verifies.

Solution: do a simple linear scan from the smallest length upward. This is exactly what the first code block does, and it is correct regardless of monotonicity:

for window_len in range(1, n + 1):
    if self._has_unique_window(nums, window_len, base, modulo, powers):
        return window_len
return n

The time complexity is O(n^2) instead of the claimed O(n log n), but it is correct. The binary-search version trades correctness for a speedup that the problem's structure does not actually permit.

Pitfall 2: Negative values after modular subtraction

When sliding the window, the code subtracts the leftmost element's contribution:

current_hash = (current_hash - leftmost) % modulo

In Python this is safe because % always returns a non-negative result. But if you port this to C++, Java, or Go, the subtraction can produce a negative intermediate value, and % in those languages preserves the sign. The fix is to add modulo before taking the remainder:

current_hash = ((current_hash - leftmost) % modulo + modulo) % modulo;

Forgetting this leads to wrong hash values and false collision/uniqueness results that are very hard to debug.

Pitfall 3: Hash collisions causing false negatives

A rolling polynomial hash maps subarrays into a finite space (modulo = 10**9 + 7). Two different subarrays can hash to the same value (a collision). When that happens:

A genuinely unique subarray's hash count gets inflated past 1, so _check_uniqueness reports False when it should report True.
The reported answer becomes larger than the true minimum.

With a single 32-bit-ish modulus and n windows, the birthday-bound collision probability is non-trivial for large n.

Solution: use a double hash (two independent (base, modulo) pairs) and key the dictionary on the tuple of both hashes:

key = (hash1, hash2)
hash_counts[key] = hash_counts.get(key, 0) + 1

This makes accidental collisions astronomically unlikely. For absolute correctness, store the actual subarray (e.g., a tuple of its elements) as the key instead of a hash — slower, but collision-free.

Pitfall 4: Resetting state between checks

The second implementation stores self.hash_values as instance state and relies on self.hash_values.clear() inside _check_uniqueness. If you refactor _check_uniqueness (e.g., to add early returns or reuse it elsewhere) and forget the clear(), counts from a previous length leak into the current check, corrupting the result.

Solution: make the count dictionary local to each call (as the first implementation does) so there is no cross-call contamination:

hash_counts: Dict[int, int] = {}   # fresh per call

This eliminates an entire class of stateful-bug surprises.

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

Problem: Given a list of tasks and a list of requirements, compute a sequence of tasks that can be performed, such that we complete every task once while satisfying all the requirements.

Which of the following method should we use to solve this problem?

Topological Sort

Uniform Cost Search

Monotonic Stack

Memoization

I don't know