2
$\begingroup$

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?

$\endgroup$
0
3
$\begingroup$

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}')
$\endgroup$
0
$\begingroup$

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]<B[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')<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).

$\endgroup$
0
$\begingroup$

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;

}

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – greybeard
    Sep 15 at 6:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.