Q. Given two arrays, A and B, of equal length, find the largest possible contiguous subarray 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 subarray has length 2
I can do this in O(n2) 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}')