Review the fundamentals: Arrays guide and time complexities.
Minimum Conveyor Segment for Target Shipments — Problem Statement & Solution Guide
Quick Answer & Algorithm Key Takeaway
Master coding challenges related to Arrays and solve the Minimum Conveyor Segment for Target Shipments problem optimally.
O(n)O(1)Problem Description
You are given an integer array shipments representing the category IDs of packages on a conveyor belt, along with two integers target and k. Your task is to determine the minimum length of a contiguous subarray that contains at least k occurrences of the target category ID. If no such subarray exists, return -1.
The solution must efficiently scan the array to find the shortest window satisfying the condition. The input array may contain negative integers, zero, or positive integers, and the target value may or may not be present in the array.
Return the length of the shortest valid segment, or -1 if it is impossible to form such a segment.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Minimum Conveyor Segment for Target Shipments"
WHY DOES IT MATTER?
The sliding‑window pattern is essential for any problem that asks for an optimal contiguous segment under a monotonic constraint (e.g., length, sum, count). It transforms a potentially quadratic search into linear time, making it viable for real‑time systems and large datasets.
OPTIMIZATION CHALLENGE
The key insight is that once the window satisfies the "k occurrences" condition, any further expansion can only increase its length, so you should immediately try to contract from the left to discard unnecessary elements while preserving the count. This greedy shrink step guarantees minimality for each right endpoint.
REAL-WORLD CONNECTION
Think of a conveyor belt in a warehouse where you need to pick the shortest stretch that contains at least k items of a specific SKU before the belt moves on. By continuously tracking how many of that SKU are in the current view and adjusting the view boundaries, you minimize the time workers spend handling the belt.
During an interview, implement the sliding window with two indices and a single integer counter for the target. Update the counter only when you encounter the target, and remember to decrement it when moving the left pointer. This keeps the code simple, avoids extra data structures, and reduces the chance of off‑by‑one bugs.
COMPLEXITY AT A GLANCE
O(n)O(1)Core Theory — Why This Approach?
The problem is a classic sliding‑window (two‑pointer) scenario where we need the smallest contiguous segment that satisfies a frequency constraint. A naive scan that examines every possible subarray would be O(n²) because for each start index we would extend to every possible end index and count occurrences, which quickly becomes infeasible for n up to 10⁵ or more. The optimal paradigm leverages the monotonic nature of the window: as we expand the right pointer we only increase the count of the target, and as we contract the left pointer we only decrease it. By maintaining a running count of the target inside the current window, we can decide in O(1) whether the window meets the "at least k" condition and then greedily shrink it to the minimal size for that right endpoint. This yields a linear‑time solution because each element is visited at most twice – once when the right pointer moves forward and once when the left pointer moves forward.
Interview Questions on This Problem
Q1How would you modify the solution if the requirement changed to "exactly k" occurrences of the target instead of "at least k"?
You would still use a sliding window but only shrink the left pointer while the count is greater than k; when the count equals k you record the window length, then continue expanding the right pointer. If the count exceeds k, you must move the left pointer until the count drops back to k or below, ensuring you never record a window with more than k occurrences.
Q2Can this algorithm be extended to handle multiple target values simultaneously, e.g., find the smallest subarray containing at least k₁ of value a and k₂ of value b?
Yes. Maintain a hash map that tracks counts for each required value. The window is valid when all counts meet or exceed their respective thresholds. When the window is valid, try to shrink from the left while preserving validity, updating the minimum length. The time remains O(n) but the space grows with the number of distinct targets.
Q3What is the worst‑case scenario for the sliding‑window approach, and how does it compare to the brute‑force method in terms of constant factors?
The worst case occurs when the target appears rarely, forcing the right pointer to traverse the entire array while the left pointer moves only a few steps, still O(n). Compared to brute force's O(n²) comparisons, the sliding window eliminates the inner loop entirely, reducing both time and memory overhead dramatically, which is critical for large‑scale data streams.
Examples
Input
shipments = [3, 1, 3, 2, 3, 1, 3], target = 3, k = 2
Output
3
Explanation: The subarray [3, 2, 3] (indices 2 to 4) contains two 3s and has length 3. The subarray [3, 1, 3] (indices 4 to 6) also contains two 3s and has length 3. No shorter subarray contains at least two 3s. Thus, the minimum length is 3.
Input
shipments = [1, 2, 3, 4, 5], target = 3, k = 2
Output
-1
Explanation: The target value 3 appears only once in the array. Since k = 2, it is impossible to find a subarray with at least two occurrences of 3. Therefore, return -1.
Input
shipments = [5, 5, 5, 5], target = 5, k = 3
Output
3
Explanation: The subarray [5, 5, 5] (indices 0 to 2) contains three 5s and has length 3. The subarray [5, 5, 5] (indices 1 to 3) also contains three 5s and has length 3. The minimum length is 3.
Input
shipments = [1, 2, 1, 2, 1, 2, 1], target = 1, k = 3
Output
5
Explanation: The subarray [1, 2, 1, 2, 1] (indices 0 to 4) contains three 1s and has length 5. The subarray [1, 2, 1, 2, 1] (indices 2 to 6) also contains three 1s and has length 5. No shorter subarray contains at least three 1s. Thus, the minimum length is 5.
Constraints
- 1 <= shipments.length <= 10^5
- -10^9 <= shipments[i] <= 10^9
- -10^9 <= target <= 10^9
- 1 <= k <= 10^5
Optimal Approach & Strategy
Use a sliding window with two pointers and a running count of the target; expand right until count ≥ k, then shrink left while maintaining count ≥ k, updating the answer each time.
Brute Force Approach
Check every possible subarray, count target occurrences inside each, and keep the minimum length that meets the requirement.
Code Solutions
function minConveyorSegment(shipments, target, k) {
let left = 0, count = 0, minLen = shipments.length + 1;
for (let right = 0; right < shipments.length; right++) {
if (shipments[right] === target) count++;
while (count >= k) {
minLen = Math.min(minLen, right - left + 1);
if (shipments[left] === target) count--;
left++;
}
}
return minLen === shipments.length + 1 ? -1 : minLen;
}#include <vector>
#include <algorithm>
int minConveyorSegment(std::vector<int>& shipments, int target, int k) {
int n = shipments.size();
int left = 0, count = 0, minLen = n + 1;
for (int right = 0; right < n; ++right) {
if (shipments[right] == target) ++count;
while (count >= k) {
minLen = std::min(minLen, right - left + 1);
if (shipments[left] == target) --count;
++left;
}
}
return (minLen == n + 1) ? -1 : minLen;
}public class Solution {
public int minConveyorSegment(int[] shipments, int target, int k) {
int left = 0, count = 0, minLen = shipments.length + 1;
for (int right = 0; right < shipments.length; right++) {
if (shipments[right] == target) count++;
while (count >= k) {
minLen = Math.min(minLen, right - left + 1);
if (shipments[left] == target) count--;
left++;
}
}
return minLen == shipments.length + 1 ? -1 : minLen;
}
}def min_conveyor_segment(shipments, target, k):
left = 0
count = 0
min_len = len(shipments) + 1
for right, val in enumerate(shipments):
if val == target:
count += 1
while count >= k:
min_len = min(min_len, right - left + 1)
if shipments[left] == target:
count -= 1
left += 1
return -1 if min_len == len(shipments) + 1 else min_lenfunction minConveyorSegment(shipments, target, k) {
let left = 0, count = 0, minLen = shipments.length + 1;
for (let right = 0; right < shipments.length; right++) {
if (shipments[right] === target) count++;
while (count >= k) {
minLen = Math.min(minLen, right - left + 1);
if (shipments[left] === target) count--;
left++;
}
}
return minLen === shipments.length + 1 ? -1 : minLen;
}Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.