Longest Switching Subarray

Easy
0/40
Average time to solve is 15m
19 upvotes
Asked in companies
Deutsche BankAmerican ExpressOla

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
1
6
5 2 3 5 2 5
Sample Output 1:
3
Explanation For Sample Output 1:
The longest switching subarray is {5, 2, 5} having length 3.
Sample Input 2 :
1
8
1 5 6 0 1 0 1 3
Sample Output 2 :
4
Hint

Think of brute force and try to generate all subarrays.

Approaches (2)
Brute force
  1. Initialise an integer variable ‘ANS’ to 0, which will store the final ‘ANS’ i.e length of the longest switching subarray.
  2. 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.
  3. 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.
  4. If the subarray is switching, get its length and update ‘ANS’ to the maximum of ‘ANS’ and length of the subarray.
  5. Finally, return the ‘ANS’.
Time Complexity

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).

Space Complexity

O(1)

 

Constant extra space is required.

Code Solution
(100% EXP penalty)
Longest Switching Subarray
Full screen
Console