Counting the Stepping Numbers between A Range using Depth/Breadth First Search Algorithm

A Stepping Number is an integer such that all of its adjacent digits have an absolute difference of exactly 1. For example, 321 is a Stepping Number while 421 is not. Given two integers low and high, find and return a sorted list of all the Stepping Numbers in the range [low, high] inclusive.

Example 1:
Input: low = 0, high = 21
Output: [0,1,2,3,4,5,6,7,8,9,10,12,21]

Constraints:
0 <= low <= high <= 2 * 10^9

Hints:
Try to generate the numbers using recursion.
In one step in the recursion, add a valid digit to the right of the current number.
Save the number if it’s in the range between low and high.

Bruteforcing the Stepping Numbers

The intutive solution would be to bruteforce the numbers within the range and check each one if it is a stepping number.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
public:
    vector<int> countSteppingNumbers(int low, int high) {
        vector<int> res;
        for (int i = low; i <= high; ++ i) {
            if (good(i)) {
                res.push_back(i);
            }
        }
        return res;
    }
private:
    bool good(int n) {
        int prev = -999;
        while (n > 0) {
            int x = n % 10;
            if ((prev >= 0) && (abs(prev - x) != 1)) return false;
            n /= 10;
            prev = x;
        }
        return true;
    }
};

class Solution {
public:
    vector<int> countSteppingNumbers(int low, int high) {
        vector<int> res;
        for (int i = low; i <= high; ++ i) {
            if (good(i)) {
                res.push_back(i);
            }
        }
        return res;
    }
private:
    bool good(int n) {
        int prev = -999;
        while (n > 0) {
            int x = n % 10;
            if ((prev >= 0) && (abs(prev - x) != 1)) return false;
            n /= 10;
            prev = x;
        }
        return true;
    }
};

The complexity would be O(H – L) where this could be a huge number. As the numbers are limited to 32-bit signed integer. The checking function e.g. good() takes constant time.

Depth First Search to Generate the Stepping Numbers

The bruteforce is slow, as we are listing all numbers most of which are not stepping numbers – and they require checking as well. We can, however, generate the stepping numbers from one digit, until they are bigger than the range.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
public:
    vector<int> countSteppingNumbers(int low, int high) {
        vector<int> res;
        if (0 >= low) res.push_back(0);
        for (int i = 1; i <= 9; ++ i) {
            dfs(res, low, high, i);
        }
        sort(begin(res), end(res));
        return res;
    }
    
    void dfs(vector<int> &res, int64_t low, int64_t high, int64_t cur) {
        if (cur > high) return;
        if (cur >= low) res.push_back(cur);
        int x = cur % 10;
        if (x < 9) {
            dfs(res, low, high, (cur * 10) + x + 1);
        }
        if (x > 0) {
            dfs(res, low, high, (cur * 10) + x - 1);
        }
    }
};

class Solution {
public:
    vector<int> countSteppingNumbers(int low, int high) {
        vector<int> res;
        if (0 >= low) res.push_back(0);
        for (int i = 1; i <= 9; ++ i) {
            dfs(res, low, high, i);
        }
        sort(begin(res), end(res));
        return res;
    }
    
    void dfs(vector<int> &res, int64_t low, int64_t high, int64_t cur) {
        if (cur > high) return;
        if (cur >= low) res.push_back(cur);
        int x = cur % 10;
        if (x < 9) {
            dfs(res, low, high, (cur * 10) + x + 1);
        }
        if (x > 0) {
            dfs(res, low, high, (cur * 10) + x - 1);
        }
    }
};

Zero is a stepping number and will be added first if it falls in range. Then, we can generate stepping numbers of 1 digit, and every recursive DFS call, will put a valid digit to the end – which makes a new stepping number.

The Depth First Search with Zero value passed in will result a duplicate search as same as starting from 1. As the input is limited to 32-bit signed integer, the algorithm complexity for above DFS is constant. Roughly complexity analysis is: 9x2x2x2x2x2x2x2x2x2 – which is trivial to enumerate. However, as we need to sort the results, the overall complexity is O(N.LogN) where N is the number of the stepping numbers within the range.

Breadth First Search to Generate the Stepping Numbers

We need to sort the numbers after DFS, but if we conduct a Breadth First Search, the sorting may not be necessary as we are always expanding the numbers from the smallest to the biggest – in other words, the BFS preserves the number ordering. We just need to make sure the smaller branch is pushed first. For example, At node “12”, the next node would be “121”, and then “123”.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution {
public:
    vector<int> countSteppingNumbers(int low, int high) {
        vector<int> res;
        if (0 >= low) res.push_back(0);
        queue<int> Q;
        for (int i = 1; i <= 9; ++ i) {
            Q.push(i);
        }
        while (!Q.empty()) {
            auto p = Q.front();
            Q.pop();
            if (p <= high / 10) {
                int x = p % 10;
                if (x > 0) {
                    Q.push(p * 10 + (p % 10 - 1));
                }
                if (x < 9) {
                    Q.push(p * 10 + (p % 10 + 1));
                }
            }
            if ((p >= low) && (p <= high)) {
                res.push_back(p);
            }
        }
        return res;
    }
};

class Solution {
public:
    vector<int> countSteppingNumbers(int low, int high) {
        vector<int> res;
        if (0 >= low) res.push_back(0);
        queue<int> Q;
        for (int i = 1; i <= 9; ++ i) {
            Q.push(i);
        }
        while (!Q.empty()) {
            auto p = Q.front();
            Q.pop();
            if (p <= high / 10) {
                int x = p % 10;
                if (x > 0) {
                    Q.push(p * 10 + (p % 10 - 1));
                }
                if (x < 9) {
                    Q.push(p * 10 + (p % 10 + 1));
                }
            }
            if ((p >= low) && (p <= high)) {
                res.push_back(p);
            }
        }
        return res;
    }
};

The BFS is thus better than DFS in this particular problem as it does not involve the sorting. The overall performance complexity is O(1) constant, and O(N) space.

–EOF (The Ultimate Computing & Technology Blog) —