Python O(n) Clean and Fast solution


  • 0
    B

    Let 1..k be the k unique differences.
    Let this be the arrangement of differences:
    [k k-1 k-2 k-3 ... 1 1 1 1 1 1 1 1]
    Let the solution start at [1]

    The solution for for getting these differences would then be:
    [1 k+1 2 k 3 k-1 4 k-2 .. k+2 k+3 .. n]

    Example

    n=10, k=6
        1  7  2  6  3  5  4  8  9  10
    k  6 -5  4 -3  2 -1  0  0  0  0
    

    Solution

    class Solution(object):
        def constructArray(self, n, k):
            a = [1]
            h = k+1
            l = 2
            for _k in range(k,0,-2):
                if _k == 1:
                    a.append(h)
                    break
                else:
                    a.append(h)
                    a.append(l)
                h -= 1
                l += 1
            a.extend(range(k+2,n+1))
            return a
    

Log in to reply
 

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