Find largest sub array formed by consecutive integers
import java.util.*;
import java.math.*;
public class FindLargestConsecutiveSubArray {
public static void main(String args[]) {
FindLargestConsecutiveSubArray consecutive = new FindLargestConsecutiveSubArray();
int[][] input = {
null,
{},
{0},
{1,0},
{1,-1},
{0,1},
{2,0,2,1,4,3,1,0},
{1,2,3,-4}
};
for(int i=0; i< input.length; i++) {
System.out.println("Input: " + Arrays.toString(input[i]) + ", Result: " + consecutive.find(input[i]));
}
}
public List<Integer> find(int[] input) {
if(input == null || input.length <= 0) {
return null;
}
List<Integer> result = new ArrayList<>();
for(int i=0; i< input.length; i++) {
int min = input[i];
int max = input[i];
for(int j=i; j< input.length; j++) {
min = Math.min(min, input[j]);
max = Math.max(max, input[j]);
if(isConsecutive(input, min, max, i, j) && (j-i) >= result.size()) {
result = extract(input, i, j);
}
}
}
return result;
}
private boolean isConsecutive(int[] input, int min, int max, int start, int end) {
if(max - min != end - start ) {
return false;
}
int size = end-start;
boolean[] visited = new boolean[size+1];
for(int i=start; i<= end; i++) {
int visitedValue = input[i] - min;
if(visited[visitedValue]) {
return false;
}
visited[visitedValue] = true;
}
return true;
}
private List<Integer> extract(int[] input, int start, int end) {
List<Integer> result = new ArrayList<>();
for(int i=start; i<= end; i++ ){
result.add(input[i]);
}
return result;
}
}