Question 5

You are given an unsorted array of integers. You need to find the largest sub-array formed by consecutive numbers. The sub-array should only contain unique values. For example

Input: {2, 7, 2, 1, 4, 3, 5, 0}

Output: The largest subarray is from index 2 to 7

The sub-array is {2, 1, 4, 3, 5}

Solution

The approach is to iterate through the array. Then we keep track of the largest sub-array seen so far. We also make sure that the integers in the sub-array is consecutive.

For the sub-array elements to be consecutive, then:

the difference between the largest and smallest element must be equal to the length of the sub-array minus one
we check the the elements are unique track tracking the already visited element in another array.

The Java code is given below:

/*
 * Find the largest consecutive sub-array
 * Written by: Kindson The Genius
 */
public class LargestSubarray {
	
	//helper function to check if sub-array is consecutive
	static boolean isConsecutive(int A[], int i, int j, int min, int max) 
	{
		if(max - min != j - i) {
			return false;
		}
		
		//track the visited elements
		boolean visited[] = new boolean[j - i + 1];
		
		for(int k = i; k <= j; k++) {
			if(visited[A[k] - min]) {
				return false;
			}
		
			visited[A[k] - min] = true;		
		}
		return true;
	}
	
	
	public static void findMaxSubarray(int[] A) {
		int len = 1;
		int start = 0;
		int end = 0;
		
		//Loop through all the elements of the array
		for(int i = 0; i < A.length - 1; i++) {
			int min_val = A[i];
			int max_val = A[i];
			
			//Loop through the current sub-array
			for(int j = i; j < A.length; j++) 
			{
				min_val = Math.min(min_val, A[j]);
				max_val = Math.max(max_val, A[j]);
				
				//check the the elements are consecutive
				if(isConsecutive(A, i, j, min_val, max_val)) {
					if(len < max_val - min_val + 1) {
						len = max_val - min_val + 1;
						start = i;
						end = j;
					}
				}
			}
		}
		
		System.out.println("The largest subarray is from index "
				+ start + " to " + end);
	}
	
	//Test the program
	public static void main(String[] args) {
		int[] A = {2, 7, 2, 1, 4, 3, 5, 0};
		findMaxSubarray(A);
	}

}