Length of the largest subarray with contiguous elements | Set 2
Given an array of integers, find length of the longest subarray which contains numbers that can be arranged in a continuous sequence.
In the previous post, we have discussed a solution that assumes that elements in given array are distinct. Here we discuss a solution that works even if the input array has duplicates.
Examples:
Input: arr[] = {10, 12, 11};
Output: Length of the longest contiguous subarray is 3Input: arr[] = {10, 12, 12, 10, 10, 11, 10};
Output: Length of the longest contiguous subarray is 2
The idea is similar to the previous post. In the previous post, we checked whether the maximum value minus the minimum value is equal to the ending index minus starting index or not. Since duplicate elements are allowed, we also need to check if the subarray contains duplicate elements or not. For example, the array {12, 14, 12} follows the first property, but its numbers are not contiguous elements.
To check duplicate elements in a subarray, we create a hash set for every subarray and if we find an element already in the hash, we don’t consider the current subarray.
Following is the implementation of the above idea.
C++
/* CPP program to find length of the largest subarray which has all contiguous elements */ #include<bits/stdc++.h> using namespace std; // This function prints all distinct elements int findLength( int arr[], int n) { int max_len = 1; // Initialize result // One by one fix the starting points for ( int i=0; i<n-1; i++) { // Create an empty hash set and // add i'th element to it. unordered_set< int > myset; myset.insert(arr[i]); // Initialize max and min in // current subarray int mn = arr[i], mx = arr[i]; // One by one fix ending points for ( int j=i+1; j<n; j++) { // If current element is already // in hash set, then this subarray // cannot contain contiguous elements if (myset.find(arr[j]) != myset.end()) break ; // Else add current element to hash // set and update min, max if required. myset.insert(arr[j]); mn = min(mn, arr[j]); mx = max(mx, arr[j]); // We have already checked for // duplicates, now check for other // property and update max_len // if needed if (mx - mn == j - i) max_len = max(max_len, mx - mn + 1); } } return max_len; // Return result } // Driver method to test above method int main () { int arr[] = {10, 12, 12, 10, 10, 11, 10}; int n = sizeof (arr) / sizeof (arr[0]); cout << "Length of the longest contiguous" << " subarray is " << findLength(arr, n); } // This article is contributed by Chhavi |
Java
/* Java program to find length of the largest subarray which has all contiguous elements */ import java.util.*; class Main { // This function prints all distinct elements static int findLength( int arr[]) { int n = arr.length; int max_len = 1 ; // Initialize result // One by one fix the starting points for ( int i= 0 ; i<n- 1 ; i++) { // Create an empty hash set and add i'th element // to it. HashSet<Integer> set = new HashSet<>(); set.add(arr[i]); // Initialize max and min in current subarray int mn = arr[i], mx = arr[i]; // One by one fix ending points for ( int j=i+ 1 ; j<n; j++) { // If current element is already in hash set, then // this subarray cannot contain contiguous elements if (set.contains(arr[j])) break ; // Else add current element to hash set and update // min, max if required. set.add(arr[j]); mn = Math.min(mn, arr[j]); mx = Math.max(mx, arr[j]); // We have already checked for duplicates, now check // for other property and update max_len if needed if (mx-mn == j-i) max_len = Math.max(max_len, mx-mn+ 1 ); } } return max_len; // Return result } // Driver method to test above method public static void main (String[] args) { int arr[] = { 10 , 12 , 12 , 10 , 10 , 11 , 10 }; System.out.println( "Length of the longest contiguous subarray is " + findLength(arr)); } } |
Python3
# python program to find length of the largest # subarray which has all contiguous elements */ # This function prints all distinct elements def findLenght(arr, n): max_len = 1 for i in range ( 0 ,n - 1 ): # Create an empty hash set and # add i'th element to it myset = set () myset.add(arr[i]) # Initialize max and min in # current subarray mn = arr[i] mx = arr[i] for j in range (i + 1 ,n): # If current element is already # in hash set, then this subarray # cannot contain contiguous elements if arr[j] in myset: break # Else add current element to hash # set and update min, max if required. myset.add(arr[j]) mn = min (mn, arr[j]) mx = max (mx, arr[j]) # We have already checked for # duplicates, now check for other #property and update max_len # if needed if mx - mn = = j - i: max_len = max (max_len, mx - mn + 1 ) return max_len # Return result # Driver code arr = [ 10 , 12 , 12 , 10 , 10 , 11 , 10 ] n = len (arr) print ( "Length of the longest contiguous subarray is" , findLenght(arr,n)) # This code is contributed by Shrikant13 |
C#
/* C# program to find length of the largest subarray which has all contiguous elements */ using System; using System.Collections.Generic; class GFG { // This function prints all distinct // elements static int findLength( int []arr) { int n = arr.Length; int max_len = 1; // Initialize result // One by one fix the starting points for ( int i = 0; i < n-1; i++) { // Create an empty hash set and // add i'th element to it. HashSet< int > set = new HashSet< int >(); set .Add(arr[i]); // Initialize max and min in current // subarray int mn = arr[i], mx = arr[i]; // One by one fix ending points for ( int j = i+1; j < n; j++) { // If current element is already // in hash set, then this subarray // cannot contain contiguous // elements if ( set .Contains(arr[j])) break ; // Else add current element to // hash set and update min, // max if required. set .Add(arr[j]); mn = Math.Min(mn, arr[j]); mx = Math.Max(mx, arr[j]); // We have already checked for // duplicates, now check for // other property and update // max_len if needed if (mx-mn == j-i) max_len = Math.Max(max_len, mx - mn + 1); } } return max_len; // Return result } // Driver function public static void Main() { int []arr = {10, 12, 12, 10, 10, 11, 10}; Console.WriteLine( "Length of the longest" + " contiguous subarray is " + findLength(arr)); } } // This code is contributed by Sam007 |
Javascript
<script> /* javascript program to find length of the largest subarray which has all contiguous elements */ // This function prints all distinct elements function findLength(arr) { var n = arr.length; var max_len = 1; // Initialize result // One by one fix the starting points for (i = 0; i < n - 1; i++) { // Create an empty hash set and add i'th element // to it. var set = new Set(); set.add(arr[i]); // Initialize max and min in current subarray var mn = arr[i], mx = arr[i]; // One by one fix ending points for (j = i + 1; j < n; j++) { // If current element is already in hash set, then // this subarray cannot contain contiguous elements if (set.has(arr[j])) break ; // Else add current element to hash set and update // min, max if required. set.add(arr[j]); mn = Math.min(mn, arr[j]); mx = Math.max(mx, arr[j]); // We have already checked for duplicates, now check // for other property and update max_len if needed if (mx - mn == j - i) max_len = Math.max(max_len, mx - mn + 1); } } return max_len; // Return result } // Driver method to test above method var arr = [ 10, 12, 12, 10, 10, 11, 10 ]; document.write( "Length of the longest contiguous subarray is " + findLength(arr)); // This code contributed by gauravrajput1 </script> |
Length of the longest contiguous subarray is 2
Time complexity of the above solution is O(n2) under the assumption that hash set operations like add() and contains() work in O(1) time.