A O(n) java Solution the should not pass


#1

Algorithm

  • Find max and min in the list. O(n)

  • Make Array of booleans (with false) with length max - min

  • Use elements of the initial list as indexes to set the new array to true. O(n)

  • Iterate through the new array and count consecutive “true”. The longest is the answer. 0(n)

The Solution makes use of the fact that there are finite elements between max and min. This Solution can blow the heap size if the gap between min and max is too big for the jvm. Or it could also break the boolean array indexing if the gap is bigger than Integer.MAX_VALUE (for example A = {-1, Integer.MAX_VALUE} will break, because of overflow). BUT! No one of these cases appears in the tests.))

  public int longestConsecutive(final List<Integer> A) {
    if (A.size() < 1) {
        return 0;
    }
    int min = A.stream().min(Integer::compareTo).get();
    int max = A.stream().max(Integer::compareTo).get();
    boolean[] all = new boolean[max - min + 1];
    for (int i : A) {
        all[i - min] = true;
    }
    int maxConseq = 0;
    int currConseq = 0;
    for (int i = 0; i < all.length; i++) {
        if (all[i]) {
            currConseq++;
        } else {
            if (currConseq > maxConseq) {
                maxConseq = currConseq;
            }
            currConseq = 0;
        }
    }
    return Math.max(maxConseq, currConseq);
}

#2

Would this even be O(n)? in the last step you’re iterating over an array of length max - min, not n. Seems like O(max-min + n). Either way you’re right that this site is janky af.