Longest Switching Subarray
You are given an array 'ARR' of 'N' positive integers. You need to find the length of the longest switching contiguous subarray.

An array is called Switching if all the elements at even indices are equal and all the elements at odd indices are also equal.

For Example :

If the given 'ARR' is [1, 4, 1, 4, 3, 2, 3, 0]. Then {1, 4, 1, 4}, {3, 2, 3}, {3, 0}, {0} are some of the switching subarrays. But {1, 4, 3}, {1, 4, 1, 4, 3, 2, 3} are not.

Input format :

The first line of input contains a single integer T, representing the number of test cases or queries to be run. Then the T test cases follow: The first line of each test case contains a positive integer 'N', where 'N' is the size of the given array. The next line contains 'N' single space-separated positive integers representing the elements of the array.

Output Format :

For each test case, print an integer denoting the length of the longest switching subarray of the given array in a single line. Output for each test case will be printed in a separate line.

Note:

You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraint :

1

Question

Longest Switching Subarray

You are given an array 'ARR' of 'N' positive integers. You need to find the length of the longest switching contiguous subarray.

An array is called Switching if all the elements at even indices are equal and all the elements at odd indices are also equal.

For Example :

If the given 'ARR' is [1, 4, 1, 4, 3, 2, 3, 0]. Then {1, 4, 1, 4}, {3, 2, 3}, {3, 0}, {0} are some of the switching subarrays. But {1, 4, 3}, {1, 4, 1, 4, 3, 2, 3} are not.

Input format :

The first line of input contains a single integer T, representing the number of test cases or queries to be run. 
Then the T test cases follow:

The first line of each test case contains a positive integer 'N', where 'N' is the size of the given array.

The next line contains 'N' single space-separated positive integers representing the elements of the array.

Output Format :

For each test case, print an integer denoting the length of the longest switching subarray of the given array in a single line.

Output for each test case will be printed in a separate line.

Note:

You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraint :

1 <= T <= 10
1 <= N <= 10^5
1 <= ARR[i] <= 10^8

Time Limit: 1 sec

Accepted Answer

Brute force

Initialise an integer variable ‘ANS’ to 0, which will store the final ‘ANS’ i.e length of the longest switching subarray.
Generate the subarray of the given array by running two nested loops, the outer loop picks starting element('START') and inner loop considers all elements on the right of the picked('START') element as the ending element('END') of the subarray.
For every ‘SUBARRAY’['START', ‘END’], check whether it is switching subarray or not.
- Run a loop from ‘START’ + 2 to ‘END’.
- If the element at ‘ARR’[i] is equal to the element at ‘ARR’[i-2] then continue, otherwise, return false.
- If the whole subarray got traversed then it satisfies the switching subarray condition, so return true.
If the subarray is switching, get its length and update ‘ANS’ to the maximum of ‘ANS’ and length of the subarray.
Finally, return the ‘ANS’.

Space Complexity: O(1)Explanation:

O(1)

Constant extra space is required.

Time Complexity: O(n^3)Explanation:

O(N ^ 3), where N is the length of the array.

In the worst case, we will be generating all the subarrays, to do so we are fixing every index as starting index O(N), and then for each starting index we are fixing an ending index, thus, generating subarray takes O(N^2) time. For each subarray, we need to check whether it is switching or not, in the worst case we have to traverse the whole subarray that can take O(N) time.

Thus, overall time complexity would be O(N^3).

Accepted Answer

Sliding Window Approach

If the length of the array is less than or equal to 2 then it is itself a switching array then returns the length of the array.
Initialize two integers variable ‘EVEN’ and ‘ODD’ to ‘ARR’[0] and ‘ARR’[1] respectively.
Also, initialise two integers variable ‘START’ and ‘MAX_LENGTH’ to 0, where the ‘START’ will store the starting index of the subarray and ‘MAX_LENGTH’ will store the length of the switching subarray.
Run a loop from 2 to ‘N’,
- If the index is odd and the current element is equal to the odd element then continue, otherwise, update the ‘MAX_LENGTH’ to the maximum of ‘MAX_LENGTH’ and current index - ‘START’
- Update the ‘START’ to current index -1.
- Update ‘EVEN’ to ‘ARR’[i-1] and ODD to ‘ARR’[i]
- If the index is even and the current element is equal to the ‘EVEN’ element then continue, otherwise, update the maxLength to the maximum of 'MAX_LENGTH' and current index - ‘START’
- Update the ‘START’ to current index -1.
- Update ‘EVEN’ to ‘ARR’[i] and ‘ODD’ to ‘ARR’[i-1]
After the whole array got traversed then update 'MAX_LENGTH' to the maximum of 'MAX_LENGTH' and ‘N’ - ‘START’.
Return 'MAX_LENGTH'.

Space Complexity: O(1)Explanation:

O(1)

Constant extra space is required

Time Complexity: O(n)Explanation:

O(N), where ‘N’ is the length of the array.

In the worst case, we are traversing the array only once. Hence the over complexity isO(N).