Learn-dsa..in 30 days!



























CC-17 : Find the longest contiguous integers subarray.

Description:

Contiguous integers are integers in their natural ascending order. Example: 3,4,5,6. Given unsorted input int array arr, find the longest contiguous subarray that can be formed by elements of arr.

Test cases and expected outputs:

Input Parameters Expected outputs
intArray = {1,9,2,18,3,16,4,5}; The longest contiguous subarray of elements has count : 5 The start element of above contiguous subarray is: 1 The end element of above contiguous subarray is: 5
intArray = {19,11,12,14,22}; The longest contiguous subarray of elements has count : 2 The start element of above contiguous subarray is: 11 The end element of above contiguous subarray is: 12
intArray = {23,24,1,2,3}; The longest contiguous subarray of elements has count : 3 The start element of above contiguous subarray is: 1 The end element of above contiguous subarray is: 3
intArray = {1,2,3,4, 22, 23, 24}; The longest contiguous subarray of elements has count : 4 The start element of above contiguous subarray is: 1 The end element of above contiguous subarray is: 4
intArray5 = {0,0,0,0}; There is *no* contiguous subarray of elements of length greater than 1 !

Pseudocode:

The java method should accept following input parameters: arr (int array).
Initialize a variable hSet of type HashSet to hold the input elements.
Initialize variables longArr, startLongArr, endLongArr to 0. We will use these variables to track the longest contiguous subarray.
Initialize variables currArr, startCurrArr, endCurrArr to 0. We will use these variables to track the current contiguous subarray that has been found while traversing arr. This current contiguous array may or may not be the longest contiguous array in arr.
Using a for loop iterate through arr, using idx as a loop variable with initial value 0 and increment idx till it reaches arr1.length-1:
Add arr1[idx] to hSet.
Using a for loop iterate through arr, using idx as a loop variable with initial value 0 and increment idx till it reaches arr1.length-1:
If hSet contains arr[idx]-1, then arr[idx] cannot be the start of a contiguous sequence, so abort current iteration.o Else we may have found the start of a new contiguous sequence:
Set startCurrArr to arr[idx].
Set endCurrArr to arr[idx].
Set currArr to 1. currArr is used to track the length of the current contiguous sequence that we have found.
Iterate using a while loop while hSet contains arr[idx]+currArr:
If we are in this while loop’s iteration, it means we have found a next contiguous integer in current sequence.
Set endCurrArr to arr[idx]+currArr.
Increment currArr by 1.
When above while loop completes, check if current sequence’s length is greater than the longest sequence we have found so far. If longArr > currArr:
Set longArr=currArr.
Set startLongArr=startCurrArr.
Set endLongArr=endCurrArr.
After the for loop completes longArr, startLongArr and endCurrArr contain the details of the longest contiguous subarray found in arr.
If longArr > 1, this means we have found a contiguous subarray of size greater than 1:
Initialize int array retArr of size 3. Set retArr[0]= longArr. Set retArr[1]=startLongArr. Set retArr[2]=endLongarr. Return retArr.
If longArr equal to 0 or 1, this means we have not found any contiguous subarray of size greater than 1:
In this case return null from the program.

Code:

public int[] arrayFindLongestContiguousSubarray(int[] arr) throws Exception{
	int longArr=0, currArr=0;
	int startLongArr=0, startCurrArr=0;
	int endLongArr=0, endCurrArr=0;
	HashSet<Integer> hSet=new HashSet<Integer>();
	for (int idx=0; idx < arr.length; idx++) {
		hSet.add(arr[idx]);
	}
	for (int idx=0; idx < arr.length; idx++) {
		if (hSet.contains(arr[idx]-1)) {
			//this number cannot be start of sequence as it has a predecesor
			continue;
		}
		startCurrArr=arr[idx];
		endCurrArr=arr[idx];
		currArr=1;
		while ((hSet.contains(arr[idx]+currArr))) {
			endCurrArr=arr[idx]+currArr;
			currArr++;
		}
		if (longArr < currArr) {
			longArr=currArr;
			startLongArr=startCurrArr;
			endLongArr=endCurrArr;
		}
			
	}
	int[] retArr=new int[3];
	if (longArr>1) {
		retArr[0]=longArr;
		retArr[1]=startLongArr;
		retArr[2]=endLongArr;
		return retArr;			
	} else {
		return null;
	}
}

Click here to download and run code and test cases !


Next Page >


About UsPrivacy PolicyContact us