Frontend School

Longest Subarray with Bounded Price Difference

DSA
medium

Longest Subarray with Bounded Price Difference

Medium
Sliding Window
Deque
Monotonic Queue

Overview

At Meesho, ensuring product consistency and managing inventory effectively across various sellers is crucial. Imagine you're building a feature to identify product batches or groups that maintain a certain level of similarity in their pricing. This problem asks you to find the longest contiguous sequence of product prices (a subarray) where the difference between the most expensive and the least expensive product in that sequence does not exceed a given threshold k. This helps in grouping similar products for promotions or identifying price anomalies.

What you need to do / Task

You are tasked with implementing a function longestSubarrayWithBoundedDifference that takes an array of positive integers nums representing product prices and an integer k representing the maximum allowed price difference. Your function should return the length of the longest non-empty subarray of nums such that the absolute difference between any two elements within that subarray is less than or equal to k. More precisely, for any subarray [min_val, ..., max_val], max_val - min_val <= k.

Input & output

Input:

  • nums: An array of positive integers (number[]), where each nums[i] represents a product's price.
  • k: A non-negative integer (number), representing the maximum allowed difference between the maximum and minimum elements in a valid subarray.

Output:

  • A single integer (number) representing the length of the longest valid subarray. If no such subarray exists (e.g., nums is empty), return 0. If nums contains only one element, that element forms a valid subarray of length 1.

Clarifications

  • Empty nums array: If nums is empty, the function should return 0.
  • Single element array: If nums contains a single element, the difference between max and min is 0, which is always <= k. So, the length will be 1.
  • k = 0: If k is 0, it means all elements in the subarray must be identical.
  • Positive integers: All prices nums[i] are positive.

Examples

1

Example 1

Input:

nums = [10,1,2,4,7,2], k = 5

Output:

4

Note:

The longest subarray where the difference between max and min is at most 5 is [2,4,7,2]. Here, the maximum element is 7 and the minimum is 2, so their difference is 5, which is <= k. The length is 4.

2

Example 2

Input:

nums = [4,8,5,1,7,9], k = 3

Output:

2

Note:

The longest valid subarrays are [8,5] (max=8, min=5, diff=3) and [7,9] (max=9, min=7, diff=2), both with length 2.

3

Example 3

Input:

nums = [1,2,3], k = 0

Output:

1

Note:

Since k is 0, all elements in a valid subarray must be identical. The longest such subarrays are [1], [2], or [3], each with length 1.

Constraints

Constraints & assumptions

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^9
  • 0 <= k <= 10^9
  • The input array nums will only contain integers.

Out of scope

  • Input validation beyond the given constraints (e.g., handling non-numeric values or negative prices).
  • Any UI/UX considerations for displaying the longest subarray.

What interviewers evaluate

  • Correctness: The solution accurately identifies the longest valid subarray across all test cases, including edge cases.
  • Efficiency: The algorithm achieves optimal time complexity, typically O(N), and reasonable space complexity for the given constraints.
  • Code Quality: The code is clean, readable, well-structured, and follows good programming practices.
  • Problem-Solving Approach: Demonstrates a clear understanding of the sliding window technique and its application with auxiliary data structures (like deques) for efficient min/max tracking.

Loading editor...