Algocademy Logo

Longest Subarray Without Repeating II in JavaScript (O(n^2) Time Complexity)


Given an input array of integers, find the length of the longest subarray without repeating integers.

Example

Input: nums = [2, 5, 6, 2, 3, 1, 5, 6]
Output: 5
Explanation: [5, 6, 2, 3, 1] or [6, 2, 3, 1, 5] are both valid and of maximum length 5

Note:

For this lesson, your algorithm should run in O(n^2) time and use O(n) extra space.
(There exist faster solutions which we will discuss in future lessons)


Problem Definition

The problem requires finding the length of the longest subarray in a given array of integers where no integer repeats. The input is an array of integers, and the output is a single integer representing the length of the longest subarray without repeating integers.

Input

  • An array of integers, nums.

Output

  • An integer representing the length of the longest subarray without repeating integers.

Constraints and Assumptions

  • The array can contain both positive and negative integers.
  • The array can be of any length.

Example

Input: nums = [2, 5, 6, 2, 3, 1, 5, 6]
Output: 5
Explanation: [5, 6, 2, 3, 1] or [6, 2, 3, 1, 5] are both valid and of maximum length 5

Understanding the Problem

The core challenge is to identify the longest contiguous subarray where all elements are unique. This problem is significant in various applications such as data stream processing, substring problems in strings, and more. A common pitfall is not handling the repeated elements correctly, which can lead to incorrect subarray lengths.

Approach

To solve this problem, we can use a sliding window approach. The idea is to use two pointers to represent the current window of unique elements and a set to track the elements within the window.

Naive Solution

A naive solution would involve checking all possible subarrays and verifying if they contain unique elements. This approach is not optimal as it has a time complexity of O(n^3).

Optimized Solution

We can optimize the solution using a sliding window technique:

  • Initialize two pointers, start and end, both set to the beginning of the array.
  • Use a set to keep track of unique elements in the current window.
  • Expand the window by moving the end pointer and add elements to the set.
  • If a duplicate is found, move the start pointer to the right until the duplicate is removed from the set.
  • Keep track of the maximum length of the window during this process.

Algorithm

Here is a step-by-step breakdown of the sliding window algorithm:

  1. Initialize start and end to 0, and an empty set uniqueElements.
  2. Iterate with end from 0 to the end of the array.
  3. For each element, check if it is in uniqueElements:
    • If it is, move start to the right until the duplicate is removed.
    • If it is not, add the element to uniqueElements and update the maximum length.
  4. Return the maximum length found.

Code Implementation

/**
 * Function to find the length of the longest subarray without repeating integers.
 * @param {number[]} nums - The input array of integers.
 * @return {number} - The length of the longest subarray without repeating integers.
 */
function longestSubarrayWithoutRepeating(nums) {
    // Initialize pointers and a set to track unique elements
    let start = 0;
    let maxLength = 0;
    let uniqueElements = new Set();

    // Iterate through the array with the end pointer
    for (let end = 0; end < nums.length; end++) {
        // If the element is already in the set, move the start pointer
        while (uniqueElements.has(nums[end])) {
            uniqueElements.delete(nums[start]);
            start++;
        }
        // Add the current element to the set
        uniqueElements.add(nums[end]);
        // Update the maximum length
        maxLength = Math.max(maxLength, end - start + 1);
    }

    return maxLength;
}

// Example usage:
const nums = [2, 5, 6, 2, 3, 1, 5, 6];
console.log(longestSubarrayWithoutRepeating(nums)); // Output: 5

Complexity Analysis

The time complexity of this approach is O(n^2) because in the worst case, each element might be added and removed from the set multiple times. The space complexity is O(n) due to the set storing unique elements.

Edge Cases

Consider the following edge cases:

  • An empty array should return 0.
  • An array with all unique elements should return the length of the array.
  • An array with all identical elements should return 1.

Testing

To test the solution comprehensively, consider the following test cases:

console.log(longestSubarrayWithoutRepeating([])); // Output: 0
console.log(longestSubarrayWithoutRepeating([1, 2, 3, 4, 5])); // Output: 5
console.log(longestSubarrayWithoutRepeating([1, 1, 1, 1])); // Output: 1
console.log(longestSubarrayWithoutRepeating([2, 5, 6, 2, 3, 1, 5, 6])); // Output: 5

Thinking and Problem-Solving Tips

When approaching such problems, consider the following tips:

  • Understand the problem requirements and constraints thoroughly.
  • Think about different approaches and their trade-offs.
  • Use data structures like sets or maps to keep track of elements efficiently.
  • Practice similar problems to improve problem-solving skills.

Conclusion

In this blog post, we discussed how to find the length of the longest subarray without repeating integers using a sliding window approach. We covered the problem definition, approach, algorithm, code implementation, complexity analysis, edge cases, and testing. Understanding and solving such problems is crucial for improving algorithmic thinking and coding skills.

Additional Resources

For further reading and practice, consider the following resources: