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:
answer = [a1, a2, a3, ... , an], then the list [|a1 - a2|, |a2 - a3|, |a3 - a4|, ... , |an-1 - an|] 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 <= 104Problem 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.
The idea here is to create a pattern with the integers that alternates between choosing numbers from the start and the end of a range. This provides the necessary number of distinct absolute differences between consecutive elements.
We build the answer list by initially alternating between numbers from opposite ends of a list of size n. Then, we fill in the remaining elements in a simple sequence.
The function constructArray creates a list using a two-pointer approach. It alternates between adding the current low and high indices, and adjusts them after each addition.
After reaching k + 1 positions, it fills up the remaining part of the array.
Time Complexity: O(n), as we build the array in a single pass.
Space Complexity: O(n), for storing the answer.
This approach constructs the answer using a specific pattern that alternates addition and subtraction. It builds the sequence by starting linearly and then intelligently adds or subtracts to reach necessary differences.
This JavaScript solution constructs the array first by filling straightforward values, then follows pattern-based alternate increments and decrements to fill in necessary distinct differences.
JavaScript
Java
Time Complexity: O(n), iterating through the elements.
Space Complexity: O(n), owing to the storage of results.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Two-Pointer Alternating Approach | Time Complexity: O(n), as we build the array in a single pass. |
| Pattern-Based Construct Increment Decrement | Time Complexity: O(n), iterating through the elements. |
| Default Approach | — |
| 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. |
Beautiful Arrangement II | Live Coding with Explanation | Leetcode - 667 • Algorithms Made Easy • 3,819 views views
Watch 9 more video solutions →Practice Beautiful Arrangement II with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor