[LeetCode] Beautiful Array

Problem: For some fixed n, an array nums is beautiful if it is a permutation of the integers 1, 2, ..., n, such that:

For every i < j, there is no k with i < k < j such that nums[k] * 2 = nums[i] + nums[j].

Given n, return any beautiful array nums.  (It is guaranteed that one exists.)

Example:

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

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

Approach: Let's try to understand the condition:

i < k < j such that nums[k] * 2 = nums[i] + nums[j]

what it is saying that for every 1 <= k <= n - 2, there are no element in left of k and right of k such that the sum of those elements is equal to 2 * k. How we can ensure it? if we see closely:

2 * nums[k] is even for any nums[k].

so if we keep odd numbers to the left of k and even numbers to the right of k. We will be able to achieve it as sum of an even number and an odd number can't be even. We can achieve it by using divide and conquer approach; basically we first divide the array in two halves and then create the beautiful array of each half recursively and then concatenate theses two arrays(halves).

Let's see how we can do it? The shortest beautiful array is [1,3,2] or [3,1,2]. Right, how to get this array:

Here n is 3 so what we can do we can divid this into two halves:

• Number of odd numbers = (n + 1) / 2 = (3 + 1) / 2 = 2 so the first half is [1,2] for now.
• Number of even numbers = n / 2 = 3 / 2 = 1 so the second half is [1] for now.

There are some problems with these halves right, as both halves have 1 in it. Odd half has 2 and even half has 1. Let's see how to actually generate right halves:

• The odd numbers will be 2 * oddHalf[i] - 1 so the first half will become [2 * 1 - 1, 2 * 2 - 1] = [1,3]
• The even numbers will be 2 * evenHalf[i] so the second half will become [2 * 1] = [2]

Now we have generated these halves we can just concatenate these halves and it will become [1,3,2] which is our answer. Now that the approach is clear, here is how our algorithm looks like:

• DEF Solve(n):
• IF n == 1:
• RETURN [1]
• oddHalf = Solve((n + 1) / 2)
• evenHalf = Solve(n/2)
• result = []
• int writeIndex = 0
• FOR i = 0 TO length of oddHalf
• result[writeIndex] = 2 * oddHalf[i] - 1
• writeIndex = writeIndex + 1
• FOR i = 0 TO length of evenHalf
• result[writeIndex] = 2 * evenHalf[i]
• writeIndex = writeIndex + 1
• RETURN result

In the implementation I have just taken a hashmap and store the intermediate results in it so that we don't have to recalculate the result for same intermediate n and in that way we can save some time.

Implementation in C#:

    public int[] BeautifulArray(int n) 

    {

        Dictionary<int, int[]> resultDict = new Dictionary<int, int[]>();

        return this.SolveBeautifulArray(n, resultDict);

    }

    

    private int[] SolveBeautifulArray(int n, Dictionary<int, int[]> resultDict)

    {

        if (resultDict.ContainsKey(n))

        {

            return resultDict[n];

        }        

        int[] result = new int[n];

        if (n == 1)

        {

            result[0] = 1;

            resultDict.Add(1, result);

            return result;

        }

        int i = 0;

        // odd nums

        foreach (int x in this.SolveBeautifulArray((n + 1) / 2, resultDict))

        {

            result[i++] = 2 * x - 1;

        }

        // even nums

        foreach (int x in this.SolveBeautifulArray(n / 2, resultDict))

        {

            result[i++] = 2 * x;

        }

        resultDict.Add(n, result);        

        return result;

    }

Complexity: O(nlogn)