disk-space.py

import bisect
from collections import deque


def comp_space(x, space):
    sub = space[:x]
    rng = deque(sub)
    sub.sort()
    max_space = 0
    idx = x
    length = len(space)

    # Now the entire loop should be of O(NlogN).
    while True:
        min_space = sub[0]  # O(1)
        if min_space > max_space:
            max_space = min_space

        if idx >= length:
            break

        # BEGIN O(1)
        rem_elem = rng.popleft()
        add_elem = space[idx]
        rng.append(add_elem)
        # END O(1)

        # BEGIN O(logN)
        pos = bisect.bisect_left(sub, rem_elem)
        sub.pop(pos)  # This might slow down to O(N)
        bisect.insort_left(sub, add_elem)
        # END O(logN)

        idx += 1

    return max_space


if __name__ == "__main__":
    assert comp_space(3, [2, 4, 6, 8, 5]) == 5