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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Beautiful Arrangement II

Number: 667

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

Given two integers n and k, construct a list answer that contains n different positive integers from 1 to n such that the list of absolute differences of consecutive elements contains exactly k distinct values. Any valid answer is acceptable.

Key Insights

  • If k equals 1, a simple ascending (or descending) sequence meets the requirement because all adjacent differences are the same.
  • To achieve exactly k distinct differences, a zigzag (or alternating) arrangement is effective.
  • The idea is to first create a sequence with k+1 numbers that produces k distinct differences by alternating between the smallest and largest available numbers.
  • After constructing the first k+1 elements, the remaining numbers can be filled in sequentially without affecting the distinct difference count.

Space and Time Complexity

Time Complexity: O(n) - We iterate through the numbers once. Space Complexity: O(n) - We store the output in a list of size n.

Solution

We use a two-pointer technique. Start with two pointers: left at 1 and right at k+1. For the first k+1 elements, alternate between choosing the leftmost and the rightmost number to create maximum differences. This yields exactly k unique differences. Then, append the rest of the numbers sequentially from k+2 to n. This approach is efficient and constructs a valid solution satisfying the problem's requirements.

Code Solutions

# Python code solution
def constructArray(n: int, k: int) -> [int]:
    # Initialize the result list.
    answer = []
    left, right = 1, k + 1  # Set two pointers to create the initial zigzag.
    
    # Create the first part of the array with alternating values.
    for i in range(k + 1):
        if i % 2 == 0:
            answer.append(left)
            left += 1
        else:
            answer.append(right)
            right -= 1
            
    # Append the remaining numbers sequentially.
    for num in range(k + 2, n + 1):
        answer.append(num)
        
    return answer

# Example usage:
print(constructArray(3, 1))
print(constructArray(3, 2))
← Back to All Questions