# Longest Subarray with Contiguous Elements

Posted in  Vinay Khatri
Last updated on October 3, 2023

## Problem

Given an array of distinct integers, find the length of the longest subarray, which contains numbers that can be arranged in a continuous sequence.

## Approach

The essential thing to remember in this case is that all of the elements are distinct. If all items are distinct, a subarray has contiguous elements if and only if the difference between the maximum and minimum elements in the subarray equals the difference between the subarray's last and first indices. So the goal is to maintain track of the lowest and maximum element values in each subarray. The time complexity of this approach would be O(N2).

### C++ Programming

```#include<bits/stdc++.h>
using namespace std;
int largestSubarray(int a[], int n)
{
int ans = 1;
for (int i=0; i<n-1; i++)
{
int minimum = a[i], maximum = a[i];

// Consider all subarrays starting with i and ending with j
for (int j=i+1; j<n; j++)
{
minimum = min(minimum, a[j]);
maximum = max(maximum, a[j]);

// If current subarray has all contiguous elements
if ((maximum - minimum) == j-i)
ans = max(ans, maximum-minimum+1);
}
}
return ans;
}
int main(){
int arr[] = {1, 2, 3, 3};
int n = sizeof(arr)/sizeof(arr);
cout<<largestSubarray(arr, n);
}```

Output

`3`

### Python Programming

```def largestSubarray(arr, n):

ans = 1
for i in range(n - 1):
minimum = arr[i]
maximum = arr[i]

# Consider all subarrays starting with i and ending with j
for j in range(i + 1, n):
minimum = min(minimum, arr[j])
maximum = max(maximum, arr[j])

if ((maximum - minimum) == j - i):
ans = max(ans, maximum - minimum + 1)

return ans
l = [1, 2, 3, 3]
n = len(l)
print(largestSubarray(l, n))```

Output

`3`

### C Programming

```#include<stdio.h>
int min(int a, int b){
return a>=b?b:a;
}
int max(int a, int b){
return a>=b?a:b;
}
int largestSubarray(int a[], int n)
{
int ans = 1;
for (int i=0; i<n-1; i++)
{
int minimum = a[i], maximum = a[i];

// Consider all subarrays starting with i and ending with j
for (int j=i+1; j<n; j++)
{
minimum = min(minimum, a[j]);
maximum = max(maximum, a[j]);

// If current subarray has all contiguous elements
if ((maximum - minimum) == j-i)
ans = max(ans, maximum-minimum+1);
}
}
return ans;
}
int main(){
int arr[] = {1, 2, 3, 3};
int n = sizeof(arr)/sizeof(arr);
printf("%d", largestSubarray(arr, n));
}
```

Output

`3`