algoadvance

Leetcode 1470. Shuffle the Array

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:

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

Input: nums = [1,2,3,4,4,3,2,1], n = 4
Output: [1,4,2,3,3,2,4,1]

Input: nums = [1,1,2,2], n = 2
Output: [1,2,1,2]

Clarifying Questions

1. Will the array always have an even number of elements?
   • Yes. The array is guaranteed to have 2n elements.
2. What are the possible values of x and y in the array?
   • x and y are integers and are within the bounds given by the problem constraints.
3. Is it required to shuffle the array in-place?
   • No, we can create a new array to hold the shuffled values.

Strategy

1. Initialize a new array to hold the shuffled result.
2. Iterate through the first half and the second half of the given array simultaneously.
3. Append elements from the first half and second half alternately to the new array.
4. Return the new array.

Code

#include <vector>
#include <iostream>

using namespace std;

vector<int> shuffle(vector<int>& nums, int n) {
    vector<int> result(2 * n);  // Initialize result array with size 2n
    
    for (int i = 0; i < n; ++i) {
        result[2 * i] = nums[i];  // Add element from the first half
        result[2 * i + 1] = nums[n + i];  // Add element from the second half
    }
    
    return result;
}

// Driver code to test the function
int main() {
    vector<int> nums1 = {2, 5, 1, 3, 4, 7};
    int n1 = 3;
    vector<int> result1 = shuffle(nums1, n1);
    for (int num : result1) {
        cout << num << " ";
    }
    cout << endl;
    
    vector<int> nums2 = {1, 2, 3, 4, 4, 3, 2, 1};
    int n2 = 4;
    vector<int> result2 = shuffle(nums2, n2);
    for (int num : result2) {
        cout << num << " ";
    }
    cout << endl;
    
    return 0;
}

Time Complexity

• The time complexity of this approach is O(n) because we iterate through the array once, where n is the half-length of the array nums (or alternatively, 2n operations for an array of size 2n).
• The space complexity is also O(n) due to the additional space used to store the result array of size 2n.

By following this strategy, we can efficiently shuffle the array as required by the problem statement.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?