Length of the largest subarray with contiguous elements

The problem “Length of the largest subarray with contiguous elements” states that you are given an integer array. The problem statement asks to find out the length of the longest contiguous sub-array of which elements can be arranged in a sequence (continuous, either ascending or descending). The numbers in the array can occur multiple times.

Example

arr[] = {10, 12, 13, 11, 8, 10, 11, 10}

4

Explanation

The number starting from 0th index to 3rd index contains numbers 10, 12, 13, 11 which can be arranged in a manner 10, 11, 12, 13 of which length becomes 4.

arr[] = {1, 1, 3, 2, 8, 4, 8, 10}

3

Explanation

The number starting from 1st index to 3rd index contains numbers 1, 3, 2 which can be arranged in a manner 1, 2, 3 of which length becomes 3.

Algorithm

1. Set maxLength to 1.
2. Open a loop, i=0, while i < l -1,
   1. Declare a Set and add arr[i] into the Set.
   2. Set the value of maxlen and minlen to arr[i].
   3. Open a loop, starting from j=i+1, while j < l,
      1. Check if Set has the value of arr[j],
         1. If true, break.
         2. Else,
            1. Add the arr[j] into Set.
            2. Find out the minimum between minlen and arr[j] and store it to minlen.
            3. Find out the maximum between maxlen and arr[j] and store it to maxlen.
            4. Check if maxlen-min = = j – i
               1. If true then find out the maximum between maxLength and max-minlen +1 and store it to maxLength.
3. Return maxLength.

Explanation

We are given a question that asks to find out the length of the longest contiguous sub-array which has some numbers that can be arranged in a sequence. There can be a case that the given array has duplicate numbers. We need to handle that case as well. To get the solution, we will be using a Set and a nested loop that will take care of duplicate elements.

Let us consider an example:

Example

Arr[]={10, 12, 13, 11, 8, 10}

We will use a Set after opening a loop and add the number, one at a time, and set the value of maxlen and minlen to arr[i]. Then open a nested loop starting from one element ahead of the current element, because we already inserted the current element into Set. Check if Set contains the value of arr[j], if element found, then break. Else insert the value of arr[j] into Set and find out the maximum between maxlen and arr[j], and also minimum between minlen and arr[j] and store it to maxlen and minlen respectively. Check if maxlen-min is equal to j-i, then update the value of maxLength.

maxLength=1.

i=0, mySet = {10}, minlen = 10, maxlen = 10

j=i+1 = 1, if mySet will have 12, is false,

So insert 12 into mySet and find the maximum of 12 and 10  and minimum of and store 12 into maxlen and 10 into minlen and check if maxlen-minlen is equal to j – i, but it is false.

j=2, if mySet will have 13, is false,

So insert 13 into mySet and find the maximum of 13 and 12 and store 13 into maxlen and 10 into minlen and check if maxlen-minlen is equal to j – i is false.

j=3, if mySet will have 11, is false,

So insert 11 into mySet and find the maximum of 11 and 10 and store 13 into maxlen and 10 into minlen and check if maxlen-minlen is equal to j – i is true now because 13-10 is equal to 3-0. So update the maxLength by finding out the maximum of maxLength and maxlen-minlen+1 max(1, 13-10+1) and it is found out to be 4 and 4 is stored into the maxLength and it will keep traversing the array and set until it finds the longer length than this of contiguous sub-array.

Output: 4

Code

C++ code to find length of the largest subarray with contiguous elements

#include<set>
#include<iostream>

using namespace std;

int getLongestLength(int arr[], int l)
{
    int maxLength = 1;
    for (int i=0; i<l-1; i++)
    {
        set<int> mySet;
        mySet.insert(arr[i]);
        int minlen = arr[i], maxlen = arr[i];

        for (int j=i+1; j<l; j++)
        {
            if (mySet.find(arr[j]) != mySet.end())
                break;

            mySet.insert(arr[j]);
            minlen = min(minlen, arr[j]);
            maxlen = max(maxlen, arr[j]);

            if (maxlen - minlen == j - i)
                maxLength = max(maxLength, maxlen - minlen + 1);
        }
    }
    return maxLength;
}
int main ()
{
    int arr[] = {10, 12, 13, 11, 8, 10};
    int l = sizeof(arr) / sizeof(arr[0]);
    cout << "Length of the Longest contiguous Sub-Array is: " << getLongestLength(arr, l);
    return 0;
}

Length of the Longest contiguous Sub-Array is: 4

Java code to find length of the largest subarray with contiguous elements

import java.util.HashSet;

class largestSubArrayContiguousElements
{
    public static int getLongestLength(int arr[])
    {
        int l = arr.length;
        int maxLength = 1;

        for (int i=0; i< l-1; i++)
        {
            HashSet<Integer> mySet = new HashSet<>();
            mySet.add(arr[i]);

            int min = arr[i];

            int max = arr[i];

            for (int j=i+1; j<l; j++)
            {
                if (mySet.contains(arr[j]))
                    break;

                mySet.add(arr[j]);
                min = Math.min(min, arr[j]);
                max = Math.max(max, arr[j]);

                if (max-min == j-i)
                    maxLength = Math.max(maxLength, max-min+1);
            }
        }
        return maxLength;
    }
    public static void main (String[] args)
    {
        int arr[] = {10, 12, 13, 11, 8, 10};
        System.out.println("Length of the Longest contiguous SubArray is: "+getLongestLength(arr));
    }
}

Length of the Longest contiguous SubArray is: 4

Complexity Analysis

Time Complexity

O(n²) where “n” is the number of elements in the array.

Space Complexity

O(n) where “n” is the number of elements in the array.