Problem 932

Abstract / Summary

Given an integer n, build an array following specific rules and return its nth element.

Note

The full problem description, including helpful examples, can be found on LeetCode.

Python 0932.py

class Solution:
    @cache
    def beautifulArray(self, n: int) -> List[int]:
        # up to n=10 you can brute force the problem
        # and will find many solutions, e.g. for 1 <= n <= 4:
        # n=1 (1)
        # n=2 (1, 2),    (2, 1)
        # n=3 (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2)
        #     (1, 3, 2, 4), (1, 3, 4, 2)
        # n=4 (2, 1, 4, 3)
        #     (2, 4, 1, 3), (2, 4, 3, 1)
        #     (3, 1, 2, 4), (3, 1, 4, 2)    <= interesting
        #     (3, 4, 1, 2)
        #     (4, 2, 1, 3), (4, 2, 3, 1)
        # somethings stands out:
        # - some solutions have all odd numbers first, then only even numbers
        #   - e.g. (3, 1, 4, 2)
        #   - the opposite is true if n is even, e.g. (4, 2, 1, 3) but never if n is odd
        #   - hence let's only consider the cases where "odds first"
        # - when looking only at these even numbers in the second half
        #   and dividing them by 2, then we get a solution for n//2
        # - it took me a while to realize that there is a similar pattern for the odd numbers:
        #   plus one then divided by two leads to a solution for n//2 as well
        # - e.g. (3, 1, 4, 2) => (3, 1) and (4, 2) => (3, 1) plus 1 div 2 and (4, 2) div 2 => (2, 1) and (2, 1)

        # basic cases
        if n <= 1:
            return [ 1 ]
        if n == 2:
            return [ 1, 2 ]

        left  = self.beautifulArray((n + 1) // 2)
        right = self.beautifulArray( n      // 2)
        return [ 2*l-1 for l in left ] + [ 2*r for r in right ]
34 lines | 1574 bytes | submitted November 22, 2023 | GitHub   220% comment ratio | tab size 4 | low complexity

Difficulty

This problem is ranked as
easy medium hard

and has an acceptance rate of about 70% (90k+ submissions).

Typical patterns to solve this problem:
  • Array
  • Divide And Conquer
  • Math
I solved 663 easy, 1250 medium and 309 hard problems

AI Disclaimer

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.
LeetCode profile | GitHub repo

Code Walkthrough

Overview

The provided implementation computes a beautiful array for a given integer n. A beautiful array is a permutation of the numbers 1 … n that satisfies the condition that for any three indices i < j < k, the middle element arr[j] is never the average of arr[i] and arr[k]. The algorithm builds such an array recursively, exploiting a structural property that separates odd and even values. Memoization via the @cache decorator ensures that each sub-problem is solved only once, yielding an efficient solution even for large inputs.

Core Logic

The function follows a divide-and-conquer strategy. For a given n it first solves two smaller instances: one for the odd positions and one for the even positions. The odd part is generated by mapping the result of a recursive call on (n + 1) // 2 through the transformation 2*l - 1. The even part is generated by mapping the result of a recursive call on n // 2 through the transformation 2*r. Concatenating these two transformed lists yields a valid beautiful array for n.

left  = self.beautifulArray((n + 1) // 2)
right = self.beautifulArray(n // 2)
return [2*l - 1 for l in left] + [2*r for r in right]

Base Cases

The recursion terminates for the smallest inputs. When n is 0 or 1, the only possible beautiful array is [1]. For n == 2 the array [1, 2] satisfies the condition and serves as a seed for larger constructions.

if n <= 1:
    return [1]
if n == 2:
    return [1, 2]

These explicit checks prevent unnecessary recursion and guarantee that the algorithm always has a concrete result to build upon.

Edge-Case Handling

The implementation explicitly addresses the minimal values of n. The condition n <= 1 captures the degenerate case where the input is zero or one, returning a singleton list. The separate clause for n == 2 handles the smallest non-trivial permutation, ensuring that the subsequent odd/even splitting logic never receives an argument smaller than one. By covering these scenarios, the function avoids invalid list indexing or empty recursive calls.

Performance Optimizations

Two primary techniques reduce the computational effort:

  • Memoization - The @cache decorator (available from functools) stores the result of each distinct call to beautifulArray. When the same sub-problem size appears again, the cached result is returned instantly, eliminating repeated work. This is especially beneficial because the recursion generates overlapping sub-problems; for example, both the left and right branches may request the result for the same n // 2 value.

  • Problem Size Halving - Each recursive step reduces the argument roughly by half ((n + 1) // 2 and n // 2). Consequently, the depth of recursion grows logarithmically with n. The transformations 2*l - 1 and 2*r are performed with list comprehensions, which are executed in linear time relative to the size of the sub-arrays, but because the total number of elements processed across all levels equals n, the overall work remains proportional to the final output size.

The combination of memoization and the divide-by-two reduction yields a solution that scales gracefully, handling large inputs without excessive recomputation.

Structural Insight

The algorithm relies on a mathematical observation: if a beautiful array exists for a size m, then scaling each element by 2 produces a beautiful array consisting solely of even numbers for size 2*m. Similarly, scaling each element by 2 and subtracting 1 yields a beautiful array of odd numbers for size 2*m. By recursively constructing the odd and even halves and then interleaving them, the method guarantees that no three elements will form an arithmetic progression, satisfying the definition of a beautiful array.

The code directly encodes this insight in the two list comprehensions that transform the recursively obtained left and right arrays. The concatenation order-odd part first, even part second-preserves the required property across the boundary between the two halves.

Summary of Execution Flow

When the function is invoked, it first checks whether n falls into one of the base cases. If not, it computes the size of the odd segment as (n + 1) // 2 and the size of the even segment as n // 2. It then recursively obtains beautiful arrays for these two sizes. The odd segment is transformed by 2*l - 1, turning each element into an odd number in the appropriate range. The even segment is transformed by 2*r, turning each element into an even number. Finally, the two transformed lists are concatenated, producing a full beautiful array for the original n. Throughout this process, previously computed sub-arrays are cached, ensuring that each distinct size is processed only once.

written by openai gpt

ELI5 - Simplified Explanation

Imagine you have a box of numbered building blocks starting from one and going all the way up to some number. The goal is to line them up in a very special way. To make this line special, if you pick any three blocks in the row, the middle one shouldn't be exactly halfway between the other two. It is like a puzzle where you have to keep the numbers dancing around each other so no one gets stuck in a perfect middle spot.

To solve this, the code uses a neat trick. It splits the big pile of numbers into two smaller piles. One pile gets all the odd numbers, like one, three, and five. The other pile gets all the even numbers, like two, four, and six.

The clever part is that the code discovers that these two smaller piles are actually just smaller versions of the same puzzle. It shrinks the odd numbers and the even numbers down until they are tiny enough to solve easily. Once those small pieces are solved, it doubles the numbers to turn them back into the right size and puts them together. By stacking the odd numbers first and the even numbers second, everything stays in the right order so that no block ever sits exactly in the middle of two others. It keeps doing this over and over until the whole line is finished.

written by google gemini

Code Quality

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):
n = 27 | median = 8 | μ = 7.89 | σ = 1.37

Complexity Analysis

not analyzed yet

Other Solutions

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)
author
author solutions
www AlgoMonster C++ Python Java TS
WalkCCC C++ Python Java
leetcode.ca C++ Python Java Go
LeetcodeHelp C++ Python Java
Progiez C++ Python Java
github black-shadows C++
charles-wangkai Java
everthis JS
fengvyi C++
JoshCrozier JS
lkwq007 Python
suxrobGM C#
wisdompeak C++
AlgoMonster C++, Python, Java, TypeScript
WalkCCC C++, Python, Java
leetcode.ca C++, Go, Java, Python
LeetcodeHelp C++, Java, Python
Progiez C++, Java, Python
black-shadows C++, C++
charles-wangkai Java
everthis JavaScript
fengvyi C++
JoshCrozier JavaScript
lkwq007 Python
suxrobGM C#
wisdompeak C++
25 links | 13 authors | 7 languages

Videos

4 videos   did my crawler come up with invalid videos ? drop me a line.

Solved On The Same Day

11 solutions   November 22, 2023

Extra

There are a few extra pages giving you some insights into my setup:
  • Tech Stack - my development environment and tools
  • AI - how AI helped me create this website (NOT solving the problems)
  • Progress - progression over time
  • Quality - code quality