Last Updated: 12 Nov, 2021

Length of the Largest Subarray

Moderate

Asked in companies

Solve now

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.

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

Solve now

Approaches

01 Approach

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 :

Create a variable (say, ‘ANS’) that will store the maximum length of the subarray having continuous elements and initialize it with 1.
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.
Finally, return ‘ANS’.

Solve now