CODEWITHSUNDEEP
arraysalgorithmtime-complexity
nikhil_vyas
nikhil_vyas

Reputation: 543

Longest consecutive sub-sequence with maximal and minimal end points

Given an array A of size n we need to find max of j-i such that for all k, i < k < j, a[i] <= a[k] and a[k] <= a[j].

I have been able to solve it in O(n^2) by dynamic programming. Is there a better solution?

Upvotes: 2

Views: 150

Answers (2)

David Eisenstat
David Eisenstat

Reputation: 65427

Here’s a new, tested, linear-time solution.

The code below computes the length of the longest subarray of each prefix a[:j + 1] for j from 0 to n - 1 (stored in k). The stack starts holds the indexes s from 0 to j such that a[s] <= a[t] for all t from s + 1 to j, i.e., those indexes that can start a valid subarray ending at index j or after. The stack blockers holds the indexes s from 0 to j such that a[s] > a[t] for all t from s + 1 to j, i.e., the minimal set of elements needed to rule out all invalid subarrays by dint of the last element not being maximum. Maintenance of starts and blockers takes amortized constant time, since at most one element is appended per loop iteration.

The valid subarrays ending at index j are those that start at some index in starts greater than that of all current blockers except j itself. Naively, we could scan backward each time to find the least suitable starting index, but then we might scan too much on average. Enter the variable i, which holds the index into starts most recently scanned. By starting the next scan at i + 1, we ensure that the amortized cost of the scan is constant, while still scanning all subarrays that may be longer than k.

import itertools


def longest(a):
    k = 0
    n = len(a)
    starts = []
    blockers = []
    for j in range(n):
        while starts and a[starts[-1]] > a[j]:
            del starts[-1]
        starts.append(j)
        while blockers and a[blockers[-1]] <= a[j]:
            del blockers[-1]
        if blockers:
            i = min(i + 1, len(starts) - 1)
            while i > 0 and starts[i - 1] > blockers[-1]:
                i -= 1
        else:
            i = 0
        k = max(k, j + 1 - starts[i])
        blockers.append(j)
    return k


def longest_slow(a):
    n = len(a)
    for k in range(n, 0, -1):
        for i in range(n - k + 1):
            b = a[i:i + k]
            if b[0] == min(b) and max(b) == b[-1]:
                return k
    return 0


def test():
    for n in range(9):
        for a in itertools.permutations(range(n)):
            assert longest(a) == longest_slow(a)


test()

Upvotes: 3

Ranald Lam
Ranald Lam

Reputation: 496

For each number, lets call it X. Find the last number thats larger than X out of those you have processed. For the sequence [3, 7, 5, 2, 1, 3, 2, 4], when you are processing X = 4, the last number thats largest is 5 and position Y = 2 (0-indexed).

Y can be found in O(log N) by maintaining a segment tree/fenwick tree that answers range maximum queries with the index of the tree being the values in the sequence and the values of the tree being the index in the sequence. Eg: when adding value X to the segment tree, we update index X of the segment tree with the index of X. To find Y, we simply query the tree for the range maximum where index > X.

Now we need to find the index of the minimum number between index Y and the index of X. This can be done using another segment tree/sparse table that handles range minimum query on the original sequence. If there are multiple minimum numbers, compute the one with the lowest index. Lets call the index Z. This will also require O(log N).

The answer should be the maximum of (index of X)-Z by doing these processing on every number in the sequence, yielding an overall complexity of O(N log N).

For the case [-1000,1000,0,1,2,3,4] provided by nikhil_vyas, When processing the last number, X = 4, Y will be 1 (value 1000), Z should be in between index 1 and 6 and it is index 2. Hence the answer would be (index of 4)-2 = 6-2 = 4. (i = 2, j = 6)

Edit: Y will be default to 'index -1' if there is no number larger than X so far. In that case, Z can exist between index 0 up till the current processed number. If Z does not exist/cannot exist, ignore this number kf the sequence and move on to the next.

Upvotes: 2

Related Questions