# 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

Given an array with all distinct elements, find 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. For example, for the array - {10,12,11,94,56,32,34,36,33,35,37}, if we consider a sub-array starting at index 0 and ending at index 2, the elements in this sub-array could be re-arranged to form a sequence 10,11,12. Similarly, for sub-array starting at index 5 and ending at index 10, if the elements in this sub-array are re-arranged we could obtain a contiguous sequence 32,33,34,35,36,37 which turns out to be longest such sub-array for this input array.

Therefore, for input array {10,12,11,94,56,32,34,36,33,35,37}, output returned should be 6. If the input array is {10,12,14} then output returned should be 1. For input array {10,13,12} output returned should be 2.

## 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>
* 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)