Off-by-one on range boundaries
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Move from brute-force thinking to an efficient approach using array strategy.
You are given a 0-indexed integer array nums representing the initial positions of some marbles. You are also given two 0-indexed integer arrays moveFrom and moveTo of equal length.
Throughout moveFrom.length steps, you will change the positions of the marbles. On the ith step, you will move all marbles at position moveFrom[i] to position moveTo[i].
After completing all the steps, return the sorted list of occupied positions.
Notes:
Example 1:
Input: nums = [1,6,7,8], moveFrom = [1,7,2], moveTo = [2,9,5] Output: [5,6,8,9] Explanation: Initially, the marbles are at positions 1,6,7,8. At the i = 0th step, we move the marbles at position 1 to position 2. Then, positions 2,6,7,8 are occupied. At the i = 1st step, we move the marbles at position 7 to position 9. Then, positions 2,6,8,9 are occupied. At the i = 2nd step, we move the marbles at position 2 to position 5. Then, positions 5,6,8,9 are occupied. At the end, the final positions containing at least one marbles are [5,6,8,9].
Example 2:
Input: nums = [1,1,3,3], moveFrom = [1,3], moveTo = [2,2] Output: [2] Explanation: Initially, the marbles are at positions [1,1,3,3]. At the i = 0th step, we move all the marbles at position 1 to position 2. Then, the marbles are at positions [2,2,3,3]. At the i = 1st step, we move all the marbles at position 3 to position 2. Then, the marbles are at positions [2,2,2,2]. Since 2 is the only occupied position, we return [2].
Constraints:
1 <= nums.length <= 1051 <= moveFrom.length <= 105moveFrom.length == moveTo.length1 <= nums[i], moveFrom[i], moveTo[i] <= 109moveFrom[i] at the moment we want to apply the ith move.Problem summary: You are given a 0-indexed integer array nums representing the initial positions of some marbles. You are also given two 0-indexed integer arrays moveFrom and moveTo of equal length. Throughout moveFrom.length steps, you will change the positions of the marbles. On the ith step, you will move all marbles at position moveFrom[i] to position moveTo[i]. After completing all the steps, return the sorted list of occupied positions. Notes: We call a position occupied if there is at least one marble in that position. There may be multiple marbles in a single position.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Array · Hash Map
[1,6,7,8] [1,7,2] [2,9,5]
[1,1,3,3] [1,3] [2,2]
Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #2766: Relocate Marbles
class Solution {
public List<Integer> relocateMarbles(int[] nums, int[] moveFrom, int[] moveTo) {
Set<Integer> pos = new HashSet<>();
for (int x : nums) {
pos.add(x);
}
for (int i = 0; i < moveFrom.length; ++i) {
pos.remove(moveFrom[i]);
pos.add(moveTo[i]);
}
List<Integer> ans = new ArrayList<>(pos);
ans.sort((a, b) -> a - b);
return ans;
}
}
// Accepted solution for LeetCode #2766: Relocate Marbles
func relocateMarbles(nums []int, moveFrom []int, moveTo []int) (ans []int) {
pos := map[int]bool{}
for _, x := range nums {
pos[x] = true
}
for i, f := range moveFrom {
t := moveTo[i]
pos[f] = false
pos[t] = true
}
for x, ok := range pos {
if ok {
ans = append(ans, x)
}
}
sort.Ints(ans)
return
}
# Accepted solution for LeetCode #2766: Relocate Marbles
class Solution:
def relocateMarbles(
self, nums: List[int], moveFrom: List[int], moveTo: List[int]
) -> List[int]:
pos = set(nums)
for f, t in zip(moveFrom, moveTo):
pos.remove(f)
pos.add(t)
return sorted(pos)
// Accepted solution for LeetCode #2766: Relocate Marbles
// Rust example auto-generated from java reference.
// Replace the signature and local types with the exact LeetCode harness for this problem.
impl Solution {
pub fn rust_example() {
// Port the logic from the reference block below.
}
}
// Reference (java):
// // Accepted solution for LeetCode #2766: Relocate Marbles
// class Solution {
// public List<Integer> relocateMarbles(int[] nums, int[] moveFrom, int[] moveTo) {
// Set<Integer> pos = new HashSet<>();
// for (int x : nums) {
// pos.add(x);
// }
// for (int i = 0; i < moveFrom.length; ++i) {
// pos.remove(moveFrom[i]);
// pos.add(moveTo[i]);
// }
// List<Integer> ans = new ArrayList<>(pos);
// ans.sort((a, b) -> a - b);
// return ans;
// }
// }
// Accepted solution for LeetCode #2766: Relocate Marbles
function relocateMarbles(nums: number[], moveFrom: number[], moveTo: number[]): number[] {
const pos: Set<number> = new Set(nums);
for (let i = 0; i < moveFrom.length; i++) {
pos.delete(moveFrom[i]);
pos.add(moveTo[i]);
}
return [...pos].sort((a, b) => a - b);
}
Use this to step through a reusable interview workflow for this problem.
Two nested loops check every pair or subarray. The outer loop fixes a starting point, the inner loop extends or searches. For n elements this gives up to n²/2 operations. No extra space, but the quadratic time is prohibitive for large inputs.
Most array problems have an O(n²) brute force (nested loops) and an O(n) optimal (single pass with clever state tracking). The key is identifying what information to maintain as you scan: a running max, a prefix sum, a hash map of seen values, or two pointers.
Review these before coding to avoid predictable interview regressions.
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Wrong move: Zero-count keys stay in map and break distinct/count constraints.
Usually fails on: Window/map size checks are consistently off by one.
Fix: Delete keys when count reaches zero.