import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class LongestConsecutiveSubsequence {

    ////////// UTIL ///////////

    private static void printArray(int[] ary){
        for (int i = 0; i < ary.length; i++) {
            System.out.printf("%4d" , ary[i]);
        }
        System.out.println();
    }


    public static void main(String[] args) {
//        int[] arr1 = {1, 9, 3, 10, 4, 20, 2};
        int[] arr1 = {36, 41, 56, 35, 44, 33, 34, 92, 43, 32, 42};

        // solution 1
//        sortAndFind(arr1);
//        hashBad(arr1);
        hashGood(arr1);
    }

    // O(n)
    // 1. 試想著，最後的結果就是一群排列好的數個陣列
    // 我們就是去挑每個陣列的開頭，並往下跑
    // 因此，我們就只會跑過每個陣列元素恰恰好就一次，強。
    // 2. 我們利用了Set.contains() O(1)的高效率
    private static void hashGood(int[] arr) {

        Set<Integer> set = new HashSet<>();
        // put ary elements to the set
        for (int i = 0; i < arr.length; i++) {
            set.add(arr[i]);
        }

        int longestLengthSoFar = 1;
        for (int i = 0; i < arr.length; i++) {

            if (!(set.contains(arr[i] - 1))){
                // we only process the node that is the first number in a sequence
                System.out.print("start a new round - starting num: " + arr[i]); // for debug purpose

                int lastNoInSequence = arr[i];
                while (set.contains(lastNoInSequence + 1)){ // here, it won't be N*N because we will at maxmum check N times for the whole array if we only get into this while loop for those first numbers in the sequence
                    lastNoInSequence++;
                    System.out.print(" -> " + lastNoInSequence);
                } // end of while

                int lengthEachRun = lastNoInSequence - (arr[i] - 1);
                System.out.print("\r\nend this round - lengthEachRun: " + lengthEachRun + "\r\n"); // for debug purpose
                if (lengthEachRun > longestLengthSoFar) {
                    longestLengthSoFar = lengthEachRun;
                    System.out.println("update the longestLengthSoFar to " + longestLengthSoFar); // for debug purpose
                }
            } // end of outer while

        }

        System.out.println("result: " + longestLengthSoFar);
    }

    // O(N*N)
    private static void hashBad(int[] arr) {

        Set<Integer> set = new HashSet<>();
        // put ary elements to the set
        for (int i = 0; i < arr.length; i++) {
            set.add(arr[i]);
        }

        int longestLengthSoFar = 1;
        for (int i = 0; i < arr.length; i++) {
            System.out.print("start a new round - starting num: " + arr[i]); // for debug purpose

            int lastNoInSequence = arr[i];
            while ((set.contains(lastNoInSequence + 1))){
                lastNoInSequence++;
                System.out.print(" -> " + lastNoInSequence);
            }

            int lengthEachRun = lastNoInSequence - (arr[i] - 1);
            System.out.print("\r\nend this round - lengthEachRun: " + lengthEachRun + "\r\n"); // for debug purpose
            if (lengthEachRun > longestLengthSoFar) {
                longestLengthSoFar = lengthEachRun;
                System.out.println("update the longestLengthSoFar to " + longestLengthSoFar); // for debug purpose
            }
        }

        System.out.println("result: " + longestLengthSoFar);
    }

    // O(N*log(N) + N) = O(N*log(N))
    private static void sortAndFind(int[] arr) {

        Arrays.sort(arr);
        printArray(arr); // for debug purpose

        int longestLengthSoFar = 1;
        int lengthEachRun = 1;
        int prevNo = -1;
        for (int i = 0; i < arr.length; i++) {

            if (lengthEachRun == 1) System.out.print("start a new round - starting num: " + arr[i]); // for debug purpose

            if (arr[i] == prevNo + 1) {
                System.out.print(" -> " + arr[i]);
                lengthEachRun++;
            }else{
                System.out.print("\r\nend this round - lengthEachRun: " + lengthEachRun + "\r\n"); // for debug purpose
                if (lengthEachRun > longestLengthSoFar){
                    longestLengthSoFar = lengthEachRun;
                    System.out.println("update the longestLengthSoFar to " + longestLengthSoFar); // for debug purpose
                }

                // reset
                lengthEachRun = 1;

            }

            prevNo = arr[i];
        }

        System.out.println("result: " + longestLengthSoFar);
    }
}