7 lines, No special case code, O(n)/O(1)

  • 4

    I use window [a, b, c], initialized to [0, k, k*k], the answers for n=0, 1 and 2. Shift it n steps and then return a. Takes O(n) time and O(1) space.

    Using a window of three elements rather than the usual two elements allows me to handle the case n=0 without special case code (the if (n==0) return 0; you can see in almost every solution). And shifting a two-element window is usually done with a temporary third variable anyway. I just make that third variable more valuable.

    int numWays(int n, int k) {
        int a = 0, b = k, c = k*k;
        while (n--) {
            a = b;
            b = c;
            c = (a + b) * (k - 1);
        return a;

    For an explanation of the computation, look for example here.

Log in to reply

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