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 ]
Difficulty
and has an acceptance rate of about 70% (90k+ submissions).
Typical patterns to solve this problem:
- Array
- Divide And Conquer
- Math
AI Disclaimer
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.
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
@cachedecorator (available fromfunctools) stores the result of each distinct call tobeautifulArray. 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 samen // 2value. -
Problem Size Halving - Each recursive step reduces the argument roughly by half (
(n + 1) // 2andn // 2). Consequently, the depth of recursion grows logarithmically withn. The transformations2*l - 1and2*rare 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 equalsn, 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.
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.
Code Quality
Complexity Analysis
Other Solutions
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++ |
Videos
Solved On The Same Day
- problem 2558: Take Gifts From the Richest Pile
- problem 395: Longest Substring with At Least K Repeating Characters
- problem 1382: Balance a Binary Search Tree
- problem 1424: Diagonal Traverse II
- problem 2406: Divide Intervals Into Minimum Number of Groups
- problem 2593: Find Score of an Array After Marking All Elements
- problem 2611: Mice and Cheese
- problem 2679: Sum in a Matrix
- problem 493: Reverse Pairs
- problem 2551: Put Marbles in Bags
Extra
- 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