Beautiful Arrangement II | Live Coding with Explanation | Leetcode - 667
Beautiful Arrangement II - Video Solution
Watch 10 video solutions for Beautiful Arrangement II, a medium level problem involving Array, Math. This walkthrough by Algorithms Made Easy has 3,846 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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: 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 <= 104
Approach Overview
Problem Overview: Build an array containing numbers from 1..n such that the absolute differences between consecutive elements produce exactly k distinct values. The challenge is controlling how many unique differences appear while still using each number exactly once.
Approach 1: Two-Pointer Alternating Construction (O(n) time, O(1) space)
This greedy strategy constructs the first k+1 elements by alternating between the smallest and largest available numbers. Use two pointers: left = 1 and right = k + 1. Add numbers in the pattern left, right, left+1, right-1.... This alternating pattern intentionally creates decreasing differences: k, k-1, k-2..., guaranteeing exactly k distinct values. Once those k differences are established, append the remaining numbers sequentially from k+2 to n, which only introduces a difference of 1 that already exists. The approach relies on simple pointer movement and works well for problems involving array construction and greedy ordering.
Approach 2: Pattern-Based Increment Decrement Construction (O(n) time, O(1) space)
This method focuses on explicitly generating the difference pattern instead of thinking in terms of pointers. Start by listing numbers from 1 to n. For the first k+1 positions, alternate between incrementing from the low end and decrementing from the high end to enforce distinct gaps. The structure effectively creates a zigzag pattern: 1, k+1, 2, k, 3, k-1.... Each step intentionally reduces the difference magnitude, guaranteeing that the set of differences contains exactly k unique values. After finishing the zigzag section, append the remaining values in increasing order. The logic is mathematical and deterministic, making it a good fit for problems that combine math reasoning with controlled sequence construction.
Recommended for interviews: Interviewers typically expect the greedy alternating pattern because it directly demonstrates control over the difference sequence. Explaining why the first k differences become k, k-1, ... ,1 shows strong understanding of array manipulation and pattern design. A brute-force permutation search would be exponential and impractical, so candidates who jump to the constructive O(n) idea signal solid algorithmic intuition.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two-Pointer Alternating Construction | O(n) | O(1) | Best general solution. Clean greedy logic and minimal extra space. |
| Pattern-Based Increment Decrement | O(n) | O(1) | When reasoning directly about difference patterns and mathematical construction. |
| Brute Force Permutation Check | O(n!) | O(n) | Conceptual baseline only. Useful for understanding constraints but infeasible for large n. |