vamsu
7/23/2018 - 2:24 PM

Find largest sub array formed by consecutive integers

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;
    }
}