Inefficient Solution


#1

Hi,

the solutions in Python are inefficient, since they recompute min and max for every step, result in a O(n^2) solution.

Observe that you can use queues to track the min and max elements for every step in an efficient way.

I suggest to use my solution as an editorial one:
from collections import deque
import time

class Solution:
# @param A : list of integers
# @param B : integer
# @return an integer
def solve(self, A, B):
if B < 0:
return 0

    n = len(A)
    s_idx = 0
    longest_dist = 1

    min_queue = deque()
    max_queue = deque()
    e_idx = s_idx

    while e_idx < n:
        curr_elem = A[e_idx]
        while min_queue and min_queue[-1] > curr_elem:
            min_queue.pop()

        while max_queue and max_queue[-1] < curr_elem:
            max_queue.pop()

        min_queue.append(curr_elem)
        max_queue.append(curr_elem)

        while max_queue[0] - min_queue[0] >= B:
            while A[s_idx] != min_queue[0] and A[s_idx] != max_queue[0]:
                s_idx += 1

            if A[s_idx] == min_queue[0]:
                min_queue.popleft()
            if A[s_idx] == max_queue[0]:
                max_queue.popleft()

            s_idx += 1

        if e_idx - s_idx + 1 > longest_dist:
            longest_dist = e_idx - s_idx + 1
        e_idx += 1

    return longest_dist