MediumNo. 0932
Beautiful Array — LeetCode 932 Python Solution
- Pattern
- Math and Number Theory
- Topics
- Array, Math, Divide and Conquer
- Reading time
- 2 min
- Source
- leetcode.com
The problem
An array nums of length n is beautiful if: nums is a permutation of the integers in the range [1, n]. For every 0 <= i < j < n, there is no index k with i < k < j where 2 * nums[k] == nums[i] + nums[j].
Example
- Input
- n = 4
- Output
- [2,1,4,3]
Python solution
class Solution:
def beautifulArray(self, n: int) -> List[int]:
if n == 1:
return [1]
left = self.beautifulArray((n + 1) >> 1)
right = self.beautifulArray(n >> 1)
left = [x * 2 - 1 for x in left]
right = [x * 2 for x in right]
return left + rightComplexity
- Time
- O(n) or O(1)
- Space · auxiliary
- O(1)
Pattern: Math and Number Theory
Find the closed form, the invariant, or the modular identity — and skip the loop entirely. LeetCode 932. Beautiful Array is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Math.
The math and number theory guide has the Python template for the pattern and the 485 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0927 | Three Equal Parts | Hard |
| 0048 | Rotate Image | Medium |
| 0066 | Plus One | Easy |
| 0189 | Rotate Array | Medium |
| 0204 | Count Primes | Medium |
| 0335 | Self Crossing | Hard |
Frequently asked questions
- How hard is LeetCode 932. Beautiful Array?
LeetCode 932. Beautiful Array is rated Medium on LeetCode.
- What topics does LeetCode 932. Beautiful Array cover?
LeetCode 932. Beautiful Array is tagged Array, Math and Divide and Conquer on LeetCode.