Jobs

Interviews

Discussions

Beautiful Arrangement II

Medium

Asked by:

4 views

Topics:

Arrays

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 = [a₁, a₂, a₃, ... , a_n], then the list [|a₁ - a₂|, |a₂ - a₃|, |a₃ - a₄|, ... , |a_n-1 - a_n|] 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 <= 10⁴

Try coding it in LeetCode

Beautiful Arrangement II

Medium

Asked by:

4 views

Topics:

Arrays

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 = [a₁, a₂, a₃, ... , a_n], then the list [|a₁ - a₂|, |a₂ - a₃|, |a₃ - a₄|, ... , |a_n-1 - a_n|] 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 <= 10⁴

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on `n` and `k`? Specifically, what are the maximum and minimum possible values for each?
If it's impossible to create an array with exactly `k` distinct differences, what should the function return? Should I throw an error, or return an empty array?
Is 'distinct differences' based on absolute differences between adjacent elements (i.e., `|arr[i+1] - arr[i]|`)?
If multiple valid arrays exist, is any valid arrangement acceptable, or is there a specific arrangement that should be preferred?
Are `n` and `k` always positive integers?

Brute Force Solution

Approach

For this arrangement problem, the brute force method involves trying all possible arrangements. We essentially explore every single way to order the numbers to see if any of them satisfy the given condition about the number of distinct differences.

Here's how the algorithm would work step-by-step:

Start by generating every possible order of the numbers from 1 up to the number we're given.
For each of these orders, calculate the differences between consecutive numbers in the arrangement.
Count how many unique difference values you find in each arrangement.
If the number of unique differences in an arrangement matches the target number of distinct differences we were given, then we've found a valid arrangement.
If, after checking every single arrangement, we find one that works, we return it. If none work, then there's likely an issue with the input, but we can only conclude no solution was found.

Code Implementation

import itertools

def beautiful_arrangement_brute_force(number, distinct_differences):
    numbers = list(range(1, number + 1))
    all_permutations = itertools.permutations(numbers)

    for permutation in all_permutations:
        # Check each permutation for distinct differences
        differences = []
        for i in range(len(permutation) - 1):
            differences.append(abs(permutation[i] - permutation[i + 1]))

        distinct_differences_count = len(set(differences))

        # If the number of distinct differences matches, return
        if distinct_differences_count == distinct_differences:
            return list(permutation)

    return []

Big(O) Analysis

Time Complexity

O(n * n!) – The brute force approach involves generating all permutations of numbers from 1 to n, which takes O(n!) time. For each permutation, we iterate through the arrangement to calculate the differences between consecutive numbers. This iteration takes O(n) time. Therefore, the overall time complexity is O(n * n!).

Space Complexity

O(N!) – The brute force solution generates every possible permutation of numbers from 1 to n. Generating all permutations will require storing all possible arrangements. In the worst case, we'll need to store all N! possible permutations before finding a valid one. Thus, the auxiliary space needed for storing the permutations is proportional to N!, resulting in O(N!) space complexity.

Optimal Solution

Approach

The goal is to construct a sequence of numbers such that the absolute differences between consecutive numbers produces a specific number of unique values. The optimal strategy involves strategically interleaving large and small numbers to create the desired number of distinct differences, then filling in the remaining numbers sequentially.

Here's how the algorithm would work step-by-step:

Begin by placing the smallest and largest numbers, then alternate between placing the next smallest and next largest until the required number of distinct differences is achieved.
Once the desired number of distinct differences is reached, fill in the remaining numbers in a sequential manner, either ascending or descending, depending on the last number placed.
This interleaving ensures the initial part of the sequence contributes to the required differences, while the sequential filling avoids creating new distinct differences.

Code Implementation

def beautiful_arrangement_ii(number_of_elements, distinct_differences):
    result = []
    left_pointer = 1
    right_pointer = number_of_elements

    # Interleave small and large numbers.
    for i in range(distinct_differences):
        if i % 2 == 0:
            result.append(left_pointer)
            left_pointer += 1
        else:
            result.append(right_pointer)
            right_pointer -= 1

    # Append the remaining numbers.
    if distinct_differences % 2 == 0:
        # Fill remaining nums ascending if needed
        for i in range(left_pointer, right_pointer + 1):
            result.append(i)

    else:
        # Fill remaining nums descending if needed
        for i in range(right_pointer, left_pointer - 1, -1):
            result.append(i)

    return result

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input range from 1 to n. The first part of the algorithm interleaves elements to generate k distinct differences, which takes at most n steps. The second part fills in the remaining elements sequentially, which also takes at most n steps. Therefore, the time complexity is proportional to n, making it O(n).

Space Complexity

O(N) – The algorithm constructs a list of size N to store the beautiful arrangement. While the algorithm uses variables like 'low' and 'high', their space is constant. The primary driver of space complexity is the creation of the resulting array which holds N integers, hence the space complexity is O(N).

Edge Cases

Case	How to Handle
k is zero	Return an ascending list from 1 to n when k is 0, as no distinct differences are needed.
k is equal to n-1	Create a list with maximal alternating differences (1, n, 2, n-1, ...).
n is 1	Return a list containing only the element 1.
k is greater than or equal to n	The maximum possible distinct differences is n-1, so treat k as n-1 in this case.
n is a large number close to integer limit	Ensure no integer overflow occurs during calculations, especially with indexing.
n is a small number (e.g., n=2) and k=1	Return [1, 2] which has a distinct difference of 1.
Multiple valid solutions exist	The algorithm should produce any one of the valid solutions; order is not significant as long as the k distinct differences are achieved.
k is 1	Return a simple ascending sequence [1, 2, 3, ..., n] as the differences will all be 1.

