Practice/ServiceTitan/Leetcode 2766. Relocate Marbles

Leetcode 2766. Relocate Marbles

CodingMust

Problem

You are managing a warehouse where boxes are placed at various positions along a long conveyor belt. Each position is represented by an integer coordinate. Initially, you have boxes at specific positions given in the boxes array.

You need to perform a series of reorganization operations. Each operation is defined by two arrays: moveFrom and moveTo. For the i-th operation, you must take all boxes currently at position moveFrom[i] and relocate them to position moveTo[i].

After completing all operations in sequence, return a sorted array of all positions that contain at least one box.

Requirements

Process each move operation in the given order
When moving boxes from a position, all boxes at that position move together
If a position has no boxes, moving from it has no effect
Return the final occupied positions in ascending sorted order
Each position in the result should appear exactly once, regardless of how many boxes are there

Constraints

1 ≤ boxes.length ≤ 105
1 ≤ moveFrom.length ≤ 105
moveFrom.length == moveTo.length
1 ≤ boxes[i], moveFrom[i], moveTo[i] ≤ 109
All values in boxes are unique (initially no position has multiple boxes)
Time complexity should be efficient for the given constraints

Examples

Example 1:

` Input: boxes = [1, 3, 5], moveFrom = [1, 5], moveTo = [2, 6] Output: [2, 3, 6] Explanation:

Initially: positions [1, 3, 5] have boxes
After move 1→2: positions [2, 3, 5] have boxes
After move 5→6: positions [2, 3, 6] have boxes `

Example 2:

` Input: boxes = [1, 2, 3], moveFrom = [1, 2, 3], moveTo = [5, 5, 5] Output: [5] Explanation:

After move 1→5: positions [2, 3, 5] have boxes
After move 2→5: positions [3, 5] have boxes (boxes from 2 join those at 5)
After move 3→5: position [5] has boxes (all boxes converged) `

Example 3:

Input: boxes = [1], moveFrom = [1, 3, 5], moveTo = [3, 5, 7] Output: [7] Explanation: Single box moves through chain: 1→3→5→7