Review the fundamentals: Arrays guide and time complexities.
Shortest Conveyor Section for Target Shipments — Problem Statement & Solution Guide
Quick Answer & Algorithm Key Takeaway
Master coding challenges related to Arrays and solve the Shortest Conveyor Section for Target Shipments problem optimally.
O(n)O(1)Problem Description
A logistics warehouse manages a sequence of packages represented by an array of integers shipments, where each integer denotes a specific category of goods. Identify the shortest continuous subarray that contains at least k packages of a category equal to target. If no such section exists, return -1.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Shortest Conveyor Section for Target Shipments"
WHY DOES IT MATTER?
Finding minimal subarrays under count constraints is a core pattern for resource allocation and threshold detection.
OPTIMIZATION CHALLENGE
The key is reducing the quadratic enumeration to a linear pass by exploiting monotonicity of the count condition.
REAL-WORLD CONNECTION
It mirrors locating the shortest conveyor segment that can fulfill a shipment quota before dispatch.
Keep a single integer counter for the target and update it incrementally; avoid recomputing frequencies on each shrink.
COMPLEXITY AT A GLANCE
O(n)O(1)Core Theory — Why This Approach?
The problem reduces to finding the minimal length window in a one‑dimensional array that contains at least k occurrences of a specific value (target). A naive double‑loop enumerates every subarray, leading to O(n²) time which quickly becomes infeasible for large n. The optimal paradigm leverages the sliding‑window (two‑pointer) technique: expand the right pointer until the window satisfies the count condition, then contract the left pointer to shrink the window while preserving validity, updating the best length along the way. This yields a linear scan because each element is visited at most twice, guaranteeing O(n) time and O(1) extra space.
The sliding‑window works because the condition (≥ k target elements) is monotonic with respect to window expansion – adding elements cannot invalidate a previously valid window. By maintaining a running count of target occurrences, we avoid recomputing frequencies for each candidate subarray, which is the key insight that transforms the brute‑force approach into an efficient solution suitable for real‑time logistics systems.
Interview Questions on This Problem
Q1How does the sliding‑window technique ensure O(n) time for this problem?
Each array index is moved by the left or right pointer at most once, so total operations are linear. The window’s validity is updated in O(1) using a running count.
Q2What modifications are needed if the requirement changes to exactly k occurrences of target?
The window must shrink only while the count exceeds k, stopping when it equals k. This still allows a linear scan with the same two‑pointer logic.
Q3Can this approach be extended to multiple target values simultaneously?
Yes, maintain a hash map of counts for each target and check that each meets its required threshold. The complexity remains O(n) but space grows with the number of distinct targets.
Examples
Input
shipments = [1, 3, 1, 2, 1, 4, 1], target = 1, k = 3
Output
5
Explanation: The shortest contiguous subarrays containing at least 3 instances of '1' are [1, 3, 1, 2, 1] (indices 0 to 4) and [1, 2, 1, 4, 1] (indices 2 to 6). Both have a length of 5.
Input
shipments = [2, 2, 3, 2], target = 2, k = 4
Output
-1
Explanation: The array only contains three occurrences of the target '2'. It is impossible to find any section containing 4 occurrences, so the output is -1.
Constraints
- 1 <= shipments.length <= 10^5
- 1 <= shipments[i], target <= 10^9
- 1 <= k <= 10^5
Optimal Approach & Strategy
Apply a sliding‑window with a running count: move the right pointer to satisfy the condition, then move the left pointer to shrink while still valid, updating the best length.
Brute Force Approach
Enumerate every possible subarray, count target occurrences inside each, and keep the minimum length that meets the requirement.
Code Solutions
/**
* @param {number[]} shipments
* @param {number} target
* @param {number} k
* @return {number}
*/
function shortestConveyorSection(shipments, target, k) {
let left = 0, count = 0;
let ans = shipments.length + 1;
for (let right = 0; right < shipments.length; ++right) {
if (shipments[right] === target) count++;
while (count >= k) {
ans = Math.min(ans, right - left + 1);
if (shipments[left] === target) count--;
left++;
}
}
return ans === shipments.length + 1 ? -1 : ans;
}#include <bits/stdc++.h>
using namespace std;
int shortestConveyorSection(const vector<int>& shipments, int target, int k) {
const int n = shipments.size();
int left = 0, count = 0;
int ans = n + 1; // sentinel larger than any possible length
for (int right = 0; right < n; ++right) {
if (shipments[right] == target) ++count;
while (count >= k) {
ans = min(ans, right - left + 1);
if (shipments[left] == target) --count;
++left;
}
}
return (ans == n + 1) ? -1 : ans;
}
public class Solution {
// Returns the length of the shortest subarray containing at least k occurrences of target.
public int shortestConveyorSection(int[] shipments, int target, int k) {
int n = shipments.length;
int left = 0, count = 0;
int ans = n + 1; // sentinel value
for (int right = 0; right < n; ++right) {
if (shipments[right] == target) {
count++;
}
while (count >= k) {
ans = Math.min(ans, right - left + 1);
if (shipments[left] == target) {
count--;
}
left++;
}
}
return (ans == n + 1) ? -1 : ans;
}
}
def shortest_conveyor_section(shipments, target, k):
"""Return the length of the shortest contiguous subarray that contains at least k occurrences of target.
If such a subarray does not exist, return -1.
"""
n = len(shipments)
left = 0
count = 0
ans = n + 1
for right in range(n):
if shipments[right] == target:
count += 1
while count >= k:
ans = min(ans, right - left + 1)
if shipments[left] == target:
count -= 1
left += 1
return -1 if ans == n + 1 else ans
/**
* @param {number[]} shipments
* @param {number} target
* @param {number} k
* @return {number}
*/
function shortestConveyorSection(shipments, target, k) {
let left = 0, count = 0;
let ans = shipments.length + 1;
for (let right = 0; right < shipments.length; ++right) {
if (shipments[right] === target) count++;
while (count >= k) {
ans = Math.min(ans, right - left + 1);
if (shipments[left] === target) count--;
left++;
}
}
return ans === shipments.length + 1 ? -1 : ans;
}
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.