# Algorithms question: Largest contiguous subset selection

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?

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]] < 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


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]] < 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}')


You can solve the problem in $$O(n \log n)$$ time. Construct a data structure $$D_A$$ that can answer queries of the following form in constant time: given two indices $$i \in \{1,\dots,n\}$$ and $$j \in \{i,\dots,n\}$$, report $$\max_{h=i,\dots,j} A[h]$$. This can be done in time $$O(n)$$. Similarly, construct a data structure $$D_B$$ that can report $$\min_{h=i,\dots,j} B[h]$$. Have a look at this paper for details.

For each index $$i=1,\dots, n$$ such that $$A[i], find the largest index $$j \ge i$$ such that $$M_i(j)=\max_{h=i,\dots,j} A[h]$$ is smaller than $$m_i(j) = \min_{h=i,\dots,j} B[h]$$. You can do so by noticing that $$M_i(\cdot)$$ is monotonically non-decreasing while $$m_i(\cdot)$$ is monotonically non-increasing. This implies that $$\forall j' \le j, M_i(j') and that $$\forall j'>j, M_i(j') \ge m_i(j')$$. As a consequence you can use binary search to find $$j$$ with only $$O(\log n)$$ queries to $$D_A$$ and $$D_B$$. Consider $$(i,j)$$ as a candidate solution.

Finally, among all the candidate pairs $$(i,j)$$, return one of those that maximize $$j-i$$ (if any).

The idea is once you have parsed a part of the 2 arrays and got a subsequence i,j then no go through it again as we already know the result

A[i-j]≤B[i-j] (that what kept the loop going)

and A[j+1]>B[j+1] (that what stopped it)

Then we keep the length of this interval in a variable, say max and start checking for a longer sequence starting from j+2

A Pseudocode could be

i=j=0;

N= array_size;

While(i<N)

{

While (A[j]≤B[j)AND(j<N) j++;

//now A[j]>B[j]

If ((j-i) > max) { Res.str=i; Res.end=j-1;}

i=j+1;

}

• Welcome COMPUTER SCIENCE @SE. I think the indentation of your Pseudocode looks strange even when using   "digit blanks". The two blanks to create an effective line break need to precede it: append them to the line before. Sep 15 at 6:51