Log inSign up
mediumLeetCodeNot Started

Beautiful Array

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Arrays
Solve on LeetCode
Lesson

Problem Statement

An array nums of length n is beautiful if: 1. nums is a permutation of the integers in the range [1, n]. 2. For every 0 <= i < j < n, there is no index k with i < k < j such that 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 · Small N = 4:

Input: n = 4
Output: [1, 3, 2, 4]
Explanation: For any pair (i, j), the average never falls strictly between them.

Example 2 · N = 5:

Input: n = 5
Output: [1, 5, 3, 2, 4]
Explanation: Valid permutation of [1, 2, 3, 4, 5] with no arithmetic progression between any three elements.

Example 3 · Base Case N = 1:

Input: n = 1
Output: [1]
Explanation: Array of length 1 is trivially beautiful.

Constraints:

  • 1 <= n <= 1000

Prerequisites

Before attempting this problem, you should be comfortable with:

  • Parity properties — odd + even = odd, 2 * integer = even
  • Divide and Conquer recursion
  • Linear transformation invariants (affine maps)

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand the parity invariant: odd + even != even.
  • Master the affine transformation preservation: (2*x - 1) and (2*x).
  • Transition from recursive divide-and-conquer to bottom-up expansion.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Input structure involves an array or contiguous sequence with constraints on element relationships.
  • Optimal solution requires avoiding O(N2) exhaustive searches through state tracking or pointers.
  • Subproblem exhibits optimal substructure or monotonicity enabling linear or logarithmic processing.

Algorithmic Decision Tree:

  • If the array is sorted or can be sorted without violating problem requirements, evaluate Two Pointers or Binary Search.
  • If tracking contiguous subsegments with monotone expansion/shrinkage, apply Sliding Window.
  • If frequency or complement lookups are required in O(1) time, use a Hash Map or Frequency Array.

Connected Patterns:

Divide and Conquer (Merge Sort)Van der Waerden Number / No 3-AP Permutation

1. Permutation Verification (Brute Force)

Intuition

Generate permutations and check all (i, k, j) triplets for the forbidden arithmetic mean condition.

Algorithm

  1. 1. Create array [1, 2, ..., N].
  2. 2. For each permutation of the array: - Check all triplets i < k < j: - If 2*nums[k] == nums[i] + nums[j], fail. - If no triplet fails, return permutation.

Brute Force All Permutations Arithmetic Check

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [1, 2, 3, 4]
Current operationSTEP 1 OF 6
Phase 1 — Step 1: Step 1: Permutation [1, 2, 3, 4] contains arithmetic progression 1, 2, 3 because 2 2 == 1 + 3
Visual state
Values and pointers at this exact step
array
S
1
2
3
4
0
↑ i=0 (val 1)
1
↑ k=1 (val 2)
2
↑ j=2 (val 3)
3
Variables at this step
Permutation
[1, 2, 3, 4]
Violating Triplet
(1, 2, 3)
Valid
NO
Check / comparison
Test permutation [1, 2, 3, 4]. Check triplet (i=0, k=1, j=2): 2 * nums[k] = 2*2 = 4. nums[i]+nums[j] = 1+3 = 4.
Decision / next transition
2 * nums[k] == nums[i] + nums[j] (4 == 4). NOT BEAUTIFUL!
Why this step matters

Phase 1 — Step 1: Step 1: Permutation [1, 2, 3, 4] contains arithmetic progression 1, 2, 3 because 2 * 2 == 1 + 3. Fails the beauty condition.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <numeric>
4#include <algorithm>
5using namespace std;
6
7// Brute Force Approach: Permutation Verification
8bool isValid(const vector<int>& nums) {
9 int n = nums.size();
10 for (int i = 0; i < n; i++) {
11 for (int k = i + 1; k < n; k++) {
12 for (int j = k + 1; j < n; j++) {
13 if (2 * nums[k] == nums[i] + nums[j]) {
14 return false;
15 }
16 }
17 }
18 }
19 return true;
20}
21
22vector<int> beautifulArray(int n) {
23 vector<int> nums(n);
24 iota(nums.begin(), nums.end(), 1);
25 do {
26 if (isValid(nums)) return nums;
27 } while (next_permutation(nums.begin(), nums.end()));
28 return {};
29}
30
31int main() {
32 int n = 4;
33 vector<int> result = beautifulArray(n);
34 cout << "Output: [";
35 for (int i = 0; i < result.size(); i++) {
36 cout << result[i] << (i + 1 < result.size() ? ", " : "");
37 }
38 cout << "]" << endl;
39 return 0;
40}

Time & Space Complexity

  • Time complexity: O(N! * N^3) — There are N! permutations, and checking triplets takes O(N3) time.
  • Space complexity: O(N) — Array of size N.

Why Brute Force Doesn't Scale:

For N = 105, quadratic O(N2) approaches require ~1010 operations, exceeding the standard 1-second CPU budget.

The optimal approach processes N elements in a single or logarithmic pass, completing in under 10ms with minimal memory footprint.

2. Recursive Divide and Conquer (Better)

Intuition

Recursively construct odds from beautifulArray((n+1)/2) and evens from beautifulArray(n/2).

Algorithm

  1. 1. If n == 1, return [1].
  2. 2. Recursively get left = beautifulArray((n + 1) / 2).
  3. 3. Recursively get right = beautifulArray(n / 2).
  4. 4. Combine: ans = [2*x - 1 for x in left] + [2*x for x in right].
  5. 5. Return ans.

Top-Down Divide & Conquer (Odd/Even Split)

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [1, 3, 2, 4]
Current operationSTEP 1 OF 6
Phase 1 — Step 1: Step 1: If all odd numbers are placed before all even numbers, NO pair crossing the boundary can have nums[i] + nums[j] == 2 nums[k]
Visual state
Values and pointers at this exact step
array
S
1
3
2
4
0
↑ Goal: n=4
1
2
3
Variables at this step
n
4
Odds Branch
n=2
Evens Branch
n=2
Check / comparison
Mathematical Invariant: An odd plus an even is always ODD. But 2 * nums[k] is always EVEN.
Decision / next transition
Divide n=4 into Odds branch (n=2) and Evens branch (n=2).
Why this step matters

Phase 1 — Step 1: Step 1: If all odd numbers are placed before all even numbers, NO pair crossing the boundary can have nums[i] + nums[j] == 2 * nums[k]!

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <unordered_map>
4using namespace std;
5
6// Better Approach: Recursive Divide and Conquer
7unordered_map<int, vector<int>> memo;
8
9vector<int> beautifulArray(int n) {
10 if (memo.find(n) != memo.end()) return memo[n];
11 if (n == 1) return {1};
12
13 vector<int> ans;
14 for (int x : beautifulArray((n + 1) / 2)) {
15 ans.push_back(2 * x - 1);
16 }
17 for (int x : beautifulArray(n / 2)) {
18 ans.push_back(2 * x);
19 }
20
21 return memo[n] = ans;
22}
23
24int main() {
25 int n = 4;
26 vector<int> result = beautifulArray(n);
27 cout << "Output: [";
28 for (int i = 0; i < result.size(); i++) {
29 cout << result[i] << (i + 1 < result.size() ? ", " : "");
30 }
31 cout << "]" << endl;
32 return 0;
33}

Time & Space Complexity

  • Time complexity: O(N log N) — Recurrence T(N) = T(N/2) + T((N+1)/2) + O(N) gives O(N log N) total work.
  • Space complexity: O(N log N) — Memoization / recursion stack takes O(N log N) space.

3. Iterative Bottom-Up Expansion (Optimal)

Intuition

Start with [1] and expand iteratively: res = [2*x - 1 for x in res] + [2*x for x in res] filtering values <= N.

Algorithm

  1. 1. Initialize res = [1].
  2. 2. While res.length < n: - nextRes = [] - For x in res: if 2*x - 1 <= n: nextRes.push(2*x - 1) - For x in res: if 2*x <= n: nextRes.push(2*x) - res = nextRes.
  3. 3. Return res.

Iterative Bottom-Up Expansion from [1]

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [1, 3, 2, 4]
Current operationSTEP 1 OF 6
Phase 1 — Loop while reslength < 4: Step 1: Initialize bottom-up array res = [1]
Visual state
Values and pointers at this exact step
array
S
1
—
—
—
0
↑ res = [1]
1
2
3
Variables at this step
res
[1]
length
1
Target
4
Check / comparison
Start with base array res = [1]. Size = 1 < n (4).
Decision / next transition
Loop while res.length < 4.
Why this step matters

Phase 1 — Loop while reslength < 4: Step 1: Initialize bottom-up array res = [1]. We iteratively double the array until size reaches n.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3using namespace std;
4
5// Optimal Approach: Iterative Bottom-Up Expansion
6vector<int> beautifulArray(int n) {
7 vector<int> res = {1};
8 while (res.size() < n) {
9 vector<int> next;
10 // Add odd mappings
11 for (int x : res) {
12 if (2 * x - 1 <= n) next.push_back(2 * x - 1);
13 }
14 // Add even mappings
15 for (int x : res) {
16 if (2 * x <= n) next.push_back(2 * x);
17 }
18 res = next;
19 }
20 return res;
21}
22
23int main() {
24 int n = 5;
25 vector<int> result = beautifulArray(n);
26 cout << "Output: [";
27 for (int i = 0; i < result.size(); i++) {
28 cout << result[i] << (i + 1 < result.size() ? ", " : "");
29 }
30 cout << "]" << endl;
31 return 0;
32}

Time & Space Complexity

  • Time complexity: O(N) — Doubles array size at each iteration (1, 2, 4, 8... up to N). Total elements processed = 1 + 2 + 4 + ... + N = O(N).
  • Space complexity: O(N) — Requires O(N) memory for the output array.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — PermutationsO(N! * N^3)O(N)Generate all permutations and verify the 2*nums[k] condition for every triplet.N! combinations.
2.Better — Recursive Divide & ConquerO(N log N)O(N log N)Recursively build beautiful arrays of size (N+1)/2 (odds) and N/2 (evens) using memoization.Recursive call stack.
3.Optimal — Iterative Parity ExpansionOptimalO(N)O(N)Start with [1], iteratively generate odds (2*x - 1) and evens (2*x) filtering elements <= N.None; industry-standard optimal solution.

Common Pitfalls & Crucial Edge Cases

Off-by-One Errors

Incorrect boundary indexing when adjusting pointers or array slices.

Integer Overflow

Using 32-bit signed integer types when accumulative operations exceed 231 - 1 in C++/Java.

Unnecessary Memory Allocation

Allocating large auxiliary arrays or objects inside inner loops causing GC overhead.

Failing to Reset Loop State

Not re-initializing state variables or counters between iterations or subproblems.

Crucial Edge Cases to Validate:

  • N = 1: Base case returns [1].
  • N = 2: Returns [1, 2].
  • Odd N vs Even N: Correctly filtering > N values ensures exact length N.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Always state the brute force baseline before presenting the optimal solution to demonstrate structured problem solving.
  2. Explicitly verify boundary conditions (empty arrays, single elements, duplicates, extremes) out loud with the interviewer.
  3. Analyze both time and auxiliary space complexities clearly, explaining trade-offs between speed and memory allocation.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the optimal time and auxiliary space complexity for Beautiful Array?

2.Why is the brute force approach suboptimal for large inputs in Beautiful Array?

3.Which data structure or technique enables the optimal solution for Beautiful Array?

Back to DSA Sheet