Beautiful Array: Divide and Conquer Construction

An array nums of length n is beautiful if for every 0 <= i < k < j < n, the condition 2 * nums[k] != nums[i] + nums[j] holds. In other words, no element in the array is the arithmetic mean of any two other elements that surround it. Given an integer n, return any beautiful array containing the integers 1 through n.

This is LeetCode 932: Beautiful Array. At first glance, the constraint seems hard to enforce globally. How do you arrange numbers so that no triple of positions ever forms an arithmetic progression? The answer lies in a clever divide and conquer construction.

Why the brute force fails

You might think about generating permutations and checking each one. For a permutation of length n, there are O(n^3) triples to check, and n! permutations to try. That blows up immediately. Even checking a single permutation in O(n^3) is fine, but generating valid ones by trial and error is not scalable. We need a constructive approach.

The key insight

The beautiful array has two properties that make divide and conquer work:

1. Multiplying every element by a constant preserves beauty. If 2 * A[k] != A[i] + A[j], then 2 * (c * A[k]) != c * A[i] + c * A[j] still holds (just multiply both sides by c).

2. Adding a constant to every element preserves beauty. If 2 * A[k] != A[i] + A[j], then 2 * (A[k] + d) != (A[i] + d) + (A[j] + d) simplifies to the same inequality (the d terms cancel).

These two properties mean you can transform a beautiful array and it stays beautiful. Now here is the crucial observation:

This means you only need to worry about violations within each half. And each half is itself a smaller beautiful array problem.

The divide and conquer construction

Given a beautiful array for [1..n], you can build it iteratively:

1. Start with [1]. A single element is trivially beautiful.
2. At each step, take the current array and produce two copies:
   • Odd positions: apply 2x - 1 to each element (maps to odd numbers)
   • Even positions: apply 2x to each element (maps to even numbers)
3. Concatenate odds first, then evens. The result is beautiful because each half is a scaled/shifted copy of a beautiful array, and cross-boundary triples are blocked by the parity argument.
4. Once the array is large enough, filter to keep only values where x is n or less.

Python solution

def beautifulArray(n):
    result = [1]
    while len(result) < n:
        result = [2 * x - 1 for x in result] + [2 * x for x in result]
    return [x for x in result if x <= n]

The loop doubles the array size each iteration. The 2 * x - 1 transform maps [1, 2, 3, ...] to [1, 3, 5, ...] (odd numbers), and 2 * x maps to [2, 4, 6, ...] (even numbers). After enough doublings, we filter out values larger than n.

Let's trace through the construction step by step.

Why this works, step by step

Consider the final array [1, 5, 3, 2, 4] for n = 5. Pick any three indices i, k, j with i strictly less than k strictly less than j:

• If all three elements come from the odd half [1, 5, 3], they are a scaled version of a smaller beautiful array, so no violation can occur within them.
• If all three come from the even half [2, 4], same reasoning applies.
• If they cross the boundary (some from the odd half, some from the even half), then A[i] + A[j] is odd (one odd, one even), but 2 * A[k] is always even. An odd number can never equal an even number, so no violation.

This parity argument is what makes the whole construction work. At every level of the recursion, cross-boundary triples are impossible, and within-boundary triples are handled by the recursive structure.

Complexity analysis

The time is O(n log n) because the array doubles in size at each step, and we perform O(n) work per step. There are O(log n) doubling steps. The final filter is O(n).

The space is O(n) for the result array. At each step, we build a new array of at most 2n elements, then discard the old one.

The building blocks

Parity-based separation

The core idea here is that separating odd and even numbers prevents arithmetic mean violations across the boundary. This parity trick shows up in other contexts too. Whenever you need to ensure that some linear relationship cannot hold between elements from two groups, check whether a parity or modular argument can rule it out. This is the same kind of thinking that appears in problems like Sort an Array, where divide and conquer splits the problem into independent halves.

Affine transformations preserve structure

The fact that 2x - 1 and 2x preserve the beautiful property is an instance of a broader principle: affine transformations (multiply by a constant, add a constant) preserve linear relationships. If a set has no arithmetic progressions, neither does any affine image of that set. This observation lets you reduce the problem to smaller instances and combine them freely.

Edge cases

• n = 1. Return [1]. A single element is always beautiful.
• n = 2. Return [1, 2]. No triple can exist with fewer than 3 elements.
• n = 3. The algorithm produces [1, 3, 2]. You can verify: 2 * 3 != 1 + 2 (6 != 3), so it works.
• Large n. The algorithm scales well since it runs in O(n log n) time and O(n) space.

From understanding to recall

The beautiful array construction is one of those problems where the idea is elegant but the details can slip. You might remember "something about odds and evens" but forget whether it is 2x - 1 for odds or 2x + 1. You might remember the parity argument but not the exact iterative loop structure.

Spaced repetition solves this. You write the solution from scratch, verify it works, then revisit it at increasing intervals. After a few reps, the construction becomes automatic. The key anchor is the loop: double the array with odds on the left, evens on the right, filter at the end.

CodeBricks breaks this into focused drills so you practice the construction independently from other problems. Each review reinforces the pattern until it sticks.

Related posts

• Sort an Array - Another divide-and-conquer problem where you split, solve recursively, and combine
• Different Ways to Add Parentheses - Divide and conquer on expressions, splitting at every operator
• Kth Largest Element - Uses quickselect's partition as a divide-and-conquer building block