Skip to main content
Talentd

Shuffle the Array - Solution & Explanation

EasyArray14 min readAsked at: Amazon, Microsoft, Meta +3
Practice this problem

Problem Statement

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 <= 500
  • nums.length == 2n
  • 1 <= nums[i] <= 10^3

Approach Overview

Problem 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.

Approach 1: Two-Pointer Technique

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: In-place Reordering

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 3: Simulation

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.

Code

PythonJavaC++GoTypeScriptRustC

Python

Java

C++

Go

TypeScript

Rust

C

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Two-Pointer Technique

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.

In-place Reordering

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.

Simulation—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Two-Pointer TechniqueO(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.

Video Solution

Shuffle the Array (Constant Space) - Leetcode 1470 - Python • NeetCodeIO • 25,328 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Shuffle the Array easy or hard?
Shuffle the Array is classified as an Easy problem on LeetCode with a very high acceptance rate. The task mainly checks whether you can recognize a simple indexing pattern and implement an O(n) array traversal.
Shuffle the Array Python/Java solution
In Python or Java, the typical implementation uses two pointers and a result array. Iterate i from 0 to n-1 and append nums[i] followed by nums[i+n]. The logic is identical across languages and runs in O(n) time.
How to solve Shuffle the Array in O(n)?
Iterate through the first half of the array while pairing elements with the second half. For every index i from 0 to n-1, append nums[i] and nums[i+n] to the result. This processes all elements exactly once, giving O(n) time complexity.
What is the best approach for Shuffle the Array?
The two-pointer technique is the best and most readable approach. Start one pointer at index 0 and another at index n, then append elements alternately to a new array. This runs in O(n) time with O(n) extra space and directly matches the required output structure.
Is Shuffle the Array asked at Google/Amazon/Meta?
Shuffle the Array is a common beginner-level array problem seen in coding practice and early interview rounds. Variations of array interleaving or index mapping appear in interviews at companies like Amazon and Meta when testing basic array manipulation skills.
What data structure is used in Shuffle the Array?
The problem primarily uses arrays. Most solutions rely on sequential traversal of the array, sometimes combined with the two-pointer pattern or bit/number encoding techniques for in-place transformations.
What is the time complexity of Shuffle the Array?
Both common solutions run in O(n) time because each element is processed once. The standard two-pointer solution uses O(n) extra space for the result array, while the in-place encoding method reduces auxiliary space to O(1).

Ready to solve this problem?

Practice Shuffle the Array with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays