Problem

Given two integers n and k, construct a list answer that contains n kxjdifferent 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.

Examples

Example 1

1
2
3

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

1
2
3

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 <= 10^4

Solution

Method 1 – Constructive Alternating High-Low

Intuition

The key idea is to create exactly k distinct absolute differences by alternating between the smallest and largest available numbers for the first k+1 positions, then filling the rest in order. This guarantees the required number of distinct differences.

Approach

  1. Initialize two pointers: l = 1 (left) and r = n (right).
  2. For the first k+1 elements, alternate picking from l and r:
    • If the current index is even, pick from l and increment l.
    • If odd, pick from r and decrement r.
  3. After k+1 elements, fill the rest with the remaining numbers in order (either ascending or descending, depending on the last pick).
  4. Return the constructed list.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
public:
   vector<int> constructArray(int n, int k) {
      vector<int> ans;
      int l = 1, r = n;
      for (int i = 0; i < k + 1; ++i) {
        if (i % 2 == 0) ans.push_back(l++);
        else ans.push_back(r--);
      }
      if ((k + 1) % 2 == 0) {
        for (int i = r; i >= l; --i) ans.push_back(i);
      } else {
        for (int i = l; i <= r; ++i) ans.push_back(i);
      }
      return ans;
   }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

func constructArray(n int, k int) []int {
   ans := make([]int, 0, n)
   l, r := 1, n
   for i := 0; i < k+1; i++ {
      if i%2 == 0 {
        ans = append(ans, l)
        l++
      } else {
        ans = append(ans, r)
        r--
      }
   }
   if (k+1)%2 == 0 {
      for i := r; i >= l; i-- {
        ans = append(ans, i)
      }
   } else {
      for i := l; i <= r; i++ {
        ans = append(ans, i)
      }
   }
   return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
   public int[] constructArray(int n, int k) {
      int[] ans = new int[n];
      int l = 1, r = n, idx = 0;
      for (int i = 0; i < k + 1; i++) {
        if (i % 2 == 0) ans[idx++] = l++;
        else ans[idx++] = r--;
      }
      if ((k + 1) % 2 == 0) {
        for (int i = r; i >= l; i--) ans[idx++] = i;
      } else {
        for (int i = l; i <= r; i++) ans[idx++] = i;
      }
      return ans;
   }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
   fun constructArray(n: Int, k: Int): IntArray {
      val ans = IntArray(n)
      var l = 1
      var r = n
      for (i in 0..k) {
        ans[i] = if (i % 2 == 0) l++ else r--
      }
      if ((k + 1) % 2 == 0) {
        for (i in r downTo l) ans[++k] = i
      } else {
        for (i in l..r) ans[++k] = i
      }
      return ans
   }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution:
   def constructArray(self, n: int, k: int) -> list[int]:
      ans: list[int] = []
      l, r = 1, n
      for i in range(k + 1):
        if i % 2 == 0:
           ans.append(l)
           l += 1
        else:
           ans.append(r)
           r -= 1
      if (k + 1) % 2 == 0:
        ans.extend(range(r, l - 1, -1))
      else:
        ans.extend(range(l, r + 1))
      return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

impl Solution {
   pub fn construct_array(n: i32, k: i32) -> Vec<i32> {
      let mut ans = Vec::with_capacity(n as usize);
      let (mut l, mut r) = (1, n);
      for i in 0..=k {
        if i % 2 == 0 {
           ans.push(l);
           l += 1;
        } else {
           ans.push(r);
           r -= 1;
        }
      }
      if (k + 1) % 2 == 0 {
        for i in (l..=r).rev() {
           ans.push(i);
        }
      } else {
        for i in l..=r {
           ans.push(i);
        }
      }
      ans
   }
}

Complexity

  • ⏰ Time complexity: O(n) — Each element is added once.
  • 🧺 Space complexity: O(n) — Output array of size n.