Interleave Two Equal-Length Array Halves
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Other
### Problem
The array nums contains[x1,...,xn,y1,...,yn]. Return[x1,y1,x2,y2,...,xn,yn], keeping the relative order within both halves.
```cpp
class Solution {
public:
vector<int> shuffle(vector<int>& nums, int n);
};
```
### Examples
**Example 1:**
```text
Input: nums = [3,4,8,9], n = 2
Output: [3,8,4,9]
Explanation: Pair the first-half entries3,4 with the second-half entries8,9.
```
**Example 2:**
```text
Input: nums = [7,2], n = 1
Output: [7,2]
Explanation: With one pair, the order already matches the required form.
```
### Constraints
- `1 <= n <= 500` and nums.length equals 2*n.
- `1 <= nums[i] <= 1000`.
### Contract considerations
This is deterministic interleaving, despite the word shuffle in the original title.
```hint Read the boundary condition
Check that every original occurrence appears once and that each half retains its relative order, including repeated values.
```
### Boundary reminders
This is deterministic interleaving, despite the word shuffle in the original title.
Overview: Interleave Two Equal-Length Array Halves. The array nums contains[x1,...,xn,y1,...,yn]. Return[x1,y1,x2,y2,...,xn,yn], keeping the relative order within both halves.