Jobs

Interviews

Discussions

Beautiful Array

Medium

Google

2 views

Topics:

ArraysRecursion

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].

Given the integer n, return any beautiful array nums of length n. There will be at least one valid answer for the given n.

Example 1:

Input: n = 4
Output: [2,1,4,3]

Example 2:

Input: n = 5
Output: [3,1,2,5,4]

Constraints:

1 <= n <= 1000

Beautiful Array

Medium

Google

2 views

Topics:

ArraysRecursion

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].

Given the integer n, return any beautiful array nums of length n. There will be at least one valid answer for the given n.

Example 1:

Input: n = 4
Output: [2,1,4,3]

Example 2:

Input: n = 5
Output: [3,1,2,5,4]

Constraints:

1 <= n <= 1000

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum size of the input integer `n`? Is it safe to assume it fits within the typical integer limits?
Is the goal to return *any* beautiful array of size `n`, or is there a specific beautiful array I should aim to construct?
Can you define more precisely what you mean by 'beautiful'? Specifically, must the condition `nums[k] * 2 != nums[i] + nums[j]` hold true for *all* i, j, and k where i < k < j, or only for *some* of them?
Is the input always a positive integer `n`? Do I need to handle edge cases like `n = 0` or `n = 1`?
Are there any memory constraints I should be aware of, given the size of `n` can be quite large?

Brute Force Solution

Approach

The brute force approach to creating a 'beautiful array' involves testing every possible arrangement of numbers. We generate each possible array, then we check if that array meets the 'beautiful' criteria. This guarantees we will find a 'beautiful' array if one exists.

Here's how the algorithm would work step-by-step:

Start with an initial arrangement of the numbers.
Check if this specific arrangement satisfies the 'beautiful' condition.
If it does, you've found a solution!
If not, create a new, different arrangement of the numbers.
Repeat the process of checking the 'beautiful' condition for this new arrangement.
Continue generating and checking different arrangements until you find one that is 'beautiful'.

Code Implementation

import itertools

def is_beautiful(arrangement):
    for i in range(len(arrangement)):
        for j in range(i + 1, len(arrangement)):
            sum_of_elements = arrangement[i] + arrangement[j]
            if sum_of_elements % 2 == 0:
                average = sum_of_elements // 2
                if average in arrangement[i+1:j]:
                    return False
    return True

def beautiful_array_brute_force(number):
    numbers = list(range(1, number + 1))
    possible_arrangements = itertools.permutations(numbers)

    for arrangement in possible_arrangements:
        # Check all permutations to meet criteria
        if is_beautiful(arrangement):

            return list(arrangement)

    # If there are no beautiful arrangements, return empty.
    return []

Big(O) Analysis

Time Complexity

O(n * n!) – The brute force approach involves generating all possible permutations of the input array of size n. Generating all permutations takes O(n!) time. For each of these permutations, we need to check if it's a 'beautiful array.' Checking the 'beautiful' condition could involve iterating through the array to check some property between pairs or triplets. Assuming this check takes O(n) time per permutation. Therefore the overall time complexity is O(n * n!).

Space Complexity

O(N) – The brute force approach generates every possible arrangement of the numbers. To check each arrangement, which is a permutation of the input numbers, the algorithm stores the current permutation. Since a permutation of N numbers requires storing all N numbers in a specific order, this implies an auxiliary array of size N is used to represent the current arrangement. Therefore, the space complexity is O(N), where N is the number of elements in the input array.

Optimal Solution

Approach

The key idea is to divide the problem into smaller, self-similar subproblems. We build the beautiful array from smaller beautiful arrays. Odd and even numbers can be placed in separate halves which guarantees the property.

Here's how the algorithm would work step-by-step:

Start with a small, known beautiful array, like a single number (e.g., [1]).
To create a larger beautiful array, generate the odd numbers and even numbers separately.
The odd numbers are created by multiplying each element of the original array by 2 and subtracting 1. Similarly generate the even numbers by multiplying each element of the original array by 2.
Concatenate the odd array and the even array to form a new beautiful array that is twice the size of the original.
If the final array is larger than the target number, filter out numbers that exceed the range.
Continue this process of generating and combining smaller beautiful arrays until you reach the desired size and range.

Code Implementation

def beautiful_array(number): 
    beautiful_array_result = [1]

    # Build beautiful arrays iteratively.
    while len(beautiful_array_result) < number:
        temp_array = []
        
        # Generate odd numbers.
        for element in beautiful_array_result:
            temp_array.append(2 * element - 1)

        # Generate even numbers.
        for element in beautiful_array_result:
            temp_array.append(2 * element)
        
        beautiful_array_result = temp_array

    # Filter out numbers exceeding the range.
    beautiful_array_result = [element for element in beautiful_array_result if element <= number]

    # Ensures the result array has the correct size
    return beautiful_array_result

Big(O) Analysis

Time Complexity

O(n log n) – The algorithm starts with an array of size 1 and repeatedly doubles its size until it reaches a size greater than or equal to n. This doubling process takes log n steps. In each step, we iterate through all elements of the current array and perform constant-time operations (multiplication and subtraction) to generate the odd and even arrays, effectively doubling the array size. Thus the number of operations at each doubling step scales linearly with the current array size. Summing the work across these log n steps gives us roughly n/2 + n/4 + ... + 1, where n is the target array size, and by properties of geometric series, this sum is bounded by O(n). However, the merging of odd and even elements at each iteration contributes another linear time operation in each iteration, i.e O(n). Therefore, the final complexity is O(n log n).

Space Complexity

O(N) – The algorithm constructs a sequence of beautiful arrays, starting from a small array and doubling in size until the target size N is reached. The intermediate beautiful arrays generated in steps 2-4, as well as the final filtered array in step 5, all require storing up to N integer elements. Therefore, the algorithm uses auxiliary space proportional to the input size N to store these arrays. This results in an O(N) space complexity.

Edge Cases

Case	How to Handle
Input n is 1	Return [1] since a single element array is trivially beautiful.
Input n is 2	Return [1,2] as the only beautiful array of size 2.
Large input n leading to deep recursion	Use dynamic programming/memoization within the recursive calls to avoid stack overflow and improve performance.
Negative input for n	Raise an IllegalArgumentException/ValueError as n must be a positive integer.
n is a power of 2	Observe the pattern that beautiful arrays for powers of 2 can be efficiently constructed recursively.
Integer overflow during calculations (e.g., mid * 2)	Ensure intermediate calculations avoid potential integer overflows by using appropriate data types (e.g., long).
Non-integer input for n	Raise an IllegalArgumentException/ValueError as n must be an integer.
Extreme value of n (near Integer.MAX_VALUE)	Ensure memory allocation for the array does not exceed available resources or lead to out-of-memory errors.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum size of the input integer `n`? Is it safe to assume it fits within the typical integer limits?
Is the goal to return *any* beautiful array of size `n`, or is there a specific beautiful array I should aim to construct?
Can you define more precisely what you mean by 'beautiful'? Specifically, must the condition `nums[k] * 2 != nums[i] + nums[j]` hold true for *all* i, j, and k where i < k < j, or only for *some* of them?
Is the input always a positive integer `n`? Do I need to handle edge cases like `n = 0` or `n = 1`?
Are there any memory constraints I should be aware of, given the size of `n` can be quite large?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start with an initial arrangement of the numbers.
Check if this specific arrangement satisfies the 'beautiful' condition.
If it does, you've found a solution!
If not, create a new, different arrangement of the numbers.
Repeat the process of checking the 'beautiful' condition for this new arrangement.
Continue generating and checking different arrangements until you find one that is 'beautiful'.

Code Implementation

import itertools

def is_beautiful(arrangement):
    for i in range(len(arrangement)):
        for j in range(i + 1, len(arrangement)):
            sum_of_elements = arrangement[i] + arrangement[j]
            if sum_of_elements % 2 == 0:
                average = sum_of_elements // 2
                if average in arrangement[i+1:j]:
                    return False
    return True

def beautiful_array_brute_force(number):
    numbers = list(range(1, number + 1))
    possible_arrangements = itertools.permutations(numbers)

    for arrangement in possible_arrangements:
        # Check all permutations to meet criteria
        if is_beautiful(arrangement):

            return list(arrangement)

    # If there are no beautiful arrangements, return empty.
    return []

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Start with a small, known beautiful array, like a single number (e.g., [1]).
To create a larger beautiful array, generate the odd numbers and even numbers separately.
The odd numbers are created by multiplying each element of the original array by 2 and subtracting 1. Similarly generate the even numbers by multiplying each element of the original array by 2.
Concatenate the odd array and the even array to form a new beautiful array that is twice the size of the original.
If the final array is larger than the target number, filter out numbers that exceed the range.
Continue this process of generating and combining smaller beautiful arrays until you reach the desired size and range.

Code Implementation

def beautiful_array(number): 
    beautiful_array_result = [1]

    # Build beautiful arrays iteratively.
    while len(beautiful_array_result) < number:
        temp_array = []
        
        # Generate odd numbers.
        for element in beautiful_array_result:
            temp_array.append(2 * element - 1)

        # Generate even numbers.
        for element in beautiful_array_result:
            temp_array.append(2 * element)
        
        beautiful_array_result = temp_array

    # Filter out numbers exceeding the range.
    beautiful_array_result = [element for element in beautiful_array_result if element <= number]

    # Ensures the result array has the correct size
    return beautiful_array_result

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Input n is 1	Return [1] since a single element array is trivially beautiful.
Input n is 2	Return [1,2] as the only beautiful array of size 2.
Large input n leading to deep recursion	Use dynamic programming/memoization within the recursive calls to avoid stack overflow and improve performance.
Negative input for n	Raise an IllegalArgumentException/ValueError as n must be a positive integer.
n is a power of 2	Observe the pattern that beautiful arrays for powers of 2 can be efficiently constructed recursively.
Integer overflow during calculations (e.g., mid * 2)	Ensure intermediate calculations avoid potential integer overflows by using appropriate data types (e.g., long).
Non-integer input for n	Raise an IllegalArgumentException/ValueError as n must be an integer.
Extreme value of n (near Integer.MAX_VALUE)	Ensure memory allocation for the array does not exceed available resources or lead to out-of-memory errors.