Smallest Unique Subarray - Solution & Explanation

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.