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?

Favourable

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

Wil

What are ans and temp_ans? – Favourable

ans is the size of the subarray and initially it is 2 . tmp_ans is also the size of the subarray but it's temporary and we update ans only if tmp_ans exceeds ans . And we are updating ans in the code ans = max(temp_ans , ans) – Wil

The function does not work correctly. Example: [7,-5,-5,-5,7,-1,7] should return [7,-1,7] or [-5,-5,-5] ==> Then the length of the longest switching array is 3. This function return 2! – Favourable

You need to change ==> else temp_ans = 2 <== to else without any condition – Favourable

actually ans = max(ans , max) is not with any condition I don't know if you are familiar with this type of coding but sure I'll change that . – Wil

Yeah.. I know. I just thought that "else temp_ans = 2" are on the same line. This is why I thought something is wrong. – Favourable

Thanks for mentioning that actually I have just created my ID and it was my first answer . I should have made that more readable but now it is :) . – Wil

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

Almund

Answer 3

I didn't analyse the time complexity, just wrote a solution that uses recursion and it works (I think):

public class Main
{
    public static int switching(int[] arr, int index, int end)
    {
        try
        {
            if (arr[index] == arr[index+2])
            {
                end = index+2;
                return switching(arr, index+1, end);
            }
            
        } catch (Exception e) {}
        
        return end;
    }
    
    public static void main(String[] args)
    {
        //int[] arr = {3,2,3,2,3};
        //int[] arr = {3,2,3};
        //int[] arr = {4,4,4};
        int[] arr = {1,2,3,4,5,4,4,7,9,8,10};
        
        int best = -1;
        
        for (int i = 0; i < arr.length; i++) 
                best = Math.max(best, (switching(arr, i, 0) - i));
        
        System.out.println(best+1); // It returns, in this example, 3
    }

}

Bhagavadgita

Answer 4

int switchingSubarray(vector<int> &arr, int n) {
if(n==1||n==2) return n;
int i=0;
int ans=2;
int j=2;
while(j<n)
{
    if(arr[j]==arr[j-2]) j++;
    else
    {
        ans=max(ans,j-i);
        i=j-1;
        j++;
    }
}
ans=max(ans,j-i);
return ans;
}

Just using sliding window technique to solve this problems as element at j and j-2 need to be same. Try to dry run on paper u will surely get it .

Satanism

Answer 5

# Switching if numbers in even positions equal to odd positions find length of longest switch in continuos sub array
 def check(t):
     even = []
     odd = []
     i = 0
     while i < len(t):
         if i % 2 == 0:
             even.append(t[i])
         else: 
             odd.append(t[i])
         i += 1

     if len(set(even)) == 1 and len(set(odd)) == 1:
         return True
     else:
         return False

 def solution(A):
     maxval = 0
     if len(A) == 1:
         return 1
     for i in range(0, len(A)):
         for j in range(0, len(A)):
             if check(A[i:j+1]) == True:
                 val = len(A[i:j+1])
                 print(A[i:j+1])
                 if val > maxval:
                     maxval = val
     return maxval
 A = [3,2,3,2,3]
 A = [7,4,-2,4,-2,-9]
 A=[4]
 A = [7,-5,-5,-5,7,-1,7]
 print(solution(A))

Heroism

Please add further details to expand on your answer, such as working code or documentation citations. – Drysalter

Answer 6

Here is C++ version of solution.

#include <vector>

int longestSwitchinLength(std::vector<int> A)
{
    int n = A.size();
    if (n < 2)
        return n;
        
        
    int maxSwitchingLength = 2;
    int currentSwitchingLength = 2;
    bool found = false;
    
    for (int i = 2; i < n; ++i) {
        if (A[i] == A[i - 2]) {
            ++currentSwitchingLength;
            found = true;
        }
    
        maxSwitchingLength = std::max(maxSwitchingLength, currentSwitchingLength);
    }
    
    if (found)
        return maxSwitchingLength;
    return 0;

}

Ranjiv