LeetCode Daily Problem - 967. Numbers With Same Consecutive Differences

Problem

Return all non-negative integers of length n such that the absolute difference between every two consecutive digits is k.

Note that every number in the answer must not have leading zeros. For example, 01 has one leading zero and is invalid.

You may return the answer in any order.

Idea

The way to solve this is to construct the number digit by digit. We can pick any digit x from 1 through 9 as the first digit. Once we have picked the digit we have at most two valid choices x + k and x - k i.e. they both lie in [0, 9]. The problem then reduces to solving a smaller problem with similar structure, i.e. with one less digit at every step. When n digits have been picked we can add the number to our answer array.

Solution

class Solution {
    public void dfs (int NumOfDigits, int currNum, int k, List<Integer> ans) {
        if (NumOfDigits == 0) {
            ans.add(currNum);
            return;
        }

        List<Integer> nextDigits = new ArrayList<>();

        int tailDigit = currNum % 10;
        nextDigits.add(tailDigit + k);
        if(k != 0) {
            nextDigits.add(tailDigit - k);
        }

        for(int nextDigit : nextDigits) {
            if(0 <= nextDigit && nextDigit < 10) {
                int num = currNum * 10 + nextDigit;
                dfs(NumOfDigits - 1, num, k, ans);
            }
        }
    }

    public int[] numsSameConsecDiff(int n, int k) {
        if (n == 1) {
            return new int[] {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
        }

        List<Integer> ans = new LinkedList<Integer>();

        for (int i = 1; i < 10; i++) {
            dfs(n - 1, i, k, ans);
        }

        return ans.stream().mapToInt(i -> i).toArray();

    }
}

Runtime: 9 ms, faster than 21.14% of Java online submissions for Numbers With Same Consecutive Differences.

Memory Usage: 44.2 MB, less than 6.62% of Java online submissions for Numbers With Same Consecutive Differences.

Note - The BFS solution of this problem will be much more memory efficient as the recursion stack will not have to be dealt with.