We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Beautiful Array

Difficulty: Medium

Problem Description

Given an integer n, return any beautiful array nums of length n. An array nums is beautiful if it is a permutation of the integers in the range [1, n] and for every 0 <= i < j < n, there is no index k with i < k < j where 2 * nums[k] == nums[i] + nums[j].

Key Insights

  • A beautiful array must contain unique integers from 1 to n.
  • The condition involving indices i, j, and k means the array cannot have certain arithmetic relationships between its elements.
  • The problem can be solved using a divide-and-conquer approach by separating the numbers into odd and even groups.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

To construct a beautiful array, we can use a recursive approach that generates two separate arrays: one containing odd numbers and the other containing even numbers. By combining these two arrays, we can ensure that the condition involving indices i, j, and k is satisfied. The algorithm effectively divides the problem into smaller subproblems until the base case is reached.

Code Solutions

def beautifulArray(n):
    if n == 1:
        return [1]
    
    # Recursive call to generate the beautiful array for even and odd indices
    odds = beautifulArray((n + 1) // 2)
    evens = beautifulArray(n // 2)
    
    # Combine odds and evens to form the final beautiful array
    return [x * 2 - 1 for x in odds] + [x * 2 for x in evens]

# Example usage
print(beautifulArray(4))  # Output: [2, 1, 4, 3]
← Back to All Questions