Beautiful Arrangement II
MedPrompt
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 = [a1, a2, a3, ... , an], then the list[|a1 - a2|, |a2 - a3|, |a3 - a4|, ... , |an-1 - an|]has exactlykdistinct 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: 1Example 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 <= 104
Approaches
3 approaches with complexity analysis and trade-offs.
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 from1ton. - 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.
Walkthrough
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
Time
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
O(n). This space is used to store a single permutation, the set of differences, and for the recursion stack if generating permutations recursively.
Trade-offs
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
ngreater than about 10 or 11.
This is an improvement over the brute-force approach. Instead of generating a full permutation and then checking it, we build the arrangement one number at a time. We maintain a set of used numbers and a set of differences encountered so far. If at any point the number of distinct differences exceeds k, we prune that search path and backtrack.
Algorithm
- Define a recursive function, e.g.,
solve(path), wherepathis the list being constructed. - The base case for the recursion is when
path.size() == n. At this point, check if the number of distinct differences is exactlyk. If so, a solution is found. - In the recursive step, iterate through all numbers from
1ton. - For each number
numnot yet used in thepath: a. Addnumto thepath. b. Marknumas used. c. Pruning: Before the recursive call, calculate the set of distinct differences for the currentpath. If the size of this set exceedsk, this path is invalid, so we backtrack immediately. d. Make a recursive call:solve(path). e. If the recursive call finds a solution, propagate it upwards. f. Backtrack: Removenumfrom thepathand unmark it as used to explore other possibilities.
Walkthrough
Backtracking systematically builds a candidate solution and abandons it as soon as it determines that it cannot be completed to a valid solution. We build the list of numbers one by one. At each step, we try to place an unused number. After placing a number, we check the new set of differences. If the number of distinct differences already exceeds k, we know this path cannot lead to a solution, so we 'prune' it by not exploring it further. This is more efficient than generating the full permutation because we discard invalid partial solutions early. However, the search space can still be very large, making this approach too slow for the problem's constraints.
class Solution { int[] ans; boolean[] used; int n, k; public int[] constructArray(int n, int k) { this.n = n; this.k = k; this.used = new boolean[n + 1]; List<Integer> path = new ArrayList<>(); solve(path); return ans; } private boolean solve(List<Integer> path) { if (path.size() == n) { Set<Integer> diffs = new HashSet<>(); for (int i = 0; i < n - 1; i++) { diffs.add(Math.abs(path.get(i) - path.get(i + 1))); } if (diffs.size() == k) { ans = path.stream().mapToInt(Integer::intValue).toArray(); return true; } return false; } // Pruning check Set<Integer> currentDiffs = new HashSet<>(); for (int i = 0; i < path.size() - 1; i++) { currentDiffs.add(Math.abs(path.get(i) - path.get(i + 1))); } if (currentDiffs.size() > k) { return false; } for (int i = 1; i <= n; i++) { if (!used[i]) { used[i] = true; path.add(i); if (solve(path)) { return true; } path.remove(path.size() - 1); // Backtrack used[i] = false; } } return false; }}Complexity
Time
O(k^n) or similar exponential complexity in the worst case. While better than O(n!), it is not efficient enough for the given constraints.
Space
O(n) for the recursion stack, the list storing the current path, and the boolean `used` array.
Trade-offs
Pros
More efficient than pure brute-force due to pruning.
It is a general strategy for solving constraint satisfaction problems.
Cons
Still has a worst-case exponential time complexity.
Too slow for the given constraints (
nup to 10^4), leading to 'Time Limit Exceeded'.The pruning logic can be tricky to implement effectively.
This optimal approach directly constructs a valid array in linear time. The key insight is to combine two simple patterns: one that generates many distinct differences and one that generates only one distinct difference. By creating a prefix that generates k distinct differences and then appending the rest of the numbers in a simple sequence (which only generates differences of 1), we can achieve the desired result.
Algorithm
- Create an integer array
ansof sizen. - Initialize two pointers,
low = 1andhigh = k + 1. - Initialize an index for the
ansarray,idx = 0. - Construct the first
k + 1elements ofansby alternating betweenlowandhighto generatekdistinct differences (k, k-1, ..., 1).- In a loop that runs as long as
low <= high: a. Placelowintoansand incrementlow:ans[idx++] = low++. b. Iflowhas not surpassedhigh, placehighintoansand decrementhigh:ans[idx++] = high--.
- In a loop that runs as long as
- The first
k + 1elements are now set. The numbers used are1throughk + 1. - Fill the rest of the array (
idxfromk + 1ton - 1) with the remaining numbers (k + 2, k + 3, ..., n) in simple increasing order.- For
ifromk + 2ton, setans[idx++] = i.
- For
- Return the constructed array
ans.
Walkthrough
We can construct the array by observing patterns for the minimum and maximum possible values of k.
- For
k=1, the array[1, 2, 3, ..., n]works, giving only the difference1. - For maximum
k, the array[1, n, 2, n-1, ...]generates a wide range of differences.
We can combine these ideas. To get exactly k distinct differences, we can construct the first part of the array to produce k distinct differences, and the rest of the array to produce no new differences. A clever way to generate k distinct differences (k, k-1, ..., 1) is to arrange the first k+1 numbers as [1, k+1, 2, k, 3, ...]. This prefix uses numbers from 1 to k+1.
After this prefix is constructed, we can simply append the remaining numbers, k+2, k+3, ..., n, in increasing order. The differences in this latter part will all be 1, which is a difference we have already created in the prefix. The single difference between the end of the prefix and the start of the suffix will not violate the k distinct difference count. This method guarantees a valid construction in a single pass.
class Solution { public int[] constructArray(int n, int k) { int[] ans = new int[n]; int idx = 0; int low = 1, high = k + 1; // Construct the first k+1 elements to generate k distinct differences. // This part creates differences: k, k-1, k-2, ..., 1. while (low <= high) { ans[idx++] = low++; if (low <= high) { ans[idx++] = high--; } } // Append the rest of the numbers. These will have a difference of 1. // The numbers from k+2 to n are simply appended in order. for (int i = k + 2; i <= n; i++) { ans[idx++] = i; } return ans; }}Complexity
Time
O(n), as we iterate through the numbers from 1 to `n` once to fill the result array.
Space
O(1) extra space. The O(n) space for the result array is not typically counted as extra space.
Trade-offs
Pros
Optimal O(n) time complexity.
Optimal O(1) extra space complexity (excluding the output array).
Simple to implement once the pattern is understood.
Directly builds the solution without any searching or backtracking.
Cons
The underlying logic for why this construction works might not be immediately obvious.
Solutions
Solution
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; }}class Solution {public: vector<int> constructArray(int n, int k) { int l = 1, r = n; vector<int> ans(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; }};class Solution: def constructArray(self, n: int, k: int) -> List[int]: l, r = 1, n ans = [] for i in range(k): if i % 2 == 0: ans . append(l) l += 1 else: ans . append(r) r -= 1 for i in range(k, n): if k % 2 == 0: ans . append(r) r -= 1 else: ans . append(l) l += 1 return ansVideo 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.