Shuffle the Array - Complete Solution Guide

Shuffle the Array is LeetCode problem 1470, a Easy level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, c.

Problem Statement

Given the array nums consisting of 2n elements in the form [x 1 ,x 2 ,...,x n ,y 1 ,y 2 ,...,y n ] . Return the array in the form [x 1 ,y 1 ,x 2 ,y 2 ,...,x n ,y n ] . Example 1: Input: nums = [2,5,1,3,4,7], n = 3 Output: [2,3,5,4,1,7] Explanation: Since x 1 =2, x 2 =5, x 3 =1, y 1 =3, y 2 =4, y 3 =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 n

Detailed Explanation

The problem asks you to rearrange a given array `nums` of size `2n` into a new array. The input array has the format [x₁, x₂, ..., xₙ, y₁, y₂, ..., yₙ]. The goal is to create an output array with the format [x₁, y₁, x₂, y₂, ..., xₙ, yₙ]. Essentially, you're interleaving the first half of the array with the second half. The input `n` specifies the length of the first half of the array.

Solution Approach

The provided solutions use a straightforward iterative approach. They iterate `n` times. In each iteration, they take one element from the first half of the input array and one from the second half and place them sequentially in the output array. This process effectively interleaves the two halves of the input array, producing the desired output.

Step-by-Step Algorithm

1. Step 1: Create a new array `result` with the same size as the input array `nums` (2n).
2. Step 2: Iterate from `i = 0` to `n - 1`. In each iteration:
3. Step 3: Append `nums[i]` (from the first half) to the `result` array.
4. Step 4: Append `nums[i + n]` (from the second half) to the `result` array.
5. Step 5: Return the `result` array.

Key Insights

• Insight 1: The problem can be solved with a simple iteration through the input array, accessing elements from the beginning and the middle.
• Insight 2: No complex data structures are required. A new array of the same size as the input is sufficient.
• Insight 3: The solution directly translates into code, making it efficient and easy to implement in any programming language.

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(n)

Topics

This problem involves: Array.

Companies

Asked at: Zoho.