Last Updated: 22 Apr, 2021
Longest Subarray With No Repetitions
Moderate
Asked in companies
You are given an array ‘arr’. You are supposed to find the length of the longest subarray which does not contain any repeated numbers.
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
Approaches
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.
- Iterate from l = 0 to r:
- Return answer as the final answer.
The idea is to iterate the left-most index of the subarray from 0 to N - 1 and then iterate the right-most index from the left-most index to N - 1 and insert the elements into the HashSet in real-time. If we get any element that is already present in the HashSet, then we will break the loop as continuing the loop after finding a repetition is redundant.
For storing the elements, we will use a hash set that can insert an element in constant extra time.
The steps are as follows:
- Initialize an integer answer to 0 that stores the final answer.
- Iterate from l = 0 to N - 1:
- Declare a HashSet allElements, which stores all the elements of the current subarray from l to r:
- Iterate from r = l to N - 1:
- If arr[r] is present in the HashSet allElements, it means that the current subarray contains repetitions. So, we will break the loop.
- Otherwise, we will update the value of the answer to a maximum of the answer and the length of the subarray, i.e., r - l + 1.
- Return answer as the final answer.
The idea is to use a hash map to store the indices of all the elements. We will iterate over the array, and if the current element is present in the hashmap, it means the sub-array contains repetitions. So, we will adjust the leftmost index accordingly such that the subarray doesn’t contain any repetition.
Here, the indices that we stored in the hashmap will be used. Whenever we find an element present in the hashmap, it means it is a repetition and we already have indices of the elements in the hashmap. So, we will ignore the last occurrence of the current element and make the subarray from the next element till the current element ie the leftmost index as the index stored in the Hashmap as the value of the current element + 1 and the rightmost index as the index of the current element.
After each step, we will store the answer as the maximum of the current answer and the length of the current subarray.
The steps are as follows:
- Initialize two integers answer and leftMostIndex to 0 that stores the final answer and the left-most index of the current subarray.
- Declare a HashSet allElementsIndices, which stores the elements as a key and their indices as the value.
- Iterate from r = 0 to N - 1:
- If the current element is present in the hashmap allElementsIndices, if we use l as the left-most index of the subarray, then there will be repetitions. So, update the left-most index leftMostIndex a maximum of leftMostIndex and 1 + index of the current element in the hashmap allElementsIndices.
- Store the index of the current element as value and the current element as key in the hashmap allElementsIndices.
- Update the value of the answer to a maximum of answer and the length of the subarray, i.e., r - leftMostIndex + 1.
- Return answer as the final answer.
Similar problems