Longest Subarray

Moderate

0/80

Average time to solve is 15m

Contributed by

3 upvotes

Asked in company

Problem statement

You are given an array ‘fruits’ of size ‘N’. Your task is to find the longest sub-array in the given array such that the count of distinct numbers in the sub-array is less than or equal to 2.

The sub-array of an array is a contiguous section. For example, for the given array, {2,3,5,1,4} sub-arrays can be {2,3,5}, {3,5,1,4} and so on.

For Example:

Consider ‘fruits’ = [1, 2, 1, 3, 2], the longest subarray following the given condition is [1, 2, 1]. The length of the sub-array is 3.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line contains an integer 'T' which denotes the number of test cases.

The first line of each test case contains a single integer ‘N’ denoting the size of the array ‘fruits’.

The second line of each test case contains ‘N’ space-separated integers representing the elements of the array ‘fruits’.

Output Format:

For each test case, print a single integer representing the length of the largest sub-array, which can be formed such that the count of distinct numbers in it is less than or equal to 2.

The output of each test case will be printed in a separate line.

Note:

You do not need to input or print anything, as it has already been taken care of. Just implement the given function.

Constraints:

1 < =T <= 10 
1 <= N <= 10 ^ 6
1 <= fruits[i] <= 10 ^ 9 

Time limit: 1 sec

Sample Input 1:

Sample Output 1:

3
2

Explanation of Sample Input 1:

Test case 1:
The longest subarray following the given condition is [1, 2, 1]. The length of the sub-array is 3.

Test case 2:
 The longest subarray following the given condition is [4, 3]. The length of the sub-array is 2.

Sample Input 2:

2
5
4 2 3 1 5
6
1 3 3 2 3 5

Sample Output 2:

2
4

Hint 1

Hint 2

Try to find the count of distinct elements present in each sub-array.

Approaches (2)

Approach 1

Approach 2

Brute Force

We will try every possible combination and check for the count of unique elements. Whenever the unique elements are greater than 2, we will change the sub-array.

Algorithm:

Maintain a variable ‘answer’ and initialize it with a 0 value.
Run a loop from ‘i’ = 0 to N-1
- Run another for loop from ‘j’ = ‘i’ to N-1
  - Count the total number of distinct elements using set. Insert fruits[j] into the set.
  - If the size of the set becomes greater than 2:
    - Break from the current loop
  - Update the answer to max(answer, j-i+1)
Return the final updated answer.

Time Complexity

O(N^2), where ‘N’ denotes the length of the array ‘fruits’.

There are two nested loops running up to ‘N’ that we are using to find our required answer. Hence, the overall time complexity is O(N^2).

Space Complexity

O(1).

Since we have used a set that will store at most 2 elements, therefore space taken is constant. Hence the overall space complexity is O(1).

(100% EXP penalty)

Longest Subarray

Console