Recover The Original Array - Leetcode Solution

Problem Statement:

You are given an array of integers nums with even length. Your task is to redistribute the elements in the array such that every i-th element (0-indexed) becomes nums[i] = nums[i * 2 + 1] and nums[i + n] = nums[i * 2] for all i in [0, n - 1] (n = nums.length / 2).

You can return any answer array that satisfies this condition.

Example: Input: nums = [1,2,3,4,5,6] Output: [1,3,5,2,4,6] Explanation: The given array becomes [1,6,2,5,3,4] after rearranging it as required.

Solution:

To solve the problem let us do the following:

• First we will sort the given array.
• Next we create the resultant array with the same length as nums.
• Then we place the larger half of the sorted nums array in the odd positions of the resultant array.
• Similarly, the smaller half of the sorted nums array is placed in the even positions of the resultant array.
• The resultant array obtained will be such that every i-th element (0-indexed) becomes nums[i] = nums[i * 2 + 1] and nums[i + n] = nums[i * 2] for all i in [0, n - 1] (n = nums.length / 2).
• Finally, we return the resultant array.

Let us write the code for the same:

class Solution {
    public int[] recoverArray(int[] nums) {
        int n = nums.length/2;
        Arrays.sort(nums);
        int[] res = new int[nums.length];
        int even = 0, odd = 1, i = 0, j = n;
        while(i<n && j<nums.length){
            res[even] = nums[i];
            even += 2;
            i++;
            res[odd] = nums[j];
            odd += 2;
            j++;
        }
        return res;
    }
}

Time Complexity: Sorting takes O(n log n) time. The loop runs n / 2 times. So the final time complexity is O(n log n).

Space Complexity: We use an additional array of size n. So space complexity is O(n).

1