Find largest subarray with distinct elements.
Filed under Microsoft
Free read 3 of 3Confirm whether the output should be the length of the subarray or the subarray itself.
The question
Given an array of integers, find the length of the longest contiguous subarray that contains all unique elements.
Constraints
- 0 <= array.length <= 10^5
- -10^9 <= array[i] <= 10^9
Examples
- Input
- nums = [1, 2, 3, 1, 4, 2, 3, 5]
- Output
- 5
- Why
- The longest substring without repeating characters is [3, 1, 4, 2, 3] or [1, 4, 2, 3, 5], length is 5.
Approach
Confirm whether the output should be the length of the subarray or the subarray itself.
Check every possible subarray using nested loops and verify uniqueness with a set. Time complexity: O(N^3) or O(N^2).
Use a sliding window approach with a hash map to store the last seen index of each element. Maintain a left pointer and expand the right pointer, updating the left pointer if a duplicate falls inside the current window.
Array with 0 or 1 element, or all elements being duplicates.
Solution
O(N) time, O(min(N, K)) space where K is number of unique elements
class Solution:
def lengthOfLongestSubstring(self, s: list) -> int:
seen = {}
l = max_len = 0
for r, val in enumerate(s):
if val in seen and seen[val] >= l:
l = seen[val] + 1
seen[val] = r
max_len = max(max_len, r - l + 1)
return max_len
Tips
- What they are testing: Test with an array of all identical elements, all unique elements, and an empty array.
- Common mistake: Failing to update the left pointer correctly when a duplicate is found, leading to outdated index evaluations.
Related Microsoft questions
Collected from public candidate posts and coding forums. Updated Nov 2026.