Beautiful Arrangement II

MEDIUM

Description

Given two integers n and k, construct a list answer that contains n different positive integers ranging from 1 to n and obeys the following requirement:

Suppose this list is answer = [a₁, a₂, a₃, ... , a_n], then the list [|a₁ - a₂|, |a₂ - a₃|, |a₃ - a₄|, ... , |a_n-1 - a_n|] has exactly k distinct integers.

Return the list answer. If there multiple valid answers, return any of them.

Example 1:

Input: n = 3, k = 1
Output: [1,2,3]
Explanation: The [1,2,3] has three different positive integers ranging from 1 to 3, and the [1,1] has exactly 1 distinct integer: 1

Example 2:

Input: n = 3, k = 2
Output: [1,3,2]
Explanation: The [1,3,2] has three different positive integers ranging from 1 to 3, and the [2,1] has exactly 2 distinct integers: 1 and 2.

Constraints:

1 <= k < n <= 10⁴

Approaches

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

Brute-Force with Permutations

This approach involves generating every possible arrangement (permutation) of numbers from 1 to n. For each permutation, we calculate the absolute differences between adjacent elements and count the number of unique differences. If the count matches k, we have found a valid arrangement and can return it.

Algorithm

Generate all n! permutations of numbers from 1 to n.
For each permutation, do the following: a. Create an empty set to store the distinct differences. b. Iterate through the permutation from the first to the second-to-last element. c. Calculate the absolute difference between the current element and the next element. d. Add the calculated difference to the set.
After iterating through the permutation, check if the size of the set is equal to k.
If it is, the current permutation is a valid solution. Return it.
If no solution is found after checking all permutations (which is impossible based on the problem statement), return null.

The most straightforward but naive way to solve the problem is to explore every single possibility. The set of all possible arrangements of n distinct numbers is the set of all permutations. We can generate each permutation of the numbers [1, 2, ..., n] and, for each one, verify if it meets the condition. To verify a permutation [a₁, a₂, ..., aₙ], we compute the differences |a₁ - a₂|, |a₂ - a₃|, ..., |aₙ₋₁ - aₙ| and count how many of them are distinct. A HashSet is suitable for this counting. If the count equals k, we have found our answer. Since the problem guarantees that a solution exists, this method will eventually find one.

Complexity Analysis

Time Complexity: O(n! * n). There are `n!` permutations of `n` numbers. For each permutation, we perform `n-1` calculations to find the differences, taking O(n) time. This complexity makes the approach infeasible for the given constraints.Space Complexity: O(n). This space is used to store a single permutation, the set of differences, and for the recursion stack if generating permutations recursively.

Pros and Cons

Pros:

Conceptually simple and easy to understand.
Guaranteed to find a solution.

Cons:

Extremely inefficient due to factorial time complexity.
Will result in a 'Time Limit Exceeded' error on any platform for n greater than about 10 or 11.

Code Solutions

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

class Solution {
public
  int[] constructArray(int n, int k) {
    int l = 1, r = n;
    int[] ans = new int[n];
    for (int i = 0; i < k; ++i) {
      ans[i] = i % 2 == 0 ? l++ : r--;
    }
    for (int i = k; i < n; ++i) {
      ans[i] = k % 2 == 0 ? r-- : l++;
    }
    return ans;
  }
}

Video Solution

Watch the video walkthrough for Beautiful Arrangement II

Patterns:

Math

Data Structures:

Array