Find shortest subarray with range ≥ k

Q: Find shortest subarray with range ≥ k

This question evaluates proficiency with array algorithms and range-query reasoning, testing understanding of max/min behavior over contiguous subarrays and use of appropriate data-structure techniques; it belongs to the Coding & Algorithms domain.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

Problem

You are given an integer array nums of length n and an integer k.

Define the range of a subarray as:

$\max(\text{subarray}) - \min(\text{subarray})$

Return the length of the shortest non-empty contiguous subarray whose range is at least k.

If no such subarray exists, return -1.

Input

nums : array of integers (can include negatives)
k : non-negative integer

Output

An integer: the minimum length of a qualifying subarray, or -1 if none exists.

Constraints (typical interview scale)

1 <= n <= 2 * 10^5
-10^9 <= nums[i] <= 10^9
0 <= k <= 10^9

Examples

nums = [1, 3, 2], k = 2 → answer 2 (subarray [1,3] has range 2 )
nums = [5, 5, 5], k = 1 → answer -1