Problem statement

https://leetcode.com/problems/beautiful-arrangement-ii/

Solution

Just create sentence 1,2, . . . , n-k, n, n-k+ 1, n-1, . . ., where we start to take biggest and smallest elements from place n-k. Let us consider case n = 14 and k = 6, then what [1,2,3,4,5,6,7,8,14,9,13,10,12,11]: then first differences are equal to 1, then we have differencese 6, -5, 4, -3, 2, -1, so in the end we will have absolute differences 1, 2, 3, 4, 5, 6.

Complexity

Time complexity is O(n), space as well to form output array

Code

class Solution:
    def constructArray(self, n, k):
        dr, diff = 1, k
        result = list(range(1, n-k+1))
        for i in range(k):
            result.append(result[-1] + dr*diff)
            dr *= -1
            diff -= 1      
        return result