How to find the largest subarray in an array whose first and last elements differ by "1" efficiently ?

Question

Expected Time Complexity : O(N) , where 'N'  is the size of array .

1<=A[i]<=1000000

1<=N<=100000

Example :

6

1 2 3 2 4 1

Output : 5 ({2,3,2,4,1} is the largest subarray whose first and last elements have difference of "1" . )

Answer 1

#Time Complexity - O(N)

#Language - C#

APPROACH

STEP 1: - Read the inputs and create a variable and assign the value 1 to it as the index should compare from 1. Initialize start and end variables as we need them while checking the longest array.

STEP 2:-  Use a loop but don't increment everytime, increment the loop value only when the j value is at it's highest length.Becoz of this it will make the loop varaible as static and compare with every other in an array.

STEP 3:- Assign loop variable value to start and If the array values are equal to 1, assign the value to end variable. 

STEP 4: - Increase the j value if it is less the array length and assign the j value to +1 of loop varaible when the j value is at it's highest length. So, once the loop varaible increases, j value will be +1 of loop varaible.

STEP 5 :- Find the difference between end and start variables and assign this value to result if it is greater. Print the result value+1 as it checks for (n-1) through loop . 

CODE

using System;

public class Test
{
    public static void Main()
    {
        int[] arr={1,2,10,1,4,7,9,5,4,9,9,6,5,9};
        int start=0,end=0,temp=0,result=0,j=1;
        for(int i=0;i<arr.Length;)
        {
            start=i; 
            if(j<arr.Length)
            {
                if(arr[i]-arr[j]==1)
                  end=j;
              j++;
            }
            
        if(j==arr.Length)
        {
            i++;
            j=i+1;
        }
        
          temp=end-start;    
            if(temp>result)
               result=temp;
            
        }
      Console.WriteLine(result+1);
    }
}

Output - 12

Input 2 :-{1,2,10,1,4,7,9,5,4,9,9,6,5,1}

Output 2 - 13