We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Beautiful Arrangement II

Difficulty: Medium

Problem Description

Given two integers n and k, construct a list answer that contains n different positive integers ranging from 1 to n and obeys the requirement that the list [|a1 - a2|, |a2 - a3|, |a3 - a4|, ... , |an-1 - an|] has exactly k distinct integers.

Key Insights

  • The absolute differences between consecutive elements must yield exactly k distinct values.
  • To achieve k distinct differences, we can use a pattern that alternates between the smallest and largest available numbers.
  • For k distinct differences, we can systematically place the numbers to ensure that the differences are maximized while still being in the range of allowable values.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

To solve this problem, we can create a sequence by placing the smallest and largest numbers alternately. This ensures that we create distinct absolute differences. We start by placing the first number as 1, then the last number n, then the second number 2, then the second last number n-1, and so on, until we fill in the entire list. This pattern guarantees that we will have k distinct absolute differences.

Code Solutions

def construct_arrangement(n, k):
    answer = []
    left, right = 1, n
    for i in range(1, n + 1):
        if i % 2 == 1:
            answer.append(left)
            left += 1
        else:
            answer.append(right)
            right -= 1
    return answer

# Example usage
print(construct_arrangement(3, 2))  # Output can be [1, 3, 2] or any valid arrangement
← Back to All Questions