Beautiful Array

The beautiful array problem is solved by using a recursive approach. We can build a beautiful array for n using the beautiful array for n/2, and then apply some transformations to ensure the properties are maintained.

Here’s the code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def beautifulArray(self, n: int) -> List[int]:
        memo = {1: [1]}

        def construct(N):
            if N not in memo:
                odds = construct((N + 1) // 2)
                evens = construct(N // 2)
                memo[N] = [2 * x - 1 for x in odds] + [2 * x for x in evens]
            return memo[N]

        return construct(n)

Explanation

  1. Base Case: A beautiful array of length 1 is simply [1].

  2. Recursive Case: To construct a beautiful array of length n, we first construct beautiful arrays for (n + 1) // 2 (odds) and n // 2 (evens).

  3. Transformations:

    • For the odd part, we multiply the elements by 2 and subtract 1: 2 * x - 1.
    • For the even part, we simply multiply the elements by 2: 2 * x.

  4. Concatenation: We concatenate the odd and even parts to create the final beautiful array for n.

  5. Memoization: We use a memo dictionary to store the beautiful arrays for previously computed values, ensuring that we don’t recompute them.

Example

  • If n = 4, the function constructs beautiful arrays for 2 (odd) and 2 (even), applies the transformations, and concatenates them to obtain [2, 1, 4, 3].

Complexity Analysis

  • Time Complexity: (O(n \log n)), as we break down the problem into halves recursively and use (O(n)) time to build the result.
  • Space Complexity: (O(n \log n)), due to the recursion depth and memoization storage.