Problem

Given an array of elements, return the length of the longest subarray where all its elements are distinct.

Examples

Example 1

1
2
3

Input: [5, 1, 3, 5, 2, 3, 4, 1]
Output: 5
Explanation: The longest subarray with unique elements is [5, 2, 3, 4, 1], having length 5.

Solution

Method 1 - Sliding window

The problem requires us to find the longest contiguous subarray with distinct elements. This can be efficiently solved using the sliding window technique, along with a HashSet to maintain the unique elements within the current window. The idea is to expand the window until a duplicate is found and then slide the starting point of the window forward to remove the duplicate.

Here is the approach:

  • Maintain two pointers (start and end) representing the current window.
  • Use a HashSet or similar data structure to keep track of unique elements.
  • Expand the window by moving the end pointer. If a duplicate element is found, move the start pointer until the duplicate is removed.
  • Track the maximum window size during the process.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

public class Solution {
    public int longestUniqueSubarray(int[] arr) {
        int n = arr.length;
        if (n == 0) {
            return 0;
        }
        
        int start = 0;
        int maxLength = 0;
        Set<Integer> uniqueElements = new HashSet<>();
        
        for (int end = 0; end < n; end++) {
            while (uniqueElements.contains(arr[end])) {
                uniqueElements.remove(arr[start]);
                start++;
            }
            uniqueElements.add(arr[end]);
            maxLength = Math.max(maxLength, end - start + 1);
        }
        
        return maxLength;
    }

    // Example usage:
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] arr = {5, 1, 3, 5, 2, 3, 4, 1};
        System.out.println(solution.longestUniqueSubarray(arr));  // Output: 5
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution:
    def longest_unique_subarray(self, arr):
        n = len(arr)
        if n == 0:
            return 0
        
        start = 0
        max_length = 0
        unique_elements = set()
        
        for end in range(n):
            while arr[end] in unique_elements:
                unique_elements.remove(arr[start])
                start += 1
            unique_elements.add(arr[end])
            max_length = max(max_length, end - start + 1)
            
        return max_length

# Example usage:
solution = Solution()
print(solution.longest_unique_subarray([5, 1, 3, 5, 2, 3, 4, 1]))  # Output: 5

Complexity

  • ⏰ Time complexity: O(n) - Each element is processed at most twice (once added and once removed).
  • 🧺 Space complexity: O(min(n, m)) - n is the length of the array, and m is the number of unique elements in the array.