Given the array nums consisting of 2n elements in the form [x1,x2,...,xn,y1,y2,...,yn].
Return the array in the form [x1,y1,x2,y2,...,xn,yn].
Example 1:
Input: nums = [2,5,1,3,4,7], n = 3 Output: [2,3,5,4,1,7] Explanation: Since x1=2, x2=5, x3=1, y1=3, y2=4, y3=7 then the answer is [2,3,5,4,1,7].
Example 2:
Input: nums = [1,2,3,4,4,3,2,1], n = 4 Output: [1,4,2,3,3,2,4,1]
Example 3:
Input: nums = [1,1,2,2], n = 2 Output: [1,2,1,2]
Constraints:
1 <= n <= 500nums.length == 2n1 <= nums[i] <= 10^3Problem Overview: You’re given an array nums of length 2n. The first half contains x1, x2, ..., xn and the second half contains y1, y2, ..., yn. The task is to rearrange it into [x1, y1, x2, y2, ..., xn, yn]. The key observation: elements from the first half and second half must be interleaved in order.
Approach 1: Two-Pointer Technique (O(n) time, O(n) space)
This is the most direct solution. Maintain two pointers: one starting at index 0 for the x elements and another at index n for the y elements. Iterate while building a new result array. On each step, append nums[i] followed by nums[j], then increment both pointers. The logic mirrors the required output structure, making it easy to reason about. The algorithm scans the array once, so the time complexity is O(n), and it uses an additional array of size 2n, giving O(n) space complexity. This approach relies only on sequential iteration over an array and is typically the cleanest implementation.
Approach 2: In-place Reordering (O(n) time, O(1) space)
If extra memory is restricted, the array can be shuffled in place. The trick is to encode two values into a single integer temporarily. Since each number fits within a known bound, store both the original value and the future value using modular arithmetic or bit manipulation. For example, pack the new value into the higher bits while preserving the old value in the lower bits, then decode the final array in a second pass. This method still processes the array in linear time O(n) but avoids allocating a separate result array, achieving O(1) auxiliary space. The approach relies on careful index mapping and works well when practicing in-place manipulation problems in arrays or encoding tricks using bit manipulation.
Recommended for interviews: Interviewers usually expect the Two-Pointer Technique. It clearly demonstrates that you recognize the structure of the input and can construct the result in linear time. The in-place encoding solution is a useful follow-up when asked to optimize space complexity. Showing both approaches signals strong understanding of two-pointer patterns and array transformations.
This approach uses a two-pointer technique to shuffle the array. The first pointer starts at the beginning of the array and represents the x values. The second pointer starts at the middle of the array and represents the y values. By iterating over the array and adding elements from these two pointers alternately to a new list, we can achieve the desired shuffle.
This C solution uses a function shuffle that accepts pointers to the input array and output array, along with n (half the size of the array). It utilizes two pointers within a single loop to construct the resulting shuffled array.
Time Complexity: O(n), where n is half the length of the array. We iterate through the array once.
Space Complexity: O(n), for storing the shuffled result.
An alternate approach is to reorder the array in-place without using additional space. However, given the elements might need to be accessed multiple times, a good understanding of index manipulation and mathematics is required. The complexity to deduce the correct indices for swapping can increase the difficulty.
This C implementation performs in-place reordering by moving each y value to its correct position through a series of swaps.
Time Complexity: O(n^2) in the worst case as the array is shifted multiple times.
Space Complexity: O(1), as the shuffling is done in-place.
We traverse the indices i in the range [0, n). Each time, we take nums[i] and nums[i+n] and place them sequentially into the answer array.
After the traversal is complete, we return the answer array.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array nums.
| Approach | Complexity |
|---|---|
| Two-Pointer Technique | Time Complexity: O(n), where n is half the length of the array. We iterate through the array once. |
| In-place Reordering | Time Complexity: O(n^2) in the worst case as the array is shifted multiple times. |
| Simulation | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two-Pointer Technique | O(n) | O(n) | Best general solution. Simple, readable, and ideal for interviews. |
| In-place Reordering (Encoding Trick) | O(n) | O(1) | Useful when memory is constrained or when asked for constant space optimization. |
Shuffle the Array (Constant Space) - Leetcode 1470 - Python • NeetCodeIO • 24,006 views views
Watch 9 more video solutions →Practice Shuffle the Array with our built-in code editor and test cases.
Practice on FleetCode