# 932. Beautiful Array

• Time: $O(n\log n)$
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 class Solution { public: vector beautifulArray(int n) { vector A(n); iota(begin(A), end(A), 1); divide(A, 0, n - 1, 1); return A; } private: void divide(vector& A, int l, int r, int mask) { if (l >= r) return; const int m = partition(A, l, r, mask); divide(A, l, m, mask << 1); divide(A, m + 1, r, mask << 1); } int partition(vector& A, int l, int r, int mask) { int nextSwapped = l; for (int i = l; i <= r; ++i) if (A[i] & mask) swap(A[i], A[nextSwapped++]); return nextSwapped - 1; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 class Solution { public int[] beautifulArray(int n) { int[] A = new int[n]; for (int i = 0; i < n; ++i) A[i] = i + 1; divide(A, 0, n - 1, 1); return A; } private void divide(int[] A, int l, int r, int mask) { if (l >= r) return; final int m = partition(A, l, r, mask); divide(A, l, m, mask << 1); divide(A, m + 1, r, mask << 1); } private int partition(int[] A, int l, int r, int mask) { int nextSwapped = l; for (int i = l; i <= r; ++i) if ((A[i] & mask) > 0) swap(A, i, nextSwapped++); return nextSwapped - 1; } private void swap(int[] A, int i, int j) { final int temp = A[i]; A[i] = A[j]; A[j] = temp; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 class Solution: def beautifulArray(self, n: int) -> List[int]: A = [i for i in range(1, n + 1)] def partition(l: int, r: int, mask: int) -> int: nextSwapped = l for i in range(l, r + 1): if A[i] & mask: A[i], A[nextSwapped] = A[nextSwapped], A[i] nextSwapped += 1 return nextSwapped - 1 def divide(l: int, r: int, mask: int) -> None: if l >= r: return m = partition(l, r, mask) divide(l, m, mask << 1) divide(m + 1, r, mask << 1) divide(0, n - 1, 1) return A