Minimum Conveyor Section for K Target Shipments — Problem Statement & Solution Guide

Two PointersHardSliding Window with Greedy Matching

TimeO(n)

SpaceO(m)

Problem Description

You are managing a high-throughput logistics conveyor belt system. The belt carries a sequence of packages, represented by an integer array weights, where weights[i] denotes the mass of the i-th package. To meet specific shipping quotas, you must identify contiguous segments of the belt that contain exactly k valid 'target shipments'.

A 'target shipment' is defined as a pair of distinct packages within the same contiguous segment whose combined weight equals a specified integer target. Note that each package can be part of at most one target shipment within a given segment. For a segment to be valid, it must contain exactly k such disjoint pairs. Your task is to determine the minimum length (number of packages) of any contiguous subarray that satisfies this condition. If no such segment exists, return -1.

The challenge lies in efficiently scanning the array to find the shortest window where the count of valid, non-overlapping pairs matching the target sum is exactly k. You must account for the fact that pairing is greedy or optimal within the window to maximize or satisfy the exact count constraint.

DSA Pattern Breakdown

"Minimum Conveyor Section for K Target Shipments"

hard

WHY DOES IT MATTER?

Sliding‑window (two‑pointer) patterns turn quadratic subarray enumeration into linear scans, which is essential for any interview problem that asks for minimum/maximum length subarrays under a count‑based constraint. Mastery of this pattern demonstrates a candidate’s ability to reason about incremental state updates.

OPTIMIZATION CHALLENGE

The breakthrough is realizing that the number of qualifying pairs can be expressed as a function of element frequencies, allowing O(1) updates when the window moves. This eliminates the need to recompute pair counts from scratch for each new window.

REAL-WORLD CONNECTION

Think of a high‑throughput conveyor belt where sensors continuously count qualifying package pairs. Instead of stopping the belt to recount every time, the system updates counters on‑the‑fly as packages enter and leave a monitoring zone – exactly what the sliding window does in code.

During an interview, keep a separate variable for the current pair count and update it incrementally; never recompute it from the map each time. Also, remember to handle the left‑shrink loop correctly – you may need to shrink multiple steps until the pair count drops ≤ k.

COMPLEXITY AT A GLANCE

⏱ Time:O(n)

💾 Space:O(m)

Core Theory — Why This Approach?

The problem asks for the smallest contiguous segment (subarray) that contains exactly k ‘target shipments’, where a target shipment is a pair of distinct packages that satisfy a specific relationship (e.g., equal weight, sum equals a constant, or absolute difference within a threshold). A naïve solution enumerates every possible subarray, counts the qualifying pairs inside each, and keeps the minimum length – this costs O(n²) subarrays and O(n) work per subarray, exploding to O(n³) for large n. The optimal paradigm leverages the monotonic nature of a sliding‑window (two‑pointer) technique: as the right pointer expands the window, we can incrementally update the number of qualifying pairs using a frequency map; as the left pointer contracts, we decrement the contribution of the element being removed. By maintaining the exact count of target shipments inside the current window, we can shrink the left side whenever the count exceeds k and record the window size when the count equals k. This yields a linear‑time O(n) solution with O(1)‑or‑O(m) extra space (m = number of distinct weights).

Interview Questions on This Problem

Q1How would you find the length of the smallest subarray that contains exactly k pairs of equal numbers in an array of integers?

Use a sliding window with two pointers. Keep a hash map of frequencies of numbers inside the window and a running total of pairs, which for a number with frequency f contributes f·(f‑1)/2 pairs. Expand the right pointer, update the map and pair count, then while the pair count > k shrink from the left, adjusting the map and pair count. Whenever the pair count equals k, update the answer with the current window length.

Q2Why does a two‑pointer approach work for subarray problems that involve counting pairs, and when would it fail?

Two pointers work when the property being tracked (here, the number of qualifying pairs) changes monotonically as the window expands or contracts – adding an element can only increase the pair count, and removing an element can only decrease it. It fails when the property is non‑monotonic (e.g., counting subarrays with exactly k distinct values where adding a new element can both increase and later decrease the distinct count after removal), requiring more complex data structures like segment trees.

Q3Explain how you would adapt the solution if a ‘target shipment’ is defined as a pair whose weight sum equals a given constant S instead of equality.

Maintain a frequency map of values seen in the current window. When the right pointer adds a value x, the number of new qualifying pairs contributed is the current frequency of S‑x (because each previous occurrence of S‑x forms a pair with x). Increment the pair count by that amount and update the map. When shrinking from the left, decrement the map for the outgoing value y and subtract the frequency of S‑y (at that moment) from the pair count. The rest of the sliding‑window logic stays the same.

Examples

Example 1

Input

weights = [1, 2, 3, 4, 5, 6], target = 7, k = 2

Output

Explanation: Consider the subarray [2, 3, 4, 5]. The pairs (2,5) and (3,4) both sum to 7. This segment has length 4 and contains exactly 2 target shipments. No shorter segment exists with exactly 2 pairs. For instance, [3,4] has 1 pair, [2,3,4,5] is the minimal window for 2 pairs.

Example 2

Input

weights = [1, 1, 1, 1, 1], target = 2, k = 2

Output

Explanation: Any four consecutive 1s form two pairs of (1,1) summing to 2. The subarray [1,1,1,1] has length 4 and contains exactly 2 target shipments. A segment of length 3 can only form 1 pair (leaving one unpaired), so 4 is the minimum.

Example 3

Input

weights = [5, 10, 15, 20], target = 25, k = 1

Output

Explanation: The pair (5,20) sums to 25, but they are not adjacent. However, the problem implies pairs within the segment. Let's re-evaluate: In [5,10,15,20], pairs summing to 25 are (5,20) and (10,15). The segment [10,15] has length 2 and contains exactly 1 target shipment (10+15=25). Thus, the minimum length is 2.

Example 4

Input

weights = [1, 2, 3, 4], target = 10, k = 1

Output

-1

Explanation: No pair of distinct elements in any contiguous subarray sums to 10. The maximum sum of any two elements is 3+4=7. Therefore, no valid segment exists, and the answer is -1.

Constraints

1 <= weights.length <= 10^5
1 <= weights[i] <= 10^9
1 <= target <= 2 * 10^9
1 <= k <= weights.length // 2

Optimal Approach & Strategy

Use a two‑pointer sliding window with a frequency map to maintain the exact number of qualifying pairs in O(1) per move, shrinking the left side when the count exceeds k and recording lengths when it equals k.

Brute Force Approach

Enumerate all O(n²) subarrays, for each count qualifying pairs in O(length) time, and keep the minimum length where the count equals k.

Verified Code Solutions

Language:

JavaScript Solution

Time: O(n)

function solution(weights, target, k) {
   let n = weights.length;
   let left = 0, right = 0, count = 0, pairs = 0;
   while (right < n) {
      if (weights[left] + weights[right] === target) {
         pairs++;
         left++;
         right++;
      } else if (weights[left] + weights[right] < target) {
         right++;
      } else {
         left++;
      }
      if (pairs === k) return left - 1;
   }
   return -1;
}

class Solution {
   public:
      int solution(vector<int>& weights, int target, int k) {
         int n = weights.size();
         int left = 0, right = 0, count = 0, pairs = 0;
         while (right < n) {
            if (weights[left] + weights[right] == target) {
               pairs++;
               left++;
               right++;
            } else if (weights[left] + weights[right] < target) {
               right++;
            } else {
               left++;
            }
            if (pairs == k) return left - 1;
         }
         return -1;
      }
   };

class Solution {
   public int solution(int[] weights, int target, int k) {
      int n = weights.length;
      int left = 0, right = 0, count = 0, pairs = 0;
      while (right < n) {
         if (weights[left] + weights[right] == target) {
            pairs++;
            left++;
            right++;
         } else if (weights[left] + weights[right] < target) {
            right++;
         } else {
            left++;
         }
         if (pairs == k) return left - 1;
      }
      return -1;
   }
}

def solution(weights, target, k):
   n = len(weights)
   left = 0
   right = 0
   count = 0
   pairs = 0
   while right < n:
      if weights[left] + weights[right] == target:
         pairs += 1
         left += 1
         right += 1
      elif weights[left] + weights[right] < target:
         right += 1
      else:
         left += 1
      if pairs == k:
         return left - 1
   return -1

function solution(weights, target, k) {
   let n = weights.length;
   let left = 0, right = 0, count = 0, pairs = 0;
   while (right < n) {
      if (weights[left] + weights[right] === target) {
         pairs++;
         left++;
         right++;
      } else if (weights[left] + weights[right] < target) {
         right++;
      } else {
         left++;
      }
      if (pairs === k) return left - 1;
   }
   return -1;
}

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.

Minimum Conveyor Section for K Target Shipments Solution

Problem Statement

Input

Output

Input

Output

Input

Output

Input

Output

Constraints

More Two Pointers

Optimized Approach

Brute Force Approach

Step-by-Step Dry Run

Tested Solutions

Minimum Conveyor Section for K Target Shipments — Problem Statement & Solution Guide

Problem Description

DSA Pattern Breakdown

Core Theory — Why This Approach?

Interview Questions on This Problem

Examples

Constraints

Optimal Approach & Strategy

Brute Force Approach

Verified Code Solutions

Solve in Interative Editor