#1470
Shuffle the Array
Easy Index arithmetic
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
The array holds x1..xn followed by y1..yn. Return it interleaved as x1, y1, x2, y2, ...
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: take the first half (x's) and the second half (y's) and zip them together: x1, y1, x2, y2…
Why this works: x_i lives at index i and y_i at index i + n; in the answer they go to 2i and 2i + 1.
Example: nums = [2, 5, 1, 3, 4, 7], n = 3
x = [2, 5, 1], y = [3, 4, 7]i=0 → ans[0]=2, ans[1]=3i=1 → ans[2]=5, ans[3]=4i=2 → ans[4]=1, ans[5]=7ans = [2, 3, 5, 4, 1, 7]
✦Hints open one at a time
x_i is at index i and y_i is at index i + n.
In the answer, x_i goes to 2i and y_i goes to 2i + 1.
↗Approach
Fill a new array using the index formulas. Getting comfortable with index arithmetic like 2i and 2i+1 pays off later in heaps and segment trees.
</>Solution (Java)
class Solution {
public int[] shuffle(int[] nums, int n) {
int[] ans = new int[2 * n];
for (int i = 0; i < n; i++) {
ans[2 * i] = nums[i]; // x_i
ans[2 * i + 1] = nums[i + n]; // y_i
}
return ans;
}
}!Common mistake
Looping i up to 2n instead of n, which reads past the first half.
Complexity
- Time: O(n).
- Space: O(n) for the output.
