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^3This 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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
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.
| 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. |
Shuffle the Array (Constant Space) - Leetcode 1470 - Python • NeetCodeIO • 19,611 views views
Watch 9 more video solutions →Practice Shuffle the Array with our built-in code editor and test cases.
Practice on FleetCode