Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/667.html

667. Beautiful Arrangement II (Medium)

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.

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.

Note:

  1. The n and k are in the range 1 <= k < n <= 104.

Related Topics:
Array

Similar Questions:

Solution 1.

  • class Solution {
    public int[] constructArray(int n, int k) {
        int[] sorted = new int[n];
        for (int i = 0; i < n; i++)
            sorted[i] = i + 1;
        int[] arrangement = new int[n];
        int low = 0, high = k;
        for (int i = 0; i <= k; i++) {
            if (i % 2 == 0)
                arrangement[i] = sorted[low++];
            else
                arrangement[i] = sorted[high--];
        }
        for (int i = k + 1; i < n; i++)
            arrangement[i] = sorted[i];
        return arrangement;
    }
}

############

class Solution {
    public int[] constructArray(int n, int k) {
        int l = 1, r = n;
        int[] ans = new int[n];
        for (int i = 0; i < k; ++i) {
            ans[i] = i % 2 == 0 ? l++ : r--;
        }
        for (int i = k; i < n; ++i) {
            ans[i] = k % 2 == 0 ? r-- : l++;
        }
        return ans;
    }
}

  • // OJ: https://leetcode.com/problems/beautiful-arrangement-ii/
// Time: O(N)
// Space: O(1)
class Solution {
public:
    vector<int> constructArray(int n, int k) {
        vector<int> ans(n);
        for (int i = 0, val = 1, diff = k, dir = 1; i < n; ++i) {
            ans[i] = val;
            if (diff == 0) {
                dir = 0;
                val = 2 + k;
                diff = 1; // any non-zero value
            } else if (dir) {
                val += diff * dir;
                --diff;
                dir = -dir;
            } else ++val;
        }
        return ans;
    }
};

  • class Solution:
    def constructArray(self, n: int, k: int) -> List[int]:
        l, r = 1, n
        ans = []
        for i in range(k):
            if i % 2 == 0:
                ans.append(l)
                l += 1
            else:
                ans.append(r)
                r -= 1
        for i in range(k, n):
            if k % 2 == 0:
                ans.append(r)
                r -= 1
            else:
                ans.append(l)
                l += 1
        return ans

############

class Solution(object):
    def constructArray(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: List[int]
        """
        a = list(range(1, n + 1))
        for i in range(1, k):
            a[i:] = a[:i-1:-1]
        return a

  • func constructArray(n int, k int) []int {
	l, r := 1, n
	ans := make([]int, n)
	for i := 0; i < k; i++ {
		if i%2 == 0 {
			ans[i] = l
			l++
		} else {
			ans[i] = r
			r--
		}
	}
	for i := k; i < n; i++ {
		if k%2 == 0 {
			ans[i] = r
			r--
		} else {
			ans[i] = l
			l++
		}
	}
	return ans
}

  • function constructArray(n: number, k: number): number[] {
    let l = 1;
    let r = n;
    const ans = new Array(n);
    for (let i = 0; i < k; ++i) {
        ans[i] = i % 2 == 0 ? l++ : r--;
    }
    for (let i = k; i < n; ++i) {
        ans[i] = k % 2 == 0 ? r-- : l++;
    }
    return ans;
}

All Problems

All Solutions