Shuffle the Array

This morning talking with one of my sons on Skype, I mentioned an article which I rewetted titled “China’s push to control Americans’ health care future”. My wife and I used to watch 60 Minutes every Sunday evening. About a couple years ago we stopped watching TV. It appeared to us that there was not much to watch. I liked the article. I agree with the points presented. To me the best part is the moneys offered to several states in the USA for a Chinese company to be allowed to offer COVID-19 services. My question is:  Where are the funds coming from? Stop for a moment and think about it… OK, now let’s move to a different subject.

Then the pandemic came. With it we started watching more content from Amazon Prime, Netflix and YouTube. In the past year it seems that two or three times Netflix has increased the price for their base tier by $1 each time. Yesterday I read the article “Why I’m canceling Netflix in 2021” which provides some reasons why you should be dropping Netflix. My wife and I seem to always watch YouTube and in addition Netflix or Amazon Prime. In these days we are favoring movies from Amazon Prime. They seem to have a larger and better selection and the service is part of Amazon Prime.

The main subject for this post is LeetCode 1470. Shuffle the Array problem. Apparently this is the warm up for another problem which I will tackle on my next post.

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].

Constraints:

o 1 <= n <= 500
o nums.length == 2n
o 1 <= nums[i] <= 10^3

We are given an int[] of numbers. We need to return an array in which every two entries represent a pair of numbers selected from the original array in a specific order.

    public int[] shuffle(int[] nums, int n) {
        
    }

The signature for the required method in Java indicates that we receive as arguments an array of integers and a number which contains the number of pairs we will generate.

I will be solving the problem on my Windows 10 machine using the VSCode IDE and the Java programming language. It is simpler to solve the problem directly on the LeetCode web site using the provided IDE. I desire to keep the solution in an environment that I can execute at my convenience. Because of this, I will have to generate a test scaffolding.

2,5,1,3,4,7
3
main <<< nums: [2, 5, 1, 3, 4, 7]
main <<<    n: 3
main <<< output: [2, 3, 5, 4, 1, 7]


1,2,3,4,4,3,2,1
4
main <<< nums: [1, 2, 3, 4, 4, 3, 2, 1]
main <<<    n: 4
main <<< output: [1, 4, 2, 3, 3, 2, 4, 1]


1,1,2,2
2
main <<< nums: [1, 1, 2, 2]
main <<<    n: 2
main <<< output: [1, 2, 1, 2]


1,2
1
main <<< nums: [1, 2]
main <<<    n: 1
main <<< output: [1, 2]

The screen capture shows a set of test cases provided by LeetCode. Our test program seems to read the two input lines, assign the values to an int[] and an int variable and display them to verify that all is well so far.

Our test code appears to process the arguments and return the result. The result then displayed.

    /**
     * Test scaffolding
     * 
     * @throws IOException
     */
    public static void main(String[] args) throws IOException {
        
        // **** open buffered reader ****
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // **** read int[] ****
        int[] nums = Arrays.stream(br.readLine().trim().split(","))
                                .mapToInt(Integer::parseInt)
                                .toArray();

        // **** read number of pairs ****
        int n = Integer.parseInt(br.readLine().trim());

        // **** close buffered reader ****
        br.close();

        // ???? ????
        System.out.println("main <<< nums: " + Arrays.toString(nums));
        System.out.println("main <<<    n: " + n);

        // **** process int[] and display result ****
        System.out.println("main <<< output: " + Arrays.toString(shuffle(nums, n)));
    }

Our test scaffolding seems to match the previous description. Not much to add.

    /**
     * O(n)
     * 
     * Runtime: 0 ms, faster than 100.00% of Java online submissions.
     * Memory Usage: 42.8 MB, less than 5.65% of Java online submissions.
     */
    static int[] shuffle(int[] nums, int n) {

        // **** sanity check(s) ****
        if (n == 1)
            return nums;

        // **** initialization ****
        int[] arr = new int[n * 2];

        // **** traverse half of the elements in the array O(n)****
        for (int i = 0, j = n, k = 0; i < n; i++, j++, k += 2) {
            arr[k]      = nums[i];
            arr[k + 1]  = nums[j];
        }

        // **** ****
        return arr;
    }

Our method of interest starts by performing a sanity check. It then allocates an output array.

The loop moves the values from the nums to the arr array. This is performed in O(n) time. The resulting array is returned.

We could have used the input array and directly swap values. That would have modified the input array. In general you do not want to induce side effects in a program. I would not consider modifying the input array an issue in this scenario.

In addition, we could have used a single variable and with different offsets and conditions we could have achieved the expected results. This approach appears to be simple and easy to understand and maintain. That said, in this case once the code is accepted by LeetCode, no additional maintenance is expected.

Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.

If you have comments or questions regarding this, or any other post in this blog, or if you would like for me to help out with any phase in the SDLC (Software Development Life Cycle) of a project associated with a product or service, please do not hesitate and leave me a note below. If you prefer, send me a private e-mail message. I will reply as soon as possible.

Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer toolset.

One last thing, many thanks to all 6,276 subscribers to this blog!!!

Keep safe during the COVID-19 pandemic and help restart the world economy. I believe we can all see the light at the end of the tunnel.

Regards;

John

john.canessa@gmail.com

Leave a Reply

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.