Longest Subarray Without Repeating II in C++ (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

The algorithm should run in O(n^2) 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 to overlook the need for contiguous subarrays and mistakenly consider non-contiguous subarrays.

Approach

To solve this problem, we can use a sliding window approach with a nested loop to ensure the time complexity remains O(n^2). The idea is to use a set to track the elements in the current window and expand the window until a duplicate is found.

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 would have a time complexity of O(n^3).

Optimized Solution

We can optimize the solution by using a sliding window approach:

Use two pointers to represent the current window.
Use a set to track the elements in the current window.
Expand the window by moving the right pointer and add elements to the set.
If a duplicate is found, move the left pointer to shrink the window until the duplicate is removed.
Keep track of the maximum length of the window during this process.

Algorithm

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

Initialize two pointers, left and right, both set to the start of the array.
Initialize an empty set to keep track of the elements in the current window.
Initialize a variable maxLength to store the maximum length of the subarray found.
Iterate with the right pointer over the array:

If the element at right is not in the set, add it to the set and update maxLength.
If the element at right is in the set, move the left pointer to the right until the duplicate is removed from the set.

Return maxLength as the result.

Code Implementation


#include <iostream>
#include <vector>
#include <unordered_set>

int longestSubarrayWithoutRepeating(std::vector<int>& nums) {
    int n = nums.size();
    int maxLength = 0;
    for (int i = 0; i < n; ++i) {
        std::unordered_set<int> seen;
        for (int j = i; j < n; ++j) {
            // If we find a duplicate, break the inner loop
            if (seen.find(nums[j]) != seen.end()) {
                break;
            }
            // Otherwise, add the element to the set
            seen.insert(nums[j]);
            // Update the maximum length
            maxLength = std::max(maxLength, j - i + 1);
        }
    }
    return maxLength;
}

int main() {
    std::vector<int> nums = {2, 5, 6, 2, 3, 1, 5, 6};
    std::cout << "Length of the longest subarray without repeating integers: " << longestSubarrayWithoutRepeating(nums) << std::endl;
    return 0;
}

Complexity Analysis

The time complexity of the above approach is O(n^2) because of the nested loops. The space complexity is O(n) due to the use of the set to store elements of the current window.

Edge Cases

Consider the following edge cases:

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

Testing

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

nums = [] (Expected output: 0)
nums = [1, 2, 3, 4, 5] (Expected output: 5)
nums = [1, 1, 1, 1] (Expected output: 1)
nums = [2, 5, 6, 2, 3, 1, 5, 6] (Expected 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 data structures like sets or maps to keep track of elements efficiently.
Practice solving 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 problem-solving skills and preparing for coding interviews.

Additional Resources

For further reading and practice, consider the following resources: