932. Beautiful Array

Problem

An array nums of length n is beautiful if:

• nums is a permutation of the integers in the range [1, n].

• For every 0 <= i < j < n, there is no index k with i < k < j where 2 * nums[k] == nums[i] + nums[j].

Given the integer n, return **any *beautiful* array nums of length **n. There will be at least one valid answer for the given n.

  Example 1:

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

Example 2:

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

  Constraints:

• 1 <= n <= 1000

Solution (Java)

class Solution {
    private Map<Integer, int[]> memo;

    public int[] beautifulArray(int n) {
        memo = new HashMap<>();
        return helper(n);
    }

    private int[] helper(int n) {
        if (n == 1) {
            memo.put(1, new int[] {1});
            return new int[] {1};
        }
        if (memo.containsKey(n)) {
            return memo.get(n);
        }
        int mid = (n + 1) / 2;
        int[] left = helper(mid);
        int[] right = helper(n - mid);
        int[] rst = new int[n];
        for (int i = 0; i < mid; i++) {
            rst[i] = left[i] * 2 - 1;
        }
        for (int i = mid; i < n; i++) {
            rst[i] = right[i - mid] * 2;
        }
        memo.put(n, rst);
        return rst;
    }
}

Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).