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:
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 <= 104The 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.
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.
C++
Time Complexity: O(n), as we build the array in a single pass.
Space Complexity: O(n), for storing the answer.
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.
This JavaScript solution constructs the array first by filling straightforward values, then follows pattern-based alternate increments and decrements to fill in necessary distinct differences.
Java
Time Complexity: O(n), iterating through the elements.
Space Complexity: O(n), owing to the storage of results.
| Approach | Complexity |
|---|---|
| Two-Pointer Alternating Approach | Time Complexity: O(n), as we build the array in a single pass. |
| Pattern-Based Construct Increment Decrement | Time Complexity: O(n), iterating through the elements. |
How many LeetCode problems should you solve? #leetcode #techinterview #developer #softwareengineer • CrioDo • 304,607 views views
Watch 9 more video solutions →Practice Beautiful Arrangement II with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor