Conveyor Triplet Packaging
Learn this problem
GoogleINTERNPHONE SCREENProblem statement
Items arrive on a conveyor as the finite double array items. Package items into boxes of exactly three. A triple fits if the absolute difference between every pair of values is at most d.
Process anchors from left to right. For the earliest unpacked anchor index i, choose the lexicographically earliest pair of later unpacked indices (j, k) that forms a fitting triple. If no such pair exists, leave the anchor unpacked and continue.
Return completed boxes in anchor order. Values inside each box must retain their input-index order, and unpacked items are omitted. Do not sort the array or allocate an auxiliary collection to track consumed items. You may mutate items by replacing consumed entries with NaN; output storage does not count as auxiliary space.
Function
packageTriplets(items: double[], d: double) → double[][]Examples
Example 1
items = [1.0,11.0,12.0,13.0,2.0,3.0]d = 3.0return = [[1.0,2.0,3.0],[11.0,12.0,13.0]]Anchor 1.0 first fits with the later values 2.0 and 3.0. The earliest remaining anchor is then 11.0, which fits with 12.0 and 13.0.
Example 2
items = [0.0,10.0,11.0,12.0,1.0,2.0,20.0]d = 2.0return = [[0.0,1.0,2.0],[10.0,11.0,12.0]]The search keeps original indices rather than sorted value order. The final value 20.0 cannot complete a box and is omitted.
Constraints
0 <= items.length <= 150- Every entry of
itemsis a finite double. dis a finite double andd >= 0.