Skip to main content
Talentd

Beautiful Arrangement II - Solution & Explanation

MediumArrayMath7 min readAsked at: Google, Bloomberg
Practice this problem

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

Approach 1: Two-Pointer Alternating Approach

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.

Code

PythonC++

Python

C++

Complexity

Time Complexity: O(n), as we build the array in a single pass.
Space Complexity: O(n), for storing the answer.

Try this approach in the editor →

Approach 2: Pattern-Based Construct Increment Decrement

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.

Code

JavaScriptJava

JavaScript

Java

Complexity

Time Complexity: O(n), iterating through the elements.
Space Complexity: O(n), owing to the storage of results.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Two-Pointer Alternating Approach

Time Complexity: O(n), as we build the array in a single pass.
Space Complexity: O(n), for storing the answer.

Pattern-Based Construct Increment Decrement

Time Complexity: O(n), iterating through the elements.
Space Complexity: O(n), owing to the storage of results.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Two-Pointer Alternating ConstructionO(n)O(1)Best general solution. Clean greedy logic and minimal extra space.
Pattern-Based Increment DecrementO(n)O(1)When reasoning directly about difference patterns and mathematical construction.
Brute Force Permutation CheckO(n!)O(n)Conceptual baseline only. Useful for understanding constraints but infeasible for large n.

Video Solution

Beautiful Arrangement II | Live Coding with Explanation | Leetcode - 667 • Algorithms Made Easy • 3,846 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Beautiful Arrangement II easy or hard?
Beautiful Arrangement II is rated Medium on LeetCode. The difficulty comes from recognizing the constructive pattern that controls distinct differences. Once the alternating strategy is understood, the implementation is straightforward.
Beautiful Arrangement II Python/Java solution
Python, Java, C++, and JavaScript implementations typically follow the same greedy pattern. Use two indices representing the current low and high numbers, alternate placement for the first k+1 positions, then append the remaining numbers sequentially. The logic stays O(n) across all languages.
How to solve Beautiful Arrangement II in O(n)?
Create the first k+1 elements using an alternating pattern between low and high values such as 1, k+1, 2, k, 3, k-1. This produces k distinct adjacent differences. After generating that section, append the remaining numbers from k+2 to n in increasing order, which doesn't introduce new difference values.
What is the best approach for Beautiful Arrangement II?
The optimal approach uses a greedy alternating pattern with two pointers. Construct the first k+1 elements by alternating between the smallest and largest numbers to produce differences k, k-1, ..., 1. After that, append the remaining numbers sequentially. This guarantees exactly k distinct differences in O(n) time and O(1) space.
Is Beautiful Arrangement II asked at Google/Amazon/Meta?
Variants of constructive array and greedy pattern problems appear in interviews at large companies like Google, Amazon, and Meta. While this exact problem may not always appear verbatim, the idea of building sequences with controlled differences or constraints is common in algorithm interviews.
What data structure is used in Beautiful Arrangement II?
The solution mainly uses an array with simple pointer variables. Two-pointer techniques help alternate between low and high values during construction. No advanced data structures like heaps or hash maps are required.
What is the time complexity of Beautiful Arrangement II?
The optimal construction runs in O(n) time because each number from 1 to n is placed exactly once in the result array. No sorting, backtracking, or nested loops are required. Space complexity is O(1) aside from the output array since only a few pointers or counters are used.

Ready to solve this problem?

Practice Beautiful Arrangement II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Beautiful Arrangement