Clean Subarray: Find Longest Subarray Containing No Repeated Element
Question Details
Problem
Given an integer array nums, find the length of the longest contiguous subarray that contains no duplicate values.
python
def clean_subarray(nums: list[int]) -> int:
pass
Example:
nums = [2, 1, 3, 1, 4, 3, 5]
**output** -> 4 # subarray [1, 4, 3, 5] or [3, 1, 4, 3] -- wait, [1,4,3,5] is the answer
nums = [1, 1, 1]
**output** -> 1
Approach
Sliding window with a hash set. Expand right; when a duplicate is found, shrink from left until the duplicate is evicted. O(n) time, O(k) space where k is the window size.
Follow-ups
1.
Return the actual subarray, not just its length.
2. What if "clean" means at most k distinct elements instead of zero duplicates?
3. How does your solution behave on a sorted vs. random array -- any optimization possible?
4. Extend to a 2D matrix: find the largest rectangular sub-matrix with no repeated value in any row.
Full Details
Problem
Given an integer array nums, find the length of the longest contiguous subarray that contains no duplicate values.
python
def clean_subarray(nums: list[int]) -> int:
pass
Example:
nums = [2, 1, 3, 1, 4, 3, 5]
**output** -> 4 # subarray [1, 4, 3, 5] or [3, 1, 4, 3] -- wait, [1,4,3,5] is the answer
nums = [1, 1, 1]
**output** -> 1
Approach
Sliding window with a hash set. Expand right; when a duplicate is found, shrink from left until the duplicate is evicted. O(n) time, O(k) space where k is the window size.
Follow-ups
1.
Return the actual subarray, not just its length.
2. What if "clean" means at most k distinct elements instead of zero duplicates?
3. How does your solution behave on a sorted vs. random array -- any optimization possible?
4. Extend to a 2D matrix: find the largest rectangular sub-matrix with no repeated value in any row.
About This Question
This is a reported interview question from a sofi interview during the onsite round.
It covers the following topics: Sliding Window, Arrays, Coding, Hash Table, Onsite, Matrix .