Smallest Unique Subarray solution and explanation
The problem
You are given an integer array nums.
Find the minimum length of a subarray that is not identical to any other subarray in nums.
Return an integer denoting the minimum possible length of such a subarray.
Two subarrays are considered identical if they have the same length and the same elements in corresponding positions.
Example 1:
Input: nums = [3,3,3]
Output: 3
Explanation:
- Subarrays of length 1:
[3]→ appears 3 times - Subarrays of length 2:
[3, 3]→ appears 2 times - Subarrays of length 3:
[3, 3, 3]→ appears once
The subarray [3, 3, 3] is unique, so the smallest unique subarray length is 3.
Example 2:
Input: nums = [2,1,2,3,3]
Output: 1
Explanation:
Subarrays of length 1:
[2]→ appears 2 times[1]→ appears once[3]→ appears 2 times
[1] is unique, so the smallest unique subarray length is 1.Example 3:
Input: nums = [1,1,2,2,1]
Output: 2
Explanation:
Subarrays of length 1:
[1]→ appears 3 times[2]→ appears 2 times
Subarrays of length 2:
[1, 1]→ appears once[1, 2]→ appears once[2, 2]→ appears once[2, 1]→ appears once
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 105
Approach overview
Problem Overview: You are given an array and need the length of the smallest contiguous subarray that contains every distinct element present in the entire array at least once. The challenge is minimizing the window while ensuring all unique values are covered.
Approach 1: Brute Force Enumeration (O(n^3) time, O(n) space)
Start by identifying the set of all distinct elements in the array. Then enumerate every possible subarray using two nested loops. For each candidate subarray, build a temporary set and check whether it contains all unique elements. This approach repeatedly scans overlapping ranges, which leads to cubic time complexity in the worst case. It is mainly useful for verifying correctness on small inputs or building intuition before optimizing.
Approach 2: Expanding Subarray with Set Tracking (O(n^2) time, O(n) space)
Instead of recomputing the set for each subarray, fix the left boundary and expand the right boundary while maintaining a set of elements currently in the window. Once the window contains all distinct values, update the minimum length. Then move the left boundary and repeat the process. This avoids rebuilding sets from scratch but still scans many overlapping ranges, giving quadratic time complexity. It works for moderate input sizes but struggles when n grows large.
Approach 3: Sliding Window with Frequency Map (O(n) time, O(n) space)
The optimal strategy uses a sliding window combined with a frequency map. First compute the number of distinct elements in the entire array. Then maintain two pointers left and right. As you move right, update a hash map counting occurrences inside the window. When the window contains all distinct elements, shrink it from the left while preserving the condition. Each element enters and leaves the window at most once, producing linear time complexity.
The key insight is that once the window satisfies the requirement, any extra occurrences at the left can be removed without losing coverage. This shrinking step ensures the window remains minimal at every stage. The approach relies on fast hash lookups and the classic two pointers pattern.
Recommended for interviews: Interviewers expect the sliding window solution. Starting with brute force shows you understand the requirement, but quickly transitioning to the O(n) window approach demonstrates strong algorithmic thinking. The ability to maintain counts, detect when all unique elements are covered, and shrink the window correctly is the key signal of skill.
Solution
At mid_len = \frac{min_len + max_len}{2}, for each candidate
subarray length mid_len, we slide a rolling hash window along all subarrays
of such a length, recording how many times each hash value shows up.
If any hash value appears exactly once, a unique subarray of length mid_len is found.
We can thereby try to shrink max_len to mid_len - 1.
Otherwise, it means that no unique subarray of that length exists, so we must raise
min_len to mid_len + 1.
This approach works because once a unique subarray exists at length l,
any subarray with length > l is also guaranteed to exist.
Time complexity is O(n log n) and space complexity is O(n), where n is original array length.
We have a total of O(log n) binary searches, each costing O(n) rolling hash time.
class Solution:
def smallestUniqueSubarray(self, nums: list[int]) -> int:
self.nums = nums
self.base = 19
self.modulo = 10**9 + 7
self.powers = [1] * (len(nums) + 1)
self.hash_values: dict[int, int] = dict()
min_possible_len = len(nums) # Base case.
min_len, max_len = 1, len(nums) # For binary search usage.
while min_len <= max_len:
mid_len = (min_len + max_len) // 2
if self._check_uniqueness(mid_len):
if mid_len < min_possible_len:
min_possible_len = mid_len
max_len = mid_len - 1
else:
min_len = mid_len + 1
return min_possible_len
def _check_uniqueness(self, subarray_len: int) -> bool:
# Only need to reset leftmost power to 1 before usage.
self.powers[0] = 1 # Because powers are calculated by bottom-up.
for idx in range(1, len(self.nums) + 1):
self.powers[idx] = (self.powers[idx - 1] * self.base) % self.modulo
current_hash = 0
for idx in range(subarray_len):
current_hash *= self.base
current_hash += self.nums[idx]
current_hash %= self.modulo
self.hash_values.clear() # Clear before usage.
self.hash_values[current_hash] = 1
for idx in range(1, len(self.nums) - subarray_len + 1):
# Window shifts: deduct leftmost num's share from hash value.
current_hash -= self.powers[subarray_len - 1] * self.nums[idx - 1]
# Integrate newly added num's share into hash value.
current_hash *= self.base
current_hash += self.nums[idx + subarray_len - 1]
current_hash %= self.modulo
if current_hash not in self.hash_values.keys():
self.hash_values.update({current_hash: 0})
self.hash_values[current_hash] += 1
return 1 in self.hash_values.values()Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration | O(n^3) | O(n) | Conceptual baseline or very small arrays |
| Expanding Subarray with Set | O(n^2) | O(n) | Moderate input sizes where simpler logic is preferred |
| Sliding Window with Frequency Map | O(n) | O(n) | Optimal general solution for large arrays and interview settings |
Frequently asked questions
Is Smallest Unique Subarray easy or hard?
The problem is typically rated Hard because recognizing the minimal covering window pattern is not always obvious. Once identified, the sliding window technique solves it efficiently in O(n) time with careful frequency tracking.
Smallest Unique Subarray Python/Java solution
Most implementations use a sliding window with a dictionary or HashMap. Increment counts as the right pointer expands the window and decrement counts when the left pointer moves forward. Track when the number of covered distinct elements equals the total distinct count and update the minimum length.
How to solve Smallest Unique Subarray in O(n)?
Compute the number of distinct values in the array, then use two pointers to maintain a sliding window. Expand the right pointer while counting element frequencies in a hash map. When the window contains all unique elements, shrink the left pointer while updating the minimum length. This guarantees linear traversal of the array.
What is the best approach for Smallest Unique Subarray?
The best approach uses a sliding window with a hash map to track element frequencies inside the current window. First compute the number of distinct elements in the entire array. Then expand the right pointer and shrink the left pointer while maintaining coverage of all distinct elements. This produces an O(n) time and O(n) space solution.
Is Smallest Unique Subarray asked at Google/Amazon/Meta?
Variants of this problem appear frequently in interviews at companies like Google, Amazon, and Meta because it tests sliding window reasoning and hash map usage. Similar questions include minimum window substring and smallest covering subarray problems.
What data structure is used in Smallest Unique Subarray?
The core data structure is a hash map (or dictionary) that stores the frequency of each element in the current window. A set is also used initially to determine how many distinct elements exist in the array. Two pointers control the sliding window boundaries.
What is the time complexity of Smallest Unique Subarray?
The optimal solution runs in O(n) time using the sliding window technique. Each element is processed at most twice: once when the right pointer expands the window and once when the left pointer shrinks it. The hash map operations are O(1) on average, giving linear overall complexity.


