pb.py

"""
Given an int array which might contain duplicates,
find the largest subset of int which form a sequence.
Eg. {1,2,10,4,7,9,5}
then ans is 4,5,6,7
Sorting is an obvious solution. Can this be done in O(n) time
"""


def find_easy(arr):
    """'easy' version with sorting 0(nlogn)"""
    arr = sorted(list(set(arr)))
    best_start, best_end = 0, 1
    start, end = 0, 1
    for i, x in enumerate(arr):
        if i == 0:
            continue
        elif x == arr[i - 1] + 1:
            end += 1
        else:
            if end - start > best_end - best_start:
                best_end, best_start = end, start
            start = i
            end = i + 1
    if end - start > best_end - best_start:
        best_end, best_start = end, start
    return arr[best_start:best_end]


def extract_one(s):
    """
    this function start with a random element in the set
    and just try to iterate to find how large the
    continuity is. It removes the elements found.
    Example:                 V extract this and remove it
        xxxx x x xxxxx xxx  [xxxxx] xxxx xx
    """
    x = s.pop()
    l = [x]
    n = x - 1
    while n in s:
        s.remove(n)
        l.append(n)
        n -= 1
    n = x + 1
    while n in s:
        s.remove(n)
        l.append(n)
        n += 1
    return l


def find(arr):
    """
    O(n) version
    just put every number in a set (O(n), hashtable)
    and then extract the continuous sets of numbers
    """
    s = set(arr)
    biggest = []
    while len(s) > len(biggest):
        found = extract_one(s)
        if len(found) > len(biggest):
            biggest = found
    return biggest


def find_smarter_than_me(arr):
    table = {}
    first = 0
    last = 0
    for i in arr:
        beg = end = i
        if i in table:
            continue
        table[i] = 'EXISTED'
        if i - 1 in table:
            beg = table[i - 1]
        if i + 1 in table:
            end = table[i + 1]
        table[beg] = end
        table[end] = beg
        if end - beg > last - first:
            first = beg
            last = end
    return list(range(first, last + 1))

arr = [1, 6, 10, 4, 7, 9, 5, 5, 8]
print(find_easy(arr))
print(find(arr))
print(find_smarter_than_me(arr))