k is zero

How to Handle:

Return an ascending list from 1 to n when k is 0, as no distinct differences are needed.

k is equal to n-1

How to Handle:

Create a list with maximal alternating differences (1, n, 2, n-1, ...).

n is 1

How to Handle:

Return a list containing only the element 1.

k is greater than or equal to n

How to Handle:

The maximum possible distinct differences is n-1, so treat k as n-1 in this case.

n is a large number close to integer limit

How to Handle:

Ensure no integer overflow occurs during calculations, especially with indexing.

n is a small number (e.g., n=2) and k=1

How to Handle:

Return [1, 2] which has a distinct difference of 1.

Multiple valid solutions exist

How to Handle:

The algorithm should produce any one of the valid solutions; order is not significant as long as the k distinct differences are achieved.

k is 1

How to Handle:

Return a simple ascending sequence [1, 2, 3, ..., n] as the differences will all be 1.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on `n` and `k`? Specifically, what are the maximum and minimum possible values for each?
If it's impossible to create an array with exactly `k` distinct differences, what should the function return? Should I throw an error, or return an empty array?
Is 'distinct differences' based on absolute differences between adjacent elements (i.e., `|arr[i+1] - arr[i]|`)?
If multiple valid arrays exist, is any valid arrangement acceptable, or is there a specific arrangement that should be preferred?
Are `n` and `k` always positive integers?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start by generating every possible order of the numbers from 1 up to the number we're given.
For each of these orders, calculate the differences between consecutive numbers in the arrangement.
Count how many unique difference values you find in each arrangement.
If the number of unique differences in an arrangement matches the target number of distinct differences we were given, then we've found a valid arrangement.
If, after checking every single arrangement, we find one that works, we return it. If none work, then there's likely an issue with the input, but we can only conclude no solution was found.

Code Implementation

import itertools

def beautiful_arrangement_brute_force(number, distinct_differences):
    numbers = list(range(1, number + 1))
    all_permutations = itertools.permutations(numbers)

    for permutation in all_permutations:
        # Check each permutation for distinct differences
        differences = []
        for i in range(len(permutation) - 1):
            differences.append(abs(permutation[i] - permutation[i + 1]))

        distinct_differences_count = len(set(differences))

        # If the number of distinct differences matches, return
        if distinct_differences_count == distinct_differences:
            return list(permutation)

    return []

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Begin by placing the smallest and largest numbers, then alternate between placing the next smallest and next largest until the required number of distinct differences is achieved.
Once the desired number of distinct differences is reached, fill in the remaining numbers in a sequential manner, either ascending or descending, depending on the last number placed.
This interleaving ensures the initial part of the sequence contributes to the required differences, while the sequential filling avoids creating new distinct differences.

Code Implementation

def beautiful_arrangement_ii(number_of_elements, distinct_differences):
    result = []
    left_pointer = 1
    right_pointer = number_of_elements

    # Interleave small and large numbers.
    for i in range(distinct_differences):
        if i % 2 == 0:
            result.append(left_pointer)
            left_pointer += 1
        else:
            result.append(right_pointer)
            right_pointer -= 1

    # Append the remaining numbers.
    if distinct_differences % 2 == 0:
        # Fill remaining nums ascending if needed
        for i in range(left_pointer, right_pointer + 1):
            result.append(i)

    else:
        # Fill remaining nums descending if needed
        for i in range(right_pointer, left_pointer - 1, -1):
            result.append(i)

    return result

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
k is zero	Return an ascending list from 1 to n when k is 0, as no distinct differences are needed.
k is equal to n-1	Create a list with maximal alternating differences (1, n, 2, n-1, ...).
n is 1	Return a list containing only the element 1.
k is greater than or equal to n	The maximum possible distinct differences is n-1, so treat k as n-1 in this case.
n is a large number close to integer limit	Ensure no integer overflow occurs during calculations, especially with indexing.
n is a small number (e.g., n=2) and k=1	Return [1, 2] which has a distinct difference of 1.
Multiple valid solutions exist	The algorithm should produce any one of the valid solutions; order is not significant as long as the k distinct differences are achieved.
k is 1	Return a simple ascending sequence [1, 2, 3, ..., n] as the differences will all be 1.

k is zero

How to Handle:

Return an ascending list from 1 to n when k is 0, as no distinct differences are needed.

k is equal to n-1

How to Handle:

Create a list with maximal alternating differences (1, n, 2, n-1, ...).

n is 1

How to Handle:

Return a list containing only the element 1.

k is greater than or equal to n

How to Handle:

The maximum possible distinct differences is n-1, so treat k as n-1 in this case.

n is a large number close to integer limit

How to Handle:

Ensure no integer overflow occurs during calculations, especially with indexing.

n is a small number (e.g., n=2) and k=1

How to Handle:

Return [1, 2] which has a distinct difference of 1.

Multiple valid solutions exist

How to Handle:

The algorithm should produce any one of the valid solutions; order is not significant as long as the k distinct differences are achieved.

k is 1

How to Handle:

Return a simple ascending sequence [1, 2, 3, ..., n] as the differences will all be 1.