Last updated on January 12th, 2025 at 03:48 am
Here, we see a Beautiful Arrangement II LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.
List of all LeetCode Solution
Topics
Array
Companies
Level of Question
Medium
Beautiful Arrangement II LeetCode Solution
Table of Contents
1. Problem Statement
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 = [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 are 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.
2. Coding Pattern Used in Solution
The coding pattern used in this code is “Greedy Algorithm”. The problem involves constructing an array with specific properties (distinct absolute differences between adjacent elements). The solution greedily constructs the array by alternating between the smallest and largest available numbers to achieve the desired differences.
3. Code Implementation in Different Languages
3.1 Beautiful Arrangement II C++
class Solution {
public:
vector<int> constructArray(int n, int k) {
int diff = n - k;
int lo = 1;
int hi = n;
vector<int> out;
int i = 0;
while(i < diff){
out.push_back(lo);
lo++;
i++;
}
bool flag = true;
for(int i = out.size() ; i < n ; i++){
if(flag){
out.push_back(hi);
hi--;
flag = false;
}
else{
out.push_back(lo);
lo++;
flag = true;
}
}
return out;
}
};
3.2 Beautiful Arrangement II Java
class Solution {
public int[] constructArray(int n, int k) {
int diff = n - k;
int lo = 1;
int hi = n;
int[] out = new int[n];
int i = 0;
while(i < diff){
out[i] = lo;
lo++;
i++;
}
boolean flag = true;
for( ; i < n ; i++){
if(flag){
out[i] = hi;
hi--;
flag = false;
}
else{
out[i] = lo;
lo++;
flag = true;
}
}
return out;
}
}
3.3 Beautiful Arrangement II JavaScript
var constructArray = function(n, k) {
let ans = new Array(n)
for (let i = 0, a = 1, z = k + 1; i <= k; i++)
ans[i] = i % 2 ? z-- : a++
for (let i = k + 1; i < n;)
ans[i] = ++i
return ans
};
3.4 Beautiful Arrangement II Python
class Solution(object):
def constructArray(self, n, k):
ans, a, z = [0] * n, 1, k + 1
for i in range(k+1):
if i % 2:
ans[i] = z
z -= 1
else:
ans[i] = a
a += 1
for i in range(k+1,n):
ans[i] = i + 1
return ans
4. Time and Space Complexity
| Time Complexity | Space Complexity | |
| C++ | O(n) | O(n) |
| Java | O(n) | O(n) |
| JavaScript | O(n) | O(n) |
| Python | O(n) | O(n) |
- The Greedy Algorithm ensures that the array satisfies the constraints by alternating between the smallest and largest available numbers.
- The time complexity is linear (
O(n)) because the loops iterate at mostntimes. - The space complexity is linear (
O(n)) because an array or vector of sizenis used to store the result.