0 like 0 dislike
193 views
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" . )
| 193 views

## 1 Answer

1 like 0 dislike
Best answer

#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
by Expert (980 points)
selected