Shuffle the Array - Video Solutions

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.