LeetCode 667: Beautiful Arrangement II Solution in Python – A Step-by-Step Guide

What Is LeetCode 667: Beautiful Arrangement II?

In LeetCode 667: Beautiful Arrangement II, you’re given two integers n and k, and your task is to construct an array of length n using numbers 1 to n exactly once (a permutation), such that the absolute differences between consecutive elements have exactly k distinct values. Return any such array. For example, with n = 5 and k = 3, one possible array is [1, 5, 2, 4, 3], with differences [4, 3, 2], exactly 3 distinct values. The problem tests your ability to control the number of unique differences in a sequence.

Problem Statement

• Input:
• n: Integer (array length, 1 to n permutation).
• k: Integer (number of distinct differences).
• Output: A list of integers—permutation with exactly k distinct differences.
• Rules:
• Use numbers 1 to n exactly once.
• Differences = |arr[i] - arr[i+1]| for i from 0 to n-2.
• Result must have exactly k unique differences.

Constraints

• 1 ≤ k < n ≤ 10⁴.

Examples

• Input: n = 3, k = 1
• Output: [1, 2, 3] (Differences: [1, 1], 1 distinct)
• Input: n = 3, k = 2
• Output: [1, 3, 2] (Differences: [2, 1], 2 distinct)
• Input: n = 5, k = 3
• Output: [1, 5, 2, 4, 3] (Differences: [4, 3, 2], 3 distinct)

These examples set the numbers—let’s solve it!

Understanding the Problem: Crafting Distinct Differences

To solve LeetCode 667: Beautiful Arrangement II in Python, we need to construct a permutation of numbers 1 to n with exactly k distinct consecutive differences. A brute-force approach—generating all permutations and checking differences—would be O(n!), impractical for n ≤ 10⁴. Since we control the differences, we can construct the array directly or adjust greedily. We’ll use:

• Best Solution (Constructive Pattern with Alternating Differences): O(n) time, O(n) space—fast and elegant.
• Alternative Solution (Greedy with Adjustment): O(n) time, O(n) space—intuitive but less precise.

Let’s start with the constructive solution, breaking it down for beginners.

Best Solution: Constructive Pattern with Alternating Differences

Why This Is the Best Solution

The constructive pattern with alternating differences is the top choice for LeetCode 667 because it’s efficient—O(n) time with O(n) space—and uses a clever insight: we can create k distinct differences by alternating high and low numbers for the first part, then filling the rest with a minimal difference (usually 1). It fits constraints (n ≤ 10⁴) perfectly and is straightforward once you see the pattern. It’s like weaving a sequence with just the right gaps!

How It Works

Think of this as a difference weaver:

• Step 1: Understand Differences:
• Max distinct differences = n-1 (e.g., n=3: [1, 3, 2] gives 2).
• Min = 1 (e.g., [1, 2, 3]).
• We need exactly k.
• Step 2: Construct Array:
• Use two pointers: low (1) and high (n).
• For first k differences:
• Alternate high and low to get k-1 large differences (n-1 down to n-k+1).
• Fill rest with remaining numbers in order (difference 1).
• Step 3: Return Result:
• Array with exactly k distinct differences.

It’s like a gap crafter—alternate and fill!

Step-by-Step Example

Example: n = 5, k = 3

• Step 1: n-1 = 4 max differences, k = 3.
• Step 2: Construct:
• Start: low = 1, high = 5.
• k=3 needs 2 large differences + 1 small:
• Add 1 (low), arr = [1].
• Add 5 (high), arr = [1, 5], diff = [4].
• Add 2 (low+1), arr = [1, 5, 2], diff = [4, 3].
• Fill rest (3, 4):
• Add 4, arr = [1, 5, 2, 4], diff = [4, 3, 2].
• Add 3, arr = [1, 5, 2, 4, 3], diff = [4, 3, 2, 1].
• Distinct = {4, 3, 2}, k = 3.
• Step 3: Return [1, 5, 2, 4, 3].
• Output: [1, 5, 2, 4, 3].

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained clearly:

Copy codeclass Solution:
    def constructArray(self, n: int, k: int) -> List[int]:
        # Step 1: Initialize result array
        result = []
        low = 1
        high = n

        # Step 2: Construct k distinct differences
        for i in range(k - 1):  # k-1 alternations
            if i % 2 == 0:
                result.append(low)
                low += 1
            else:
                result.append(high)
                high -= 1

        # Fill remaining with ascending order
        if k % 2 == 0:  # Last was high, reverse order
            for i in range(high, low - 1, -1):
                result.append(i)
        else:  # Last was low, ascending order
            for i in range(low, high + 1):
                result.append(i)

        # Step 3: Return result
        return result

• Lines 4-6: Init: Empty array, low=1, high=n.
• Lines 9-15: Construct:
• Alternate low and high for k-1 differences.
• Lines 18-23: Fill:
• If k even, descending; if odd, ascending.
• Line 26: Return array.
• Time Complexity: O(n)—single pass to build array.
• Space Complexity: O(n)—result array.

This is like an array designer—weave and complete!

Alternative Solution: Greedy with Adjustment

Why an Alternative Approach?

The greedy with adjustment approach builds the array incrementally—O(n) time, O(n) space. It’s more intuitive, starting with a simple sequence and adjusting to hit k, but requires tweaking to ensure correctness. It’s like starting with a basic pattern and nudging it to fit!

How It Works

Picture this as a difference nudger:

• Step 1: Start with ascending array (1 diff).
• Step 2: Greedily increase differences:
• Swap or adjust elements to add new differences.
• Stop at k distinct values.
• Step 3: Return result.

It’s like a gap adjuster—start and tweak!

Step-by-Step Example

Example: n = 5, k = 3

• Step 1: Start: [1, 2, 3, 4, 5], diff = [1], 1 distinct.
• Step 2: Adjust:
• Swap 2 and 5: [1, 5, 3, 4, 5], diff = [4, 2, 1, 1], 3 distinct.
• Step 3: Return [1, 5, 3, 4, 5].
• Output: [1, 5, 3, 4, 5].

Code for Greedy Approach

Copy codeclass Solution:
    def constructArray(self, n: int, k: int) -> List[int]:
        # Step 1: Start with ascending array
        result = list(range(1, n + 1))

        # Step 2: Greedily adjust for k differences
        diff_set = {1}  # Initial difference
        left = 1
        right = n - 1

        while len(diff_set) < k and left < right:
            # Swap to introduce new difference
            result[left], result[right] = result[right], result[left]
            new_diff = abs(result[left] - result[left - 1])
            diff_set.add(new_diff)
            left += 1
            right -= 1

        # Step 3: Return result
        return result

• Line 4: Start: [1, 2, ..., n].
• Lines 7-16: Adjust:
• Swap ends inward, add new differences until k reached.
• Line 19: Return array.
• Time Complexity: O(n)—single pass with swaps.
• Space Complexity: O(n)—array and set.

It’s a greedy tweaker—adjust and fit!

Comparing the Two Solutions

• Constructive (Best):
• Pros: O(n) time, O(n) space, guaranteed k differences.
• Cons: Pattern less intuitive.
• Greedy (Alternative):
• Pros: O(n) time, O(n) space, simpler concept.
• Cons: May need tuning for exact k.

Constructive wins for precision.

Additional Examples and Edge Cases

• Input: n = 2, k = 1
• Output: [1, 2].
• Input: n = 4, k = 2
• Output: [1, 4, 2, 3] (Differences: [3, 2]).

Constructive handles these well.

Complexity Breakdown

• Constructive: Time O(n), Space O(n).
• Greedy: Time O(n), Space O(n).

Constructive is optimal for control.

Key Takeaways

• Constructive: Pattern crafting—smart!
• Greedy: Incremental tweaking—clear!
• Differences: Arranging is fun.
• Python Tip: Loops rock—see Python Basics.

Final Thoughts: Arrange That Array

LeetCode 667: Beautiful Arrangement II in Python is a fun arrangement challenge. Constructive pattern offers precision and speed, while greedy adjustment provides an intuitive alternative. Want more? Try LeetCode 561: Array Partition or LeetCode 628: Maximum Product of Three Numbers. Ready to arrange? Head to Solve LeetCode 667 on LeetCode and craft that beautiful array today!