Length of the Largest Subarray II

Moderate
0/80
profile
Contributed by
4 upvotes
Asked in company
Amazon

Problem statement

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.
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 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
Sample Input 1:
2
6 
3 4 5 1 4 5
4 
1 2 3 4
Sample Output 1:
3
4
Explanation:
For the first test case, ARR’ =[3, 4, 5, 1, 4, 5].  In the given array the largest subarray with continuous elements is [3, 4, 5] of size 3, Hence the answer is 3.

For the second test case, ‘ARR’ = [1, 2, 3, 4]. In the given array the largest subarray with continuous elements is [1, 2, 3, 4] of size 4, Hence the answer is 4.
Sample Input 2:
2
7 
1 2 3 4 5 6 7
2
4 2
Sample Output 2:
7
1
Hint

 Try to track duplicate elements while considering any subarray.

Approaches (1)
HashSet

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’
Time Complexity

O(N^2), Where N is the size of the array.

 

We are iterating through every subarray of the array, which will cost O(N^2) time, all the HashSet operations will take O(1) time. Hence the final time complexity is O(N^2).

Space Complexity

O(N), Where N is the size of the array.

 

For each subarray, we are maintaining a set of size N, Hence in the worst case the space complexity is O(N).

Code Solution
(100% EXP penalty)
Length of the Largest Subarray II
Full screen
Console