667. Beautiful Arrangement II
Description
Given two integers n
and k
, you need to construct a list which contains n
different positive integers ranging from 1
to n
and obeys the following requirement:
Suppose this list is [a1, a2, a3, ... , an], then the list [|a1 - a2|, |a2 - a3|, |a3 - a4|, ... , |an-1 - an|] has exactly k
distinct integers.
If there are multiple answers, print any of them.
Constraints
The
n
andk
are in the range 1 <= k < n <= 104.
Approach
Links
GeeksforGeeks
ProgramCreek
Examples
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.
Solutions
/**
* Time complexity : O(N)
* Space complexity : O(N)
*/
class Solution {
public int[] constructArray(int n, int k) {
int[] result = new int[n];
int low = 1, high = n;
int index = 0;
result[index++] = low++;
boolean isHigh = false;
while(k > 1) {
result[index++] = high--;
k--;
isHigh = true;
if(k > 1) {
result[index++] = low++;
k--;
isHigh = false;
}
}
while(index < n) {
if(isHigh) {
result[index++] = high--;
} else {
result[index++] = low++;
}
}
return result;
}
}
Follow up
Last updated
Was this helpful?