Finding the subarray with the minimum range

Question

Given an array of N positive integers, ranging from index 0 to N - 1, how can I find a contiguous subarray of length K with the minimum range possible. In other words, max(subarray) - min(subarray) is minimised. If there are multiple answers, any is fine.

For example, find the subarray of length 2 with the smallest range from [4, 1, 2, 6]

The answer would be [1, 2] as 2 - 1 = 1 gives the smallest range of all possible contiguous subarrays.

Other subarrays are [4, 1] (range 3), [2, 6] (range 4)

I'm using python and so far I've tried a linear search with min() max() functions and it just doesn't seem efficient to do so. I've thought of using a minheap but I'm not sure how you would implement this and I'm not even sure if it would work. Any help would be much appreciated.

edit: code added

# N = length of array_of_heights, K = subarray length
N, K = map(int, input().split(' '))
array_of_heights = [int(i) for i in input().split(' ')]



min_min = 100000000000000000000

# iterates through all subarrays in the array_of_heights of length K
for i in range(N + 1 - K):
    subarray = land[i : i + K]
    min_min = min(max(subarray)-min(subarray), min_min)

print(min_min)

I think you would have to maintain a window of size `k` while iterating along the array like a sliding window. — nice_dev, Jan 15 '20 at 07:11
You would need a minheap and a maxheap. And the code would implement a sliding window. When an element enters the window, it should be added to both heaps. When the max value leaves the window, it should be removed from the maxheap. Additional elements in the maxheap that are already outside the window should also be removed. Likewise for the minimum. — user3386109, Jan 15 '20 at 07:12
https://stackoverflow.com/questions/7861387/maximum-contiguous-subsequence-sum-of-at-least-length-l/7862283#7862283 — Masklinn, Jan 15 '20 at 07:15

abc · Answer 1 · 2020-01-15T15:14:43.037

1

You could use numpy to improve execution time.

Example:

def f1(l,k):
    subs = np.array([l[i:i+k] for i in range(len(l)-k+1)])
    return np.min(subs.max(axis=1) - subs.min(axis=1))

Small test (f2 is your function here).

>>> arr = np.random.randint(100,size=10000)
>>> timeit.timeit("f1(arr,4)",setup="from __main__ import f1,f2,np,arr",number=1)
0.01172515214420855
>>> timeit.timeit("f2(arr,4)",setup="from __main__ import f1,f2,np,arr",number=1)
14.226237731054425

edited Jan 15 '20 at 15:14

answered Jan 15 '20 at 08:04

abc

11,579
2
26
51

Out of interest, whats causing the marked time difference here? Numpy makes it run so much faster... – Brandon Ru Jan 15 '20 at 08:22
@BrandonRu there's an answer over here that gives an idea https://stackoverflow.com/a/8385658/171450 but basically you're working with much more efficient structures, in C using algorithms built for bulk array operations. – Aidan Kane Jan 15 '20 at 08:35

MBo · Accepted Answer · 2020-01-15T10:21:46.097

There is linear-time algorithm O(N)for getting min or max in moving window of specified size (while your implementation has O(N*K) complexity)

Using deque from collections module you can implement two parallel deques keeping minumum and maximum for current window position and retrieve the best difference after the only walk through the list.

import collections

def mindiff(a, k):
    dqmin = collections.deque()
    dqmax = collections.deque()
    best = 100000000
    for i in range(len(a)):
        if len(dqmin) > 0 and dqmin[0] <= i - k:
            dqmin.popleft()
        while len(dqmin) > 0 and a[dqmin[-1]] > a[i]:
            dqmin.pop()
        dqmin.append(i)
        if len(dqmax) > 0 and dqmax[0] <= i - k:
            dqmax.popleft()
        while len(dqmax) > 0 and a[dqmax[-1]] < a[i]:
            dqmax.pop()
        dqmax.append(i)
        if i >= k - 1:
            best = min(best, a[dqmax[0]]-a[dqmin[0]])
    return best

print(mindiff([4, 1, 2, 6], 2))

Finding the subarray with the minimum range

2 Answers2