Longest Subarray with Contiguous Elements

Posted in

Longest Subarray with Contiguous Elements
vinaykhatri

Vinay Khatri
Last updated on April 16, 2024

    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:

    Leave a Comment on this Post

    0 Comments