Skip to main content
Talentd

Smallest Unique Subarray - Solution & Explanation

HardArrayHash TableBinary SearchRolling Hash5 min read
Practice this problem

Problem Statement

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
The subarray [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
There is at least one subarray of length 2 that is unique, so the smallest unique subarray length is 2.

 

Constraints:

  • 1 <= nums.length <= 105
  • 1 <= 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.

Code

Python

Python

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force EnumerationO(n^3)O(n)Conceptual baseline or very small arrays
Expanding Subarray with SetO(n^2)O(n)Moderate input sizes where simpler logic is preferred
Sliding Window with Frequency MapO(n)O(n)Optimal general solution for large arrays and interview settings

Video Solution

LeetCode 3934 | Smallest Unique Subarray | Binary Search + Rolling Hash | Java | Hindi • Code Kage • 500 views views

Watch 1 more video solutions →

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.

Ready to solve this problem?

Practice Smallest Unique Subarray with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays