Length of the Largest Subarray

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

Problem statement

You are given ‘N’ distinct 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: All elements are distinct from the array.

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
3
1 3 2
3
1 4 2
Sample Output 1 :
3
1
Explanation For Sample Input 1 :
For test case 1: 
The whole array consists of continuous elements.
So the length is 3.

For test case 2: 
The largest subarray with continuous sequence will be [1] or [2] or [4].
So the length will be 1.
Sample Input 2 :
2
4 
14 12 11 20
3
10 12 11
Sample Output 2 :
2
3
Hint

Try to check all subarrays

Approaches (1)
Brute Force

The basic idea is to check all the subarrays possible for the array. The subarray having a continuous element is possible when the minimum number and maximum number present in that subarray are equal to the differences between the last index and the first subarray index. 

For example: 

Let the array be: [1, 3, 2]

If we consider the subarray [0, 2] the minimum and maximum values of the subarray will be 1 and 3, respectively. Their difference is equal to 2, which is equal to the difference between the first and last subarray index.

 

Here is the algorithm :
 

  1. Create a variable (say, ‘ANS’) that will store the maximum length of the subarray having continuous elements and initialize it with 1.
  2. Run a loop from 0 to ‘N’ - 1 (say, iterator ‘i’).
    • Create two variables (say, ‘MX’ and ‘MN’) that will store the maximum and minimum values of the subarray and initialize them with ‘ARR[i]’.
    • Run a loop from ‘i’ + 1 to ‘N’ (say, iterator ‘j’)
      • Update the ‘MX’ value by the maximum of ‘MX’ and ‘ARR[j]’.
      • Update ‘MN’ value by the minimum of ‘MN’ and ‘ARR[j]’.
      • Check if ‘MX’ - ‘MN’ is equal to ‘j’ - ‘i’.
        • Update ‘ANS’ by the maximum of ‘ANS’ and ‘MX’ - ‘MN’ + 1.
  3. Finally, return ‘ANS’.
Time Complexity

O(N^2), where ‘N’ is the size of the array.

 

We iterate the array once to iterate the elements and run another nested loop to find the subarrays. Therefore, the overall time complexity will be O(N^2).

Space Complexity

O(1)

 

We don’t use any extra space. Therefore, the overall space complexity will be O(1).

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