Longest Subarray Without Reapeating in C++

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 Format:

An array of integers, nums.

Output Format:

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 incorrect results or inefficient solutions.

Approach

To solve this problem efficiently, we can use the sliding window technique combined with a hash map to keep track of the indices of elements. This allows us to dynamically adjust the window size and ensure all elements within the window are unique.

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) and is not feasible for large arrays.

Optimized Solution:

The optimized solution uses a sliding window approach with 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.
Iterate through the array with the end pointer, updating the hash map and adjusting the start pointer as needed to maintain a window of unique elements.
Keep track of the maximum length of the window during the iteration.

Algorithm

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

Initialize start and end pointers to 0.
Initialize a hash map to store the last seen index of each element.
Initialize a variable maxLength to keep track of the maximum length of the subarray.
Iterate through the array with the end pointer.
If the current element is already in the hash map and its index is within the current window, move the start pointer to the right of the last seen index of the current element.
Update the hash map with the current element's index.
Update maxLength with the length of the current window if it is larger than the previous maximum length.

Code Implementation


#include <iostream>
#include <unordered_map>
#include <vector>

using namespace std;

int longestSubarrayWithoutRepeating(vector<int>& nums) {
    unordered_map<int, int> lastSeen;
    int start = 0, maxLength = 0;

    for (int end = 0; end < nums.size(); ++end) {
        if (lastSeen.find(nums[end]) != lastSeen.end()) {
            start = max(start, lastSeen[nums[end]] + 1);
        }
        lastSeen[nums[end]] = end;
        maxLength = max(maxLength, end - start + 1);
    }

    return maxLength;
}

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

Complexity Analysis

The time complexity of the optimized solution is O(n) because each element is processed at most twice (once by the end pointer and once by the start pointer). The space complexity is also O(n) due to the hash map storing the indices of elements.

Edge Cases

Potential edge cases include:

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.

These edge cases can be tested to ensure the algorithm handles them correctly.

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)

Using a testing framework like Google Test can help automate and validate these test cases.

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 diagrams or pseudo-code to visualize the solution.
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 an optimized 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:

Longest Subarray Without Repeating IV in C++ (O(n) Time Complexity)