Welcome to Subscribe On Youtube

667. Beautiful Arrangement II

Description

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 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 <= 104

Solutions

• Java
• C++
• Python
• Go
• TypeScript

• 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;
      }
  }
  

• class Solution {
  public:
      vector<int> constructArray(int n, int k) {
          int l = 1, r = n;
          vector<int> ans(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;
      }
  };
  

• 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
  
  

• 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