Katkat
Back

Return the longest contiguous subarray with all distinct values

NetflixSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to use the sliding window pattern and a hash map to maintain a range of unique elements efficiently in O(n) time.

Problem Statement

Given an array of integers nums, find the length of the longest contiguous subarray where every element is distinct. Return this maximum length.

Function Signature

def longest_distinct_subarray(nums: list[int]) -> int:

Constraints

  • 0 <= len(nums) <= 10^5
  • -10^9 <= nums[i] <= 10^9

Examples

Example 1: Input: nums = [1, 2, 3, 1, 4, 5] Output: 4 Explanation: The longest subarray with distinct values is [2, 3, 1, 4], which has length 4.

Example 2: Input: nums = [7, 7, 7, 7] Output: 1 Explanation: The longest subarray with distinct values is [7], which has length 1.

Edge Cases

  • Empty array: Should return 0.
  • Array with all identical elements: Should return 1.
  • Array with all unique elements: Should return the length of the array.

Hints

Hint 1

Consider using two pointers, 'left' and 'right', to represent the boundaries of the current window.

Hint 2

Use a hash map (or dictionary) to store the last seen index of each element to quickly skip the 'left' pointer when a duplicate is encountered.

Hint 3

As you move the 'right' pointer, update the window size and ensure that if a duplicate is found within the current range, the 'left' pointer is moved to the position after the previous occurrence of that value.

Follow-up questions

  • How would your approach change if you were asked to return the actual subarray itself instead of just its length?
  • Can you optimize the space complexity if the range of values in `nums` was constrained to a small set of integers (e.g., 0 to 255)?
  • How would you adapt this algorithm to find the longest subarray with at most 'k' distinct elements?