Last Updated: 21 Nov, 2021
Length of the Largest Subarray II
Moderate
Asked in company
You are given ‘N’ integers in the form of an array ‘ARR’. You need to print the length of the longest subarray in which the numbers are present in a continuous sequence.
Note:
This problem is similar to the problem "Length of the Largest Subarray". The only difference is that there can be duplicate elements in this problem.
For example:
Let ‘ARR’ be: [1, 2, 4]
Then the largest subarray with continuous sequence will be: [1, 2]
So the length will be 2.
Input Format :
The first line of input contains an integer ‘T’, denoting the number of test cases.
The first line of each test case contains a single integer ‘N’, representing the size of the array.
The second line of each test case contains ‘N’ space-separated integers, representing the elements of the array ‘ARR’.
Output Format :
For each test case, print the length of the longest subarray having a continuous sequence.
Print output of each test case in a separate line.
Note :
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 10
1 <= N <= 5*10^3
1 <= ARR[i] <= 10^9
Time Limit: 1 sec
Approaches
In this approach, we will find the maximum and minimum element of each subset in the array and if the difference between maximum and minimum elements is equal to the difference in indices then it’s a valid set.
This method will work if all the elements are distinct, but to account for duplicates we will have to keep a HashSet and if an element occurs twice in the subarray, we won’t count that subarray.
Algorithm:
- Set ‘ans’ as 1
- Iterate i from 0 to size of the array - 2
- Initialise an empty set numSet.
- Insert arr[i] into numSet
- Set maxElement and minElement as arr[i]
- Iterate j from i + 1 to size of the array - 1
- If arr[j] is in numSet, break the loop
- Insert arr[j] in numSet
- If maxElement - minElement is equal to j - i
- Set ‘ans’ as the maximum of ‘ans’ and j - i + 1
- Return the ‘ans’