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