Longest Subarray Without Repeating II in Java (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 and 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 analysis, 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 with a nested loop to check for the longest subarray without repeating elements. This approach ensures that we check all possible subarrays and keep track of the maximum length 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 has a time complexity of O(n^3).

Optimized Solution

We can optimize the solution by using a sliding window approach with a set to keep track of unique elements. This approach reduces the time complexity to O(n^2) as required.

Algorithm

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

Initialize a variable maxLength to store the maximum length of the subarray found.
Use a nested loop to iterate through the array. The outer loop represents the starting point of the subarray, and the inner loop represents the ending point.
Use a set to keep track of unique elements in the current subarray.
For each subarray, check if the element is already in the set. If it is, break the inner loop. If not, add the element to the set and update the maximum length if the current subarray length is greater.
Return the maximum length found.

Code Implementation

import java.util.HashSet;
import java.util.Set;

public class LongestSubarrayWithoutRepeating {
    public static int lengthOfLongestSubarray(int[] nums) {
        int maxLength = 0;

        // Outer loop to set the starting point of the subarray
        for (int i = 0; i < nums.length; i++) {
            Set<Integer> uniqueElements = new HashSet<>();

            // Inner loop to set the ending point of the subarray
            for (int j = i; j < nums.length; j++) {
                // If the element is already in the set, break the loop
                if (uniqueElements.contains(nums[j])) {
                    break;
                }
                // Add the element to the set
                uniqueElements.add(nums[j]);
                // Update the maximum length
                maxLength = Math.max(maxLength, j - i + 1);
            }
        }

        return maxLength;
    }

    public static void main(String[] args) {
        int[] nums = {2, 5, 6, 2, 3, 1, 5, 6};
        System.out.println("Length of the longest subarray without repeating integers: " + lengthOfLongestSubarray(nums));
    }
}

Complexity Analysis

The time complexity of this approach is O(n^2) because of the nested loops. The space complexity is O(n) due to the set used to store unique 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

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

nums = [] (Empty array)
nums = [1, 2, 3, 4, 5] (All unique elements)
nums = [1, 1, 1, 1] (All identical elements)
nums = [2, 5, 6, 2, 3, 1, 5, 6] (Mixed elements)

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 unique elements.
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 with a set. 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: