patternMinor

Algorithms question: Largest contiguous subset selection

Submitted by: @import:stackexchange-cs·Mar 10, 2026·

Viewed 0 times

divide-and-conquer cs stackoverflow algorithms

selectionalgorithmslargestcontiguoussubsetquestion

Problem

Q. Given two arrays, $A$ and $B$, of equal length, find the largest possible contiguous subset of indices $[i,j]$ such that $\max(A[i: j]) < \min(B[i: j])$.

Example: $A = [10, 21, 5, 1, 3], B = [3, 1, 4, 23, 56]$.

Explanation: $A[4] = 1, A[5] = 3$, $B[4] = 23, B[5] = 56$, $\max(A[4], A[5]) < \min(B[4], B[5])$.

The indices are $[4,5]$ (inclusive), and the largest contiguous subset has size 2.

I can do this in $O(n^2)$ brute force method but cannot seem to reduce the time complexity. Any ideas?

Solution

O(n) solution:

Move index j from left to right and drag i behind so that the window from i to j is valid. So always increase j by 1, and then increase i as much as needed for the window to be valid.

To do that, keep a queue Aq of indexes of non-increasing A-values. Then A[Aq[0]] tells you the max A-value in the window. Similarly, keep a queue for non-decreasing B-values.

For each new j, first update Aq and Bq according to the new A-value and new B-value. Then, while the window is invalid, increase i and drop Aq[0] and Bq[0] if they're i. When both j and i are updated, update the result with the window size j - i - 1.

Python implementation:

def solution(A, B):
    Aq = deque()
    Bq = deque()
    i = 0
    maxlen = 0
    for j in range(len(A)):
        while Aq and A[Aq[-1]]  B[j]:
            Bq.pop()
        Bq.append(j)
        while Aq and A[Aq[0]] >= B[Bq[0]]:
            if Aq[0] == i:
                Aq.popleft()
            if Bq[0] == i:
                Bq.popleft()
            i += 1
        maxlen = max(maxlen, j - i + 1)
    return maxlen

Test results from comparing against a naive brute force reference solution:

expect:  83   result:  83   same: True
expect: 147   result: 147   same: True
expect: 105   result: 105   same: True
expect:  71   result:  71   same: True
expect: 110   result: 110   same: True
expect:  56   result:  56   same: True
expect: 140   result: 140   same: True
expect: 109   result: 109   same: True
expect:  86   result:  86   same: True
expect: 166   result: 166   same: True

Testing code (Try it online!)

from timeit import timeit
from random import choices
from collections import deque
from itertools import combinations

def solution(A, B):
    Aq = deque()
    Bq = deque()
    i = 0
    maxlen = 0
    for j in range(len(A)):
        while Aq and A[Aq[-1]]  B[j]:
            Bq.pop()
        Bq.append(j)
        while Aq and A[Aq[0]] >= B[Bq[0]]:
            if Aq[0] == i:
                Aq.popleft()
            if Bq[0] == i:
                Bq.popleft()
            i += 1
        maxlen = max(maxlen, j - i + 1)
    return maxlen

def naive(A, B):
    return max((j - i + 1
                for i, j in combinations(range(len(A)), 2)
                if max(A[i:j+1]) < min(B[i:j+1])),
               default=0)

for _ in range(10):
    n = 500
    A = choices(range(42), k=n)
    B = choices(range(1234), k=n)
    expect = naive(A, B)
    result = solution(A, B)
    print(f'expect: {expect:3}   result: {result:3}   same: {result == expect}')

Code Snippets

def solution(A, B):
    Aq = deque()
    Bq = deque()
    i = 0
    maxlen = 0
    for j in range(len(A)):
        while Aq and A[Aq[-1]] < A[j]:
            Aq.pop()
        Aq.append(j)
        while Bq and B[Bq[-1]] > B[j]:
            Bq.pop()
        Bq.append(j)
        while Aq and A[Aq[0]] >= B[Bq[0]]:
            if Aq[0] == i:
                Aq.popleft()
            if Bq[0] == i:
                Bq.popleft()
            i += 1
        maxlen = max(maxlen, j - i + 1)
    return maxlen

expect:  83   result:  83   same: True
expect: 147   result: 147   same: True
expect: 105   result: 105   same: True
expect:  71   result:  71   same: True
expect: 110   result: 110   same: True
expect:  56   result:  56   same: True
expect: 140   result: 140   same: True
expect: 109   result: 109   same: True
expect:  86   result:  86   same: True
expect: 166   result: 166   same: True

from timeit import timeit
from random import choices
from collections import deque
from itertools import combinations

def solution(A, B):
    Aq = deque()
    Bq = deque()
    i = 0
    maxlen = 0
    for j in range(len(A)):
        while Aq and A[Aq[-1]] < A[j]:
            Aq.pop()
        Aq.append(j)
        while Bq and B[Bq[-1]] > B[j]:
            Bq.pop()
        Bq.append(j)
        while Aq and A[Aq[0]] >= B[Bq[0]]:
            if Aq[0] == i:
                Aq.popleft()
            if Bq[0] == i:
                Bq.popleft()
            i += 1
        maxlen = max(maxlen, j - i + 1)
    return maxlen

def naive(A, B):
    return max((j - i + 1
                for i, j in combinations(range(len(A)), 2)
                if max(A[i:j+1]) < min(B[i:j+1])),
               default=0)

for _ in range(10):
    n = 500
    A = choices(range(42), k=n)
    B = choices(range(1234), k=n)
    expect = naive(A, B)
    result = solution(A, B)
    print(f'expect: {expect:3}   result: {result:3}   same: {result == expect}')

Context

StackExchange Computer Science Q#143926, answer score: 3

Revisions (0)

No revisions yet.