Longest Subarray Without Reapeating in JavaScript

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) time and use O(n) extra space

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

The algorithm should run in O(n) time.
The algorithm should use O(n) extra space.

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 sliding window correctly, which can lead to suboptimal solutions.

Approach

To solve this problem, we can use the sliding window technique combined with a hash map to keep track of the elements and their indices. This approach ensures that we can efficiently find the longest subarray without repeating elements.

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^2) or worse.

Optimized Solution

The optimized solution uses a sliding window and a hash map:

Initialize two pointers, start and end, both set to the beginning of the array.
Use a hash map to store the last seen index of each element.
Expand the window by moving the end pointer and update the hash map.
If a duplicate is found, move the start pointer to the right of the last seen index of the duplicate element.
Keep track of the maximum length of the window.

Algorithm

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

Initialize start and end pointers to 0.
Initialize an empty hash map map to store the last seen index of each element.
Initialize maxLength to 0.
Iterate through the array using the end pointer.
If the element at end is already in the hash map and its index is greater than or equal to start, update start to map[nums[end]] + 1.
Update the hash map with the current index of the element.
Calculate the length of the current window and update maxLength if it is greater than the previous maximum length.
Return maxLength after the loop ends.

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 the start pointer, maxLength, and a map to store the last seen index of elements
    let start = 0;
    let maxLength = 0;
    const map = new Map();

    // Iterate through the array using the end pointer
    for (let end = 0; end < nums.length; end++) {
        // If the element is already in the map and its index is greater than or equal to start
        if (map.has(nums[end]) && map.get(nums[end]) >= start) {
            // Update the start pointer to the right of the last seen index of the duplicate element
            start = map.get(nums[end]) + 1;
        }

        // Update the map with the current index of the element
        map.set(nums[end], end);

        // Calculate the length of the current window and update maxLength if necessary
        maxLength = Math.max(maxLength, end - start + 1);
    }

    // Return the maximum length found
    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 solution is O(n) because we are iterating through the array once with the end pointer and the start pointer only moves forward. The space complexity is O(n) due to the hash map storing the indices of the elements.

Edge Cases

Consider the following edge cases:

Empty array: The output should be 0.
Array with all unique elements: The output should be the length of the array.
Array with all identical elements: The output should be 1.

Testing these edge cases ensures the robustness of the solution.

Testing

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

// Test case 1: Empty array
console.log(longestSubarrayWithoutRepeating([])); // Output: 0

// Test case 2: Array with all unique elements
console.log(longestSubarrayWithoutRepeating([1, 2, 3, 4, 5])); // Output: 5

// Test case 3: Array with all identical elements
console.log(longestSubarrayWithoutRepeating([1, 1, 1, 1])); // Output: 1

// Test case 4: Mixed array
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 time and space complexities.
Use diagrams or pseudo-code to visualize the solution.
Test the solution with various edge cases to ensure its correctness.

Practicing similar problems and studying different algorithms can help 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 and hash map 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:

Longest Subarray Without Repeating IV in O(n) Time and O(n) Space using JavaScript