Longest Subarray with Contiguous Elements

By | November 20, 2021
Longest Contiguous Subarray

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[0]);
    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[0]);
    printf("%d", largestSubarray(arr, n));
}

Output

Vamware
3

People are also reading:

Author: Vinay

I am a Full Stack Developer with a Bachelor's Degree in Computer Science, who also loves to write technical articles that can help fellow developers.

Leave a Reply

Your email address will not be published.