Longest Subarray With No Repetitions

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
4 upvotes
Asked in companies
AmazonFacebookSlice

Problem statement

You are given an array ‘arr’. You are supposed to find the length of the longest subarray which does not contain any repeated numbers.

Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of input contains an integer ‘T’, denoting the number of test cases. The test cases follow.

The first line of each test case contains an integer ‘N’, which denotes the number of elements in the array ‘arr’.

The second line of each test case contains 'N' space-separated integers denoting the elements of the array ‘arr’.
Output Format : 
For each test case, print the longest subarray, which does not contain any repeated number.

Print the output of each test case in a separate line.
Note : 
You are not required to print the expected output, it has already been taken care of. Just implement the function.
Constraints : 
1<= T <= 100
1 <= N <= 10^4
1 <= arr[i] <= 10^9

Time Limit: 1 sec
Sample Input 1 :
2
8
1 2 3 4 5 6 2 3
5
5 4 3 2 1
Sample Output 1 :
6
5
Explanation For Sample Input 1 :
In the first test case, the given array is [1, 2, 3, 4, 5, 6, 2, 3], and the maximum length subarray which doesn’t contain any repetition is [1, 2, 3, 4, 5, 6]. So, the answer is 6.

In the second test case, the given array is [5, 4, 3, 2, 1], and the array does not contain any repetitions. So, we can use the complete array as the answer. So, the answer is 5.
Sample Input 2 :
2
7
1 1 1 1 1 1 1
6
1 2 2 1 1 2
Sample Output 2 :
1
2
Hint

Can you make all the subarrays and count if there is any repetition or not?

Approaches (3)
Brute Force

The idea is to make all the subarrays and then iterate over each subarray and find if there is any repetition or not. The maximum length subarray with no repetition will be the final answer.

 

At first, we will store the right index of the subarray, and then we will store the left index of the subarray. When we have both right and left indices, we will iterate from left to right indices and check if there is any repetition or not?

 

For storing the elements, we will use a hash set that inserts an element in constant extra time.

 

The steps are as follows:

 

  • Initialize an integer answer to 0 that stores the final answer.
  • Iterate from r = 0 to N - 1:
    • Iterate from l = 0 to r:
      • Declare a HashSet allElements, which stores all the elements of the current subarray.
      • Initialize a boolean variable hasRepetitions to false, which is false if there are no reparations and true if there is any repetition.
      • Iterate from i = l to r:
        • If arr[i] is present in the HashSet allElements, it means that the current subarray contains reparations. Update hasRepetitions to true and break the loop.
        • Otherwise, insert arr[i] into the HashSet allElements.
      • If hasRepitations is false, it means that the sub-array doesn’t contain any repetitions. So, update the value of the answer to a maximum of answer and the length of the subarray, i.e., r - l + 1.
  • Return answer as the final answer.
Time Complexity

O(N ^ 3), where N is the number of elements in the array ‘arr’.

 

We are fixing the rightmost index of a subarray, and then we are fixing the leftmost index of the subarray, which takes O(N) time in each case. For each subarray, we are iterating over the elements which take O(N) time, and storing the elements in the HashSet takes O(1) time. Hence, the overall time complexity is O(N ^ 3).

Space Complexity

O(N), where N is the number of elements in the array ‘arr’.

 

As we are using a HashSet for storing the elements of the subarray. In the worst case, the indices of the subarray vary from 0 to N - 1, and the HashSet will store all the elements of the array. Hence, the overall space complexity is O(N).

Code Solution
(100% EXP penalty)
Longest Subarray With No Repetitions
Full screen
Console