algoadvance

Leetcode 1470. Shuffle the Array

Problem Statement

You are given an array nums consisting of 2n elements in the form [x1, x2, ..., xn, y1, y2, ..., yn].

You need to 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]

The elements in the nums array should be rearranged such that elements from x and y are interleaved.

Clarifying Questions

  1. Input Validation: Can we assume that the input will always be valid as per the problem description?
  2. Data Range: Are there any constraints on the size of the elements in the array, or is it limited to the fact that the array will have 2n elements?
  3. Edge Cases: Are there any special cases we should consider, such as n being zero?

Strategy

  1. Input Validation: We assume the input is valid and nums has exactly 2n elements. If n is provided but not properly constrained, checks could be added.
  2. Array Formation: Initialize a result array of size 2n.
  3. Interleaving: Use a loop to place elements from each half of the input array into the result array alternately.

Code

Let’s implement the solution in Java:

public class Solution {
    public int[] shuffle(int[] nums, int n) {
        int[] result = new int[2 * n];
        int j = 0;
        
        for (int i = 0; i < n; i++) {
            result[j++] = nums[i];
            result[j++] = nums[i + n];
        }
        
        return result;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] nums = {2,5,1,3,4,7};
        int n = 3;
        int[] shuffled = sol.shuffle(nums, n);
        for (int num : shuffled) {
            System.out.print(num + " ");
        }
    }
}

Time Complexity

The time complexity for this solution is:

Explanation

  1. Initialization: We create an array result of length 2n to store the shuffled elements.
  2. Looping through the array:
    • For each index i from 0 to n-1, we place the ith element from the first half of nums and the ith element from the second half of nums alternately into result.
  3. Returning the result: The resultant array result is returned which has elements in the required shuffled order.

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