LeetCode Problem 1470

Difficulty: 🟢 Easy
Topics: Array

Solution

LeetCode 1470 - Shuffle the Array

Problem Understanding

The problem gives us an array nums with exactly 2n elements. The structure of the array is guaranteed to follow a very specific pattern:

[x1, x2, ..., xn, y1, y2, ..., yn]

This means the first half of the array contains all the x values, and the second half contains all the y values.

Our task is to rearrange the array into the following format:

[x1, y1, x2, y2, ..., xn, yn]

In other words, we must interleave the two halves of the array. We take one element from the first half, then one element from the second half, repeating this process until all elements are used.

For example, if:

nums = [2,5,1,3,4,7]
n = 3

then:

First half  = [2,5,1]
Second half = [3,4,7]

Interleaving them produces:

[2,3,5,4,1,7]

The constraints are relatively small:

• 1 <= n <= 500
• nums.length == 2n
• 1 <= nums[i] <= 1000

Since the maximum array size is only 1000, even less efficient solutions would still run comfortably within limits. However, the goal is still to design a clean and efficient algorithm.

An important observation is that the input format is always valid. The problem guarantees that:

• The array length is exactly 2n
• The first half and second half each contain exactly n elements
• There are no malformed inputs

This removes the need for defensive validation logic.

Potential edge cases include very small arrays such as:

nums = [1,2]
n = 1

where there is only one pair to interleave.

Another possible source of bugs is index handling. Since we access both halves simultaneously, incorrect indexing can easily produce off-by-one errors.

Duplicate values are also important to consider. The algorithm must preserve order exactly, even when numbers repeat.

Approaches

Brute Force Approach

A brute force solution would explicitly separate the array into two temporary arrays:

• One array for the first half
• One array for the second half

After splitting, we could iterate through both arrays simultaneously and append elements alternately into a result array.

This approach is straightforward and easy to understand. Since the problem size is small, it performs perfectly fine within constraints.

However, this solution uses unnecessary extra memory because we create additional arrays to store both halves separately before constructing the final answer.

Optimal Approach

The key observation is that we do not actually need to split the array into separate structures.

The first half already starts at index 0, and the second half already starts at index n.

This means:

• x_i is located at nums[i]
• y_i is located at nums[i + n]

We can therefore iterate from 0 to n - 1 and directly append:

nums[i]
nums[i + n]

to the result array.

This avoids unnecessary intermediate arrays and keeps the implementation concise and efficient.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(n)	Splits the array into two temporary arrays before merging
Optimal	O(n)	O(n)	Directly interleaves elements from the two halves

Algorithm Walkthrough

1. Create an empty result array that will store the shuffled sequence.
2. Iterate through the indices from 0 to n - 1. Each iteration corresponds to one pair of elements that should appear together in the output.
3. For the current index i, access the corresponding element from the first half using nums[i]. This represents x_i.
4. Access the matching element from the second half using nums[i + n]. This represents y_i.
5. Append both elements to the result array in order:

• First append nums[i]
• Then append nums[i + n]

6. Continue until all pairs have been processed.
7. Return the completed result array.

Why it works

The input array is guaranteed to contain exactly two consecutive halves of equal length. For every valid index i:

• nums[i] corresponds to the next element from the first half
• nums[i + n] corresponds to the matching element from the second half

By appending these two values together during every iteration, we exactly reproduce the required interleaving order:

[x1, y1, x2, y2, ..., xn, yn]

Because every element is processed once and inserted in the correct relative order, the algorithm always produces the correct output.

Python Solution

from typing import List

class Solution:
    def shuffle(self, nums: List[int], n: int) -> List[int]:
        shuffled = []

        for i in range(n):
            shuffled.append(nums[i])
            shuffled.append(nums[i + n])

        return shuffled

The implementation begins by creating an empty list named shuffled that will hold the final reordered array.

The loop runs exactly n times because there are n pairs to process. During each iteration:

• nums[i] retrieves the next element from the first half
• nums[i + n] retrieves the corresponding element from the second half

Both values are appended immediately to preserve the required ordering.

After all pairs are processed, the completed shuffled array is returned.

The implementation directly mirrors the algorithm described earlier, making it easy to verify for correctness.

Go Solution

func shuffle(nums []int, n int) []int {
    shuffled := make([]int, 0, 2*n)

    for i := 0; i < n; i++ {
        shuffled = append(shuffled, nums[i])
        shuffled = append(shuffled, nums[i+n])
    }

    return shuffled
}

The Go implementation follows the same logic as the Python version.

One notable difference is the use of:

make([]int, 0, 2*n)

This preallocates capacity for the result slice, which avoids unnecessary reallocations while appending elements.

Go slices dynamically grow as needed, but preallocating the expected size is more efficient.

There are no concerns about integer overflow because the constraints are very small.

The function also handles empty-like behavior naturally, although the constraints guarantee at least one pair exists.

Worked Examples

Example 1

Input:

nums = [2,5,1,3,4,7]
n = 3

Initial structure:

First half  = [2,5,1]
Second half = [3,4,7]

i	nums[i]	nums[i+n]	Result
0	2	3	[2,3]
1	5	4	[2,3,5,4]
2	1	7	[2,3,5,4,1,7]

Final output:

[2,3,5,4,1,7]

Example 2

Input:

nums = [1,2,3,4,4,3,2,1]
n = 4

Initial structure:

First half  = [1,2,3,4]
Second half = [4,3,2,1]

i	nums[i]	nums[i+n]	Result
0	1	4	[1,4]
1	2	3	[1,4,2,3]
2	3	2	[1,4,2,3,3,2]
3	4	1	[1,4,2,3,3,2,4,1]

Final output:

[1,4,2,3,3,2,4,1]

Example 3

Input:

nums = [1,1,2,2]
n = 2

Initial structure:

First half  = [1,1]
Second half = [2,2]

i	nums[i]	nums[i+n]	Result
0	1	2	[1,2]
1	1	2	[1,2,1,2]

Final output:

[1,2,1,2]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	We process each pair exactly once
Space	O(n)	The output array stores 2n elements

The algorithm performs a single linear pass through the array. Each iteration appends two elements to the result array, resulting in overall linear time complexity.

The extra space complexity is also linear because the output array itself requires storage proportional to the input size.

Test Cases

from typing import List

class Solution:
    def shuffle(self, nums: List[int], n: int) -> List[int]:
        shuffled = []

        for i in range(n):
            shuffled.append(nums[i])
            shuffled.append(nums[i + n])

        return shuffled

solution = Solution()

# Example 1
assert solution.shuffle([2,5,1,3,4,7], 3) == [2,3,5,4,1,7]

# Example 2
assert solution.shuffle([1,2,3,4,4,3,2,1], 4) == [1,4,2,3,3,2,4,1]

# Example 3
assert solution.shuffle([1,1,2,2], 2) == [1,2,1,2]

# Smallest valid input
assert solution.shuffle([1,2], 1) == [1,2]

# Duplicate values everywhere
assert solution.shuffle([5,5,5,5], 2) == [5,5,5,5]

# Increasing sequence
assert solution.shuffle([1,2,3,4,5,6], 3) == [1,4,2,5,3,6]

# All elements identical
assert solution.shuffle([7,7,7,7,7,7], 3) == [7,7,7,7,7,7]

# Maximum reasonable size pattern
large_input = list(range(1, 1001))
expected = []

n = 500

for i in range(n):
    expected.append(large_input[i])
    expected.append(large_input[i + n])

assert solution.shuffle(large_input, n) == expected

Test Summary

Test	Why
[2,5,1,3,4,7]	Verifies the primary example
[1,2,3,4,4,3,2,1]	Tests larger interleaving
[1,1,2,2]	Verifies duplicate handling
[1,2]	Smallest valid input
[5,5,5,5]	Ensures duplicates preserve order
Increasing sequence	Verifies index correctness
All identical values	Confirms stability with repeated numbers
Large input of size 1000	Stress test near maximum constraints

Edge Cases

One important edge case is the smallest valid input size:

nums = [1,2]
n = 1

This case is useful because many indexing mistakes become obvious when only a single pair exists. The implementation handles this naturally because the loop runs exactly once and appends one element from each half.

Another important edge case involves duplicate values:

nums = [5,5,5,5]

When all numbers are identical, it becomes impossible to visually distinguish whether elements were reordered correctly. Some incorrect implementations may accidentally skip or duplicate elements. Since this algorithm strictly processes indices in order, duplicates are handled safely and correctly.

A third edge case is the maximum allowed input size. With n = 500, the array contains 1000 elements. Inefficient algorithms with excessive nested loops or repeated insertions could become unnecessarily slow. The current implementation performs only a single linear traversal, so it remains efficient even at maximum input size.

Another subtle edge case involves preserving order exactly. Consider:

nums = [1,2,3,4,5,6]

The output must be:

[1,4,2,5,3,6]

An incorrect indexing formula could easily produce:

[1,4,2,6,3,5]

or another invalid ordering. By consistently pairing nums[i] with nums[i+n], the implementation guarantees correct alignment between the two halves.