Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Make and follow sheets.Sign in

Beautiful Arrangement II solution and explanation

MediumArrayMath5 min read61.1% acceptanceUpdated 9 Apr 2026
Asked atGoogleBloomberg
Practise Beautiful Arrangement II
10:11
Beautiful Arrangement II | Live Coding with Explanation | Leetcode - 667Algorithms Made Easy · 10:11 · 3K viewsWatch on YouTube
9 more videos on this problem
  1. Beautiful Arrangement II | Live Coding with Explanation | Leetcode - 667Algorithms Made Easy · 10:11 · 3K views
  2. 667. Beautiful Arrangement II (Leetcode Medium)Programming Live with Larry · 31:22 · 987 views
  3. Beautiful Arrangement II | Leetcode 667 | Live coding session | April 12 | Explore | Leetcode MediumCoding Decoded · 11:56 · 958 views
  4. LeetCode - 667. Beautiful Arrangement II | Day 12 April ChallengeAditya Mahajan · 10:55 · 576 views
  5. LeetCode 667. Beautiful Arrangement IIHappy Coding · 11:25 · 457 views
  6. Leetcode - Beautiful Arrangement II (Python)Timothy H Chang · 4:45 · 407 views
  7. Daily Leetcode #377: Apr 12, 2021 - 667. Beautiful Arrangement IIProgramming Live with Larry · 18:11 · 400 views
  8. Beautiful Arrangement II | Maths | 667 LeetCode | LeetCode Explore | Day 12CodeWithSunny · 10:50 · 368 views
  9. Beautiful Arrangement II | LeetCode 667 | Coders CampCoders Camp · 6:38 · 356 views
  10. Leetcode 667 Beautiful Arrangement IIMath Geeks · 5:07 · 82 views

The problem

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.

def constructArray(n, k):
    answer = []
    low, high = 1, n
    for i in range(k + 1):
        if i % 2 == 0:
            answer.append(low)
            low += 1
        else:
            answer.append(high)
            high -= 1
    if k % 2 == 0:
        answer.extend(range(high, low - 1, -1))
    else:
        answer.extend(range(low, high + 1))
    return answer
#include <vector>
using namespace std;

vector<int> constructArray(int n, int k) {
    vector<int> answer;
    int low = 1, high = n;
    for (int i = 0; i <= k; ++i) {
        if (i % 2 == 0) {
            answer.push_back(low++);
        } else {
            answer.push_back(high--);
        }
    }
    if (k % 2 == 0) {
        for (int i = high; i >= low; --i) {
            answer.push_back(i);
        }
    } else {
        for (int i = low; i <= high; ++i) {
            answer.push_back(i);
        }
    }
    return answer;
}

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.

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.

import java.util.*;
public int[] constructArray(int n, int k) {
    int[] answer = new int[n];
    int index = 0;
    for (int i = 1; i <= n - k - 1; i++) {
        answer[index++] = i;
    }
    for (int j = 0; j <= k; j++) {
        if (j % 2 == 0) {
            answer[index++] = n - k / 2 + j / 2;
        } else {
            answer[index++] = n - (j + 1) / 2;
        }
    }
    return answer;
}
function constructArray(n, k) {
    let answer = Array(n);
    let index = 0;
    for (let i = 1; i <= n - k - 1; i++) {
        answer[index++] = i;
    }
    for (let j = 0; j <= k; j++) {
        answer[index++] = (j % 2 === 0) ? (n - k / 2 + Math.floor(j / 2)) : (n - Math.floor((j + 1) / 2));
    }
    return answer;
}

This Java solution involves incrementally constructing the initial sequence. Then it follows a methodical alternate increment and decrement strategy to meet the requirements of 'k' distinct differences.

Complexity

Time Complexity: O(n), due to filling the array comprehensively.
Space Complexity: O(n), for the array storage.

Try this approach in the editor

Approach 3: Default Approach

function constructArray(n: number, k: number): number[] {
    let l = 1;
    let r = n;
    const ans = new Array(n);
    for (let i = 0; i < k; ++i) {
        ans[i] = i % 2 == 0 ? l++ : r--;
    }
    for (let i = k; i < n; ++i) {
        ans[i] = k % 2 == 0 ? r-- : l++;
    }
    return ans;
}
func constructArray(n int, k int) []int {
	l, r := 1, n
	ans := make([]int, n)
	for i := 0; i < k; i++ {
		if i%2 == 0 {
			ans[i] = l
			l++
		} else {
			ans[i] = r
			r--
		}
	}
	for i := k; i < n; i++ {
		if k%2 == 0 {
			ans[i] = r
			r--
		} else {
			ans[i] = l
			l++
		}
	}
	return ans
}
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), due to filling the array comprehensively.
Space Complexity: O(n), for the array storage.

Default Approach–

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.

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.

Comments

Next problem · similarBeautiful ArrangementMedium
Now write it yourselfClose this page and solve Beautiful Arrangement II in the editor, without looking.
Practise Beautiful Arrangement II