Longest Subarray with Contiguous Elements

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

3

People are also reading:

• WAP to print the truth table for XY+Z
• WAP to print the 1 to 10 Multiples of a Number
• Find the smallest subarray length whose sum of elements is >= k
• Find Cube of a Number using Functions
• Calculate sum and average of three numbers
• WAP to calculate the sum of two numbers
• Find the greatest number among the three numbers
• Perfect Number in C
• WAP to check whether a given character is an alphabet, digit or any special character