Given an array with all distinct elements, find the length of the longest sub-array which has elements(not in any particular order) that could form a contiguous sequence

Algorithm/Insights

The main insight used in this algorithm is that for a given sub-array if the length of the sub-array is equal to one plus difference of values of maximum and minimum element in that sub-array then the elements in that sub-array would be able to form a contiguous sequence. This condition holds true only if the elements of the sub-array are distinct elements.
For example, for sub-array {32,34,36,33,35,37} from array {10,12,11,94,56,32,34,36,33,35,37}, maximum element in this sub-array is 37 and minimum element is 32 making the difference between them as 5. This difference of 5 plus one is equal to the length of this sub-array which is 6.
In the algorithm, we check for the condition (maxElement - minElement + 1 = length of the sub-array) for all possible sub-arrays. If this condition evaluates to true, we update the maximum length of such sub-array if required.

Time complexity for this approach is O(n^2) with O(1) extra space.

Checkout function findRequiredLength(int[] array) for implementation details.

Code Snippet

			
package com.ideserve.questions.nilesh;

import java.util.Arrays;

/**
 * <b>IDeserve <br>
 * <a href="https://www.youtube.com/c/IDeserve">https://www.youtube.com/c/IDeserve</a>
 * Finds the length of the longest sub-array in that array such that the elements present in that sub-array when re-arranged * could form a contiguous sequence.
 * @author Nilesh
 */

public class LongestSubarrayContiguousElements
{
    public int findRequiredLength(int[] array)
    {
        if (array.length == 0)
        {
            return 0;
        }
        
        int maxLength = 1;
        int subArrayStart = 0, subArrayEnd = 0;
        
        // we are interested in looking at sub-arrays with minimum length as 2
        // since length of 1 for longest sub-array with contiguous elements is trivial 
        // and we don't need to check for that  
        for (int i = 0;  i < array.length - 1; i++)
        {
            int maxElement = array[i], minElement = array[i];
            
            for (int j = i+1; j < array.length; j++)
            {
                // update min and max elements
                if (array[j] > maxElement)
                {
                    maxElement = array[j];
                }
                if (array[j] < minElement)
                {
                    minElement = array[j];
                }
                
                // if difference between min and max is equal to length of sub-array 
                // then we have found sub-array with elements which could form contiguous sequence
                if ((maxElement - minElement) == (j - i))
                {
                    // if length of sub-array is greater than maximum length found
                    if ((j - i + 1) > maxLength)
                    {
                        maxLength = j - i + 1;
                        subArrayStart = i; 
                        subArrayEnd = j;
                    }
                }
            }
        }
        
        System.out.println(subArrayStart + "-" + subArrayEnd);
        return maxLength;
    }
    
    
    public static void main(String[] args)
    {
        LongestSubarrayContiguousElements solution = new LongestSubarrayContiguousElements();
        int[] testArray = {10,12,11,94,56,32,34,36,33,35,37};
        
        System.out.println(solution.findRequiredLength(testArray));
        
    }
}
		

Order of the Algorithm

Time Complexity is O(n^2)
Space Complexity is O(1)