Minimum number of strictly increasing subsequences

Question

Problem Statement

Adrian is a runner and every morning he goes for a run with his friends. Every morning, their coach gives them a list of checkpoints from left to right to cover. Each checkpoint has a special value. Now, the coach has a rule such that a runner will only go to checkpoints whose value is strictly higher than the previous checkpoints. Also, all runners are supposed to move strictly towards the right. You need to find out the minimum number of runners it would take to cover all the checkpoints.

The input is taken in the form of an array which denotes the values of checkpoints from left to right.

Sample Input

[12, 15, 18, 17, 20, 25, 27, 19, 20, 21]

Sample Output

2

Explanation of the Sample Case:

First runner will cover [12, 15, 18, 19, 20, 21] and the second runner will cover [17, 25, 27].

My code

My recursive algorithm gives the correct output but it is not efficient enough.

visited = [0] * len(A)
def ans(A, visited):
    n = len(A)
    if visited.count(0) == 0:
        return 0
    num = 0
    ind = visited.index(0)
    visited[ind] = 1
    min_num = A[ind]
    for i in range(ind, n):
        if A[i] > min_num and visited[i] == 0:
            visited[i] = 1
            min_num = A[i]
    return 1 + ans(A, visited)  

Question

What's the way this problem could be solved more efficiently? My code was giving TLE on some test cases. I couldn't figure out how to make it work.

My code was giving the correct output. It is just not efficient enough.

Answer 1

Your algorithm has a time complexity of O(n²).

You can use the following O(nlogn) algorithm:

Create an empty list, which will get one value per needed runner (so far). For each runner you will store the maximum value that the corresponding runner will visit (so far), and the values (once they get in there) will be ordered in descending order (invariant).

Go through the input once. For each visited value v, perform a binary search in the above mentioned list in order to find the greatest value w that is less than it. If found, overwrite that w with v (i.e. the corresponding runner will visit it). If not found, then append v to that list: this means an additional runner is needed. Of course, that will be the case when processing the first input value.

At the end of this process, the length of the new list represents the answer (the minimum number of runners needed).

Implementation

For the binary search I'll use bisect, but you can of course implement your own.

As bisect only works on lists that are in ascending order, I will visit the elements from A in reverse order, and update the runner's information to be the minimum value so far -- as we are working in the opposite direction:

def ans(A):
    runners = []
    for val in reversed(A):
        i = bisect.bisect_left(runners, val + 1)
        if i >= len(runners):
            runners.append(val)
        else:
            runners[i] = val
    return len(runners)

Note: val + 1 is needed to deal correctly with equal values (I assume integers). In the case there is a duplicate value, this means the same runner cannot visit it, so we should look for a runner with at least a value of val + 1 (again: we are working backwards here).