Stepping Numbers

Given N and M find all stepping numbers in range N to M

The stepping number:

A number is called as a stepping number if the adjacent digits have a difference of 1.
e.g 123 is stepping number, but 358 is not a stepping number

Example:

N = 10, M = 20
all stepping numbers are 10 , 12 

Return the numbers in sorted order.

public class Solution {
    public ArrayList<Integer> stepnum(int A, int B) {
        ArrayList<Integer> res = new ArrayList<>();
        if (A > B)
            return res;
        Queue<Integer> q = new ArrayDeque<>();
        for (int i = 1; i <= 9; i++)
            q.add(i);
        if (A == 0)
            res.add(0);
        while (!q.isEmpty()) {
            int p = q.poll();
            if (p < B) {
                int lastDigit = p % 10;
                // Adding both possibilities in queue if possible
                if (lastDigit > 0)
                    q.add(p * 10 + lastDigit - 1);
                if (lastDigit < 9)
                    q.add(p * 10 + lastDigit + 1);
            }
            if (p >= A && p <= B)
                res.add(p);
        }
        return res;
    }
}

Last updated