The longest sub-array with switching elements

Question

An array is called "switching" if the odd and even elements are equal.

Example:

[2,4,2,4] is a switching array because the members in even positions (indexes 0 and 2) and odd positions (indexes 1 and 3) are equal.

If A = [3,7,3,7, 2, 1, 2], the switching sub-arrays are:

== > [3,7,3,7] and [2,1,2]

Therefore, the longest switching sub-array is [3,7,3,7] with length = 4.

As another example if A = [1,5,6,0,1,0], the the only switching sub-array is [0,1,0].

Another example: A= [7,-5,-5,-5,7,-1,7], the switching sub-arrays are [7,-1,7] and [-5,-5,-5].

Question:

Write a function that receives an array and find its longest switching sub-array.

I would like to know how you solve this problem and which strategies you use to solve this with a good time complexity?

Answer 1

I am assuming that the array is zero indexed .

if arr.size <= 2
    return arr.size
else 
   ans = 2
   temp_ans = 2 // We will update ans when temp_ans > ans;
   for i = 2; i < arr.size ; ++i
       if arr[i] = arr[i-2]
            temp_ans = temp_ans + 1;
       else
            temp_ans = 2;
       ans = max(temp_ans , ans);
   return ans;

I think this should work and I don't think it needs any kind of explanation .
Example Code

Answer 2

 private static int solve(int[] arr){
        if(arr.length == 1) return 1;
        int even = arr[0],odd = arr[1];
        int start = 0,max_len = 0;
        for(int i=2;i<arr.length;++i){
            if(i%2 == 0 && arr[i] != even || i%2 == 1 && arr[i] != odd){
                 max_len = Math.max(max_len,i - start);
                 start = i-1;
                 if(i%2 == 0){
                     even = arr[i];
                     odd = arr[i-1];
                 }else{
                     even = arr[i-1];
                     odd = arr[i];
                 }
            }
        }     


        return Math.max(max_len,arr.length - start);
    }

• It's like a sliding window problem.
• We keep track of even and odd equality with 2 variables, even and odd.
• Whenever we come across a unmet condition, like index even but not equal with even variable and same goes for odd, we first
  • Record the length till now in max_len.
  • Reset start to i-1 as this is need incase of all elements equal.
  • Reset even and odd according to current index i to arr[i] and arr[i-1] respectively.

Demo: https://ideone.com/iUQti7