Python, Straightforward with Explanation

  • 9

    When k = n-1, a valid construction is [1, n, 2, n-1, 3, n-2, ....]. One way to see this is, we need to have a difference of n-1, which means we need 1 and n adjacent; then, we need a difference of n-2, etc.

    This leads to the following idea: we will put [1, 2, ...., n-k-1] first, and then we have N = k+1 adjacent numbers left, of which we want k different differences. This is just the answer above translated by n-k-1: we'll put [n-k, n, n-k+1, n-1, ....] after.

    def constructArray(self, n, k):
        ans = range(1, n - k)
        for d in xrange(k+1):
            if d % 2 == 0:
                ans.append(n-k + d/2)
                ans.append(n - d/2)
        return ans

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.