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

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.

 

Code->

#include<iostream>
using namespace std;

// Utility functions to find minimum and maximum of
// two elements
int min(int x, int y) { return (x < y)? x : y; }
int max(int x, int y) { return (x > y)? x : y; }

// Returns length of the longest contiguous subarray
int findLength(int arr[], int n)
{
int max_len = 1; // Initialize result
for (int i=0; i<n-1; i++)
{
// Initialize min and max for all subarrays starting with i
int mn = arr[i], mx = arr[i];

// Consider all subarrays starting with i and ending with j
for (int j=i+1; j<n; j++)
{
// Update min and max in this subarray if needed
mn = min(mn, arr[j]);
mx = max(mx, arr[j]);

// If current subarray has all contiguous elements
if ((mx - mn) == j-i)
max_len = max(max_len, mx-mn+1);
}
}
return max_len; // Return result
}

// Driver program to test above function
int main()
{
int arr[] = {1, 56, 58, 57, 90, 92, 94, 93, 91, 45};
int n = sizeof(arr)/sizeof(arr[0]);
cout << "Length of the longest contiguous subarray is "
<< findLength(arr, n);
return 0;
}

 

Leave a Reply

Your email address will not be published. Required fields are marked *

For Inserting code :
Paste your code in the comment form, select it and then click the language link

C | C++ | Java |

*