Last Updated: 3 Sep, 2021
Longest Subarray
Moderate
Asked in company
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.
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
Approaches
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)
- Run another for loop from ‘j’ = ‘i’ to N-1
- Return the final updated answer.
We will create a sliding window that will keep track of the distinct elements. Initially, we will increase the size of our window and try to add as many elements as possible. After that, when the total number of distinct elements in the array is more than 2, then we will try to reduce the size of our window. We will keep updating the answer. Finally, we will return the overall maximum answer.
Algorithm:
- To check for the number of distinct elements, we will create a map ‘maps’.
- We will maintain ‘start’, ‘end’ pointers of our sliding window. We will initialize ‘start’ and ‘end’ with 0. This indicates that the size of our current sliding window is 0.
- Now we will increase the size of our window by increasing the end pointer.
- While start < N-1 and end<N-1 :
- Add the current element into our map, maps[fruits[end]]++.
- And increase the size of window, end++.
- Now that we have increased our array to the fullest and we are out of the loop, the size of the map is definitely larger than 2.
- While maps.size()>2:
- Trying to shrink the size of the window by increasing the start pointer.
- We will also remove the element from our map.
- Maps[fruits[start]]--
- start++, decreasing the size of our window.
- end - start is the current size of the window and maximum values of all the windows would be our required answer.
Similar problems