Stepping Numbers Editorial

Practice Problem Link: Stepping Numbers

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given two numbers begin and end, find all the stepping numbers in the range [begin, end]. A positive integer is called a stepping number if the adjacent digits have a difference of 1. All single-digit numbers are stepping numbers. 123, 121, 654, 5 are all stepping numbers. 124, 122, 46 are not stepping numbers.

Naive Approach

We can iterate over all the numbers in the range [begin, end] and check if each number is a “Stepping Number” or not.

Analysis

• Time Complexity: O((begin - end + 1) * log (numbers in the range))
• Space Complexity: O(1)

Implementation

C++

bool isStepping(int n){
	string digits = to_string(n);
	int len = digits.size();
	for(int i = 1; i < len; i++) {
		if(abs(digits[i] - digits[i - 1]) != 1) {
			return false;
		}
	}
	return true;
}
vector<int> getSteppingNumbers(int begin, int end) {
	vector<int> answer;
	for(int i = begin; i <= end; i++) {
		if(isStepping(i)) {
			answer.push_back(i);
		}
	}
	return answer;
}

Java

class Solution {
	boolean isStepping(int n) {
		String digits = Integer.toString(n);
		int len = digits.length();
		for(int i = 1; i < len; i++) {
			if(Math.abs(digits.charAt(i) - digits.charAt(i - 1)) != 1) {
				return false;
			}
		}
		return true;
	}
	List<Integer> getSteppingNumbers(int begin, int end) {
		List<Integer> answer = new ArrayList<>();
		for(int i = begin; i <= end; i++) {
			if(isStepping(i)) {
				answer.add(i);
			}
		}
		return answer;
	}
}

Optimal Approach:

We will try to model this problem into a graph traversal problem. Consider that the starting node is 0, and from it, we try to move to all possible reachable nodes in our given range. 

• From 0, we can move to 1, 2, 3, 4,…, 9
• From 1, we can move to 12, 10
• From 2, we can move to 23, 21
• And so on….

In this manner we can traverse on the reachable nodes and store those which are in our range. As soon as we go outside our range, we break the iteration.

Analysis:

• Time Complexity: O(n)
• Space Complexity: O(n)

Implementation:

C++

vector<int> getSteppingNumbers(int begin, int end) {
	int initialValue[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
	vector<int> answer;
	queue<int> q;
	for(int i = 1; i <= 9; i++) {
		q.push(i);
	}
	if(begin == 0) {
		answer.push_back(begin);
	}
	while(!q.empty()) {
		int node = q.front();
		q.pop();
		if(node >= begin && node <= end) {
			answer.push_back(node);
		}
		int child, lastDigit = node % 10;
		node *= 10;
		if(lastDigit) {
			child = node + initialValue[lastDigit - 1];
			if(child <= end) {
				q.push(child);
			}
		}
		if(lastDigit != 9) {
			child = node + initialValue[lastDigit + 1];
			if(child <= end) {
				q.push(child);
			}
		}
	}
	return answer;
}

 Java

class Solution {
	List<Integer> getSteppingNumbers(int begin, int end) {
    	int initialValue[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
		List<Integer> answer = new ArrayList<>();
		Queue<Integer> q = new LinkedList<>();
		for(int i = 1; i <= 9; i++) {
			q.add(i);
		}
		if(begin == 0) {
			answer.add(begin);
		}
		while(!q.isEmpty()) {
			int node = q.poll();
			if(node >= begin && node <= end) {
				answer.add(node);
			}
			int child, lastDigit = node % 10;
			node *= 10;
			if(lastDigit != 0) {
				child = node + initialValue[lastDigit - 1];
				if(child <= end) {
					q.add(child);
				}
			}
			if(lastDigit != 9) {
				child = node + initialValue[lastDigit + 1];
				if(child <= end) {
					q.add(child);
				}
			}
		}
		return answer;
	}
}