Beautiful Array

MEDIUM

Description

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

Approaches

Checkout 3 different approaches to solve Beautiful Array. Click on different approaches to view the approach and algorithm in detail.

Brute Force by Generating All Permutations

The most straightforward approach is to try every possible arrangement of numbers from 1 to n. We can generate all permutations of the array [1, 2, ..., n]. For each permutation, we check if it satisfies the 'beautiful' property. The first one we find is a valid answer, as the problem guarantees at least one exists.

Algorithm

Create an array nums containing integers from 1 to n.
Implement a backtracking function generatePermutations(start, nums):
- Base case: If start == n, we have a full permutation. Check if it's beautiful using isBeautiful(nums). If it is, store it as the answer and stop.
- Recursive step: For i from start to n-1:
  - Swap nums[start] and nums[i].
  - Call generatePermutations(start + 1, nums).
  - Backtrack: Swap nums[start] and nums[i] back.
Implement isBeautiful(nums):
- For i from 0 to n-1:
- For j from i + 2 to n-1:
  - For k from i + 1 to j-1:
    - If 2 * nums[k] == nums[i] + nums[j], return false.
- Return true.
Start the process by calling generatePermutations(0, nums).

The algorithm first generates a list of numbers from 1 to n. It then uses a backtracking algorithm to generate all n! permutations of this list. For each generated permutation, a helper function isBeautiful is called to verify the property. The isBeautiful function iterates through all possible triplets (i, k, j) such that i < k < j. For each triplet, it checks if 2 * nums[k] == nums[i] + nums[j]. If this condition is ever met, the array is not beautiful, and the function returns false. The first permutation that passes the check is returned as the answer.

class Solution {
    int[] ans;
    public int[] beautifulArray(int n) {
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = i + 1;
        }
        permute(nums, 0);
        return ans;
    }

    private void permute(int[] nums, int start) {
        if (ans != null) return; // Already found a solution
        if (start == nums.length) {
            if (isBeautiful(nums)) {
                ans = nums.clone();
            }
            return;
        }
        for (int i = start; i < nums.length; i++) {
            swap(nums, start, i);
            permute(nums, start + 1);
            swap(nums, start, i); // backtrack
        }
    }

    private boolean isBeautiful(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            for (int j = i + 2; j < n; j++) {
                for (int k = i + 1; k < j; k++) {
                    if (2 * nums[k] == nums[i] + nums[j]) {
                        return false;
                    }
                }
            }
        }
        return true;
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

Complexity Analysis

Time Complexity: O(n! * n^3). There are `n!` permutations. For each permutation, we check the beautiful property in O(n^3) time. This is prohibitively slow for the given constraints.Space Complexity: O(n) for storing the permutation and for the recursion stack.

Pros and Cons

Pros:

Conceptually simple and easy to understand.
Guaranteed to find a solution if one exists.

Cons:

Extremely inefficient and times out for n larger than about 10.

Code Solutions

Checking out 3 solutions in different languages for Beautiful Array. Click on different languages to view the code.

class Solution {
public
  int[] beautifulArray(int n) {
    if (n == 1) {
      return new int[]{1};
    }
    int[] left = beautifulArray((n + 1) >> 1);
    int[] right = beautifulArray(n >> 1);
    int[] ans = new int[n];
    int i = 0;
    for (int x : left) {
      ans[i++] = x * 2 - 1;
    }
    for (int x : right) {
      ans[i++] = x * 2;
    }
    return ans;
  }
}

Video Solution

Watch the video walkthrough for Beautiful Array

Algorithms:

Divide and Conquer

Patterns:

Math

Data Structures:

Array