Scale Engineer

Beautiful Array

Med
#0886Time: 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: O(n) for storing the permutation and for the recursion stack.
Patterns
Math
Algorithms
Divide and Conquer
Data structures
Array

Prompt

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

3 approaches with complexity analysis and trade-offs.

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

Walkthrough

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

Time

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

O(n) for storing the permutation and for the recursion stack.

Trade-offs

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.

Solutions

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 walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem