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

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

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

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.

Example 3

Input: n = 9, k = 6

Output: [1, 9, 2, 8, 3, 7, 6, 5, 4]

Solutions

Solution 1

/**
 * 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