386. Lexicographical Numbers
Problem Description
The problem at hand is to generate a list of integers from 1 to n
and sort this list in lexicographical order. Lexicographical order is akin to how words are ordered in a dictionary, where the sequence is based on the alphabetical order of their component letters. When applied to numbers, it means ordering them as if they're strings, where '10' comes before '2' because '1' comes before '2' in the lexicographic sequence.
Constraints ensure that the algorithm is efficient, with the requirement being to run in linear time O(n)
, which means that the time taken to solve the problem should be directly proportional to the size of the input, without any nested iterations that would increase the time complexity. Additionally, the solution must use constant extra space O(1)
, excluding the output list, meaning the memory usage should not grow with the size of n
.
Flowchart Walkthrough
Let's analyze Lexicographical Numbers using the Flowchart. Here's a step-by-step walkthrough:
Is it a graph?
- No: This problem involves generating numbers in lexicographical order, which doesn't inherently involve a graph structure.
The flowchart in this situation stops here as it's explicitly designed to handle graph-related problems, thus not entirely applicable to lexicographical number generation.
However, to solve Leetcode 386 using Depth-First Search (DFS):
- We can consider each number as a node in an implied graph where each digit is a path leading to the next possible set of numbers.
- We can recursively explore deeper into each number by appending additional digits (considering the lexicographical constraints).
- We initiate the DFS from 1 to 9 and explore as deep as possible into each path before backtracking to explore the next possible path.
This approach mirrors the DFS exploration in implicit graphs formed by decision trees, successfully applying the Depth-First Search pattern in a non-traditional use case.
Intuition
The problem prompts us to think about the properties of numbers in lexicographical order. Upon closer inspection, we can observe a pattern akin to performing a depth-first search (DFS) on a tree, where each number is treated as a node, and its subsequent numbers are its children in tree-like form.
To use this approach, we start from 1 and explore as deep (as big a number) as we can by multiplying by 10 until we're still within bounds of n
. This is analogous to traversing down a branch of a tree. When we can't multiply by 10 anymore (either because we reach a number ending in 9 which can't have a digit appended or we exceed n
), we backtrack by dividing by 10, which simulates going up one level in the tree, and then we move to the next node by adding 1, which is like visiting the next sibling in the tree.
We repeat this process until we've visited all valid nodes (numbers from 1 to n
). Since we're visiting each number once, and every operation we're performing is constant time, the algorithm meets the time complexity requirement of O(n). Also, the only extra space used is for the output, with the variables inside the function using constant space, satisfying the space complexity constraint.
Applying this principle, the given solution efficiently constructs the lexicographical sequence without explicitly converting the numbers to strings, thereby avoiding the overhead of string manipulation and sorting, which would exceed the time complexity allowed.
Learn more about Depth-First Search and Trie patterns.
Solution Approach
The implementation uses a simple integer to keep track of the current number and appends it to the result list (acting as a stack) until we've constructed all numbers from 1
to n
in lexicographical order. Here's the step-by-step breakdown of the algorithm:
- Initialize
v
to 1 as we need to start constructing our numbers from the smallest positive integer. - Create an empty list
ans
that will contain our final sorted numbers. - Iterate
i
from 0 ton - 1
, which will allow us to fill inans
with the appropriaten
numbers. - During each iteration, append the current value of
v
toans
. - If
v
multiplied by 10 is less than or equal ton
, then replacev
withv * 10
. This step is like going deeper into the tree (taking a step to the next depth). - If we can't go deeper (either
v
has a last digit of 9 orv * 10
would exceedn
), we do the following to backtrack and find the next number to explore:- We use a
while
loop to keep dividingv
by 10 until we find a number that can have 1 added to it without exceedingn
or ending with a 9 (this is the backtracking step, where we essentially go up in the tree to explore other branches). - Once we find such a number, we increment
v
by 1 to move to the next possible number (next sibling in the tree).
- We use a
- Repeat steps 4 to 6 until all
n
numbers have been generated and added toans
. - Return the
ans
list, which now contains all numbers from 1 ton
sorted lexicographically.
The given solution can be linked to a depth-first search (DFS) algorithm in the following ways:
- Starting from 1 and exploring deeper numbers (
v * 10
) resembles visiting all child nodes in a path before backtracking. - Once we can't go deeper, we backtrack by dividing by 10, analogous to going up to a previous node in DFS.
- Incrementing
v
is like visiting the next node on the same level in DFS.
By following this pattern, we ensure that every number is visited only once, following the desired sequence, and thus the time complexity is O(n)
. There are no additional data structures used to store intermediate results; hence, the space complexity is O(1)
if we don't consider the space needed for the output list ans
.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach using n = 21
as a small example:
-
Start by initializing
v
to 1 because we must construct numbers starting from the smallest positive integer. -
Create an empty list
ans
to contain our lexicographically ordered numbers. -
Now, we iterate from
i = 0
ton - 1
(until we haven
numbers inans
):- For
i = 0
:v = 1
. Sincev * 10 = 10
is less than or equal to 21, we can go deeper in the lexicographical tree. We appendv
toans
making it[1]
.
- For
i = 1
:- Now,
v = 10
. Sincev * 10 = 100
is greater than 21, we can't go deeper. So, we addv
toans
to have[1, 10]
. - We enter the backtracking while loop:
v / 10 = 1
, which can't have 1 added to it because it ends with a 9 after incrementing (this step is not applicable for this value but will be later).- We increment
v
to 11, since it's within bounds and not ending with a 9.
- Now,
- Continuing this process, our
ans
progresses through:[1, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
. - After reaching 19, we can't multiply by 10 because it would exceed 21. So, we backtrack:
- Divide 19 by 10 to get 1, increment by 1 to get 2 which is valid.
- We append 2 to
ans
to get[1, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 2]
. - We continue this process,
v
becomes 20, which we append toans
, then it becomes 21 which is also appended. - Since
v * 10
is greater thann
, we try to increment. However, 21 ends in a 9 after backtracking and incrementing, so we would stop the process here.
- For
-
After all iterations, our list
ans
is[1, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 2, 20, 21]
. -
We then reorder
ans
to get it into the correct lexicographical order manually:[1, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 2, 20, 21]
becomes[1, 2, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21]
.
Note that steps 4 and 5 occur automatically as part of the algorithm's design; they are effectively illustrating what the algorithm is doing under the hood.
By following each iteration's decision to either "go deeper" or "backtrack and move next" as outlined in the solution approach, the lexicographical order is achieved with O(n)
time complexity and O(1)
space complexity, excluding the space of the output list ans
.
Solution Implementation
1from typing import List
2
3class Solution:
4 def lexicalOrder(self, n: int) -> List[int]:
5 current_value = 1
6 lex_order_list = []
7
8 # Generate n lexicographic numbers
9 for _ in range(n):
10 # Append current value to the result list
11 lex_order_list.append(current_value)
12
13 # If the current value times 10 is less than or equal to n,
14 # then *10 will still give us a lexicographically smaller number
15 if current_value * 10 <= n:
16 current_value *= 10
17 else:
18 # If current_value * 10 is larger than n, we check:
19 # If the current value is the end of the range (ends in 9)
20 # or adding one to current value would exceed n,
21 # we continuously divide current_value by 10 until it's not.
22 while current_value % 10 == 9 or current_value + 1 > n:
23 current_value //= 10
24
25 # Finally, we increment current_value by one to get the next valid number
26 # in lexicographical order that is also less than or equal to n.
27 current_value += 1
28
29 # Return the list containing all n numbers in lexicographical order
30 return lex_order_list
31
1import java.util.ArrayList;
2import java.util.List;
3
4class Solution {
5
6 public List<Integer> lexicalOrder(int n) {
7 // Initialize an ArrayList to store the lexicographically ordered numbers
8 List<Integer> result = new ArrayList<>();
9 // Start with the smallest lexicographically number 1
10 int current = 1;
11
12 for (int i = 0; i < n; ++i) {
13 // Add the current number to the result list
14 result.add(current);
15
16 // Check if the next lexicographical step is to multiply by 10
17 if (current * 10 <= n) {
18 current *= 10; // If so, go down one level of the lexical tree
19 } else {
20 // If reached the end of this lexical level (e.g., n is 13 and current is 9),
21 // or the increment leads past n, go up one level and increment
22 while (current % 10 == 9 || current + 1 > n) {
23 current /= 10;
24 }
25 current++; // Increment to the next number in lexical order
26 }
27 }
28
29 // Return the list containing the lexicographically ordered numbers
30 return result;
31 }
32
33}
34
1#include <vector>
2using namespace std;
3
4class Solution {
5public:
6 // Function to generate the lexicographical order of numbers from 1 to n
7 vector<int> lexicalOrder(int n) {
8 vector<int> result;
9 int current = 1;
10 for (int i = 0; i < n; ++i) {
11 // Add the current number to the result
12 result.push_back(current);
13 // If multiplying current by 10 is less than or equal to n, keep going to the next depth
14 if (current * 10 <= n) {
15 current *= 10;
16 } else {
17 // When current reaches the end of a depth (a multiple of 10 - 1) or n
18 // We go back to the closest ancestor which can have a right sibling
19 // and increment it by 1 in the lexicographical sequence
20 while (current % 10 == 9 || current + 1 > n) {
21 current /= 10;
22 }
23 ++current;
24 }
25 }
26 return result; // Return the list in lexicographically increasing order
27 }
28};
29
1// Defines the lexicalOrder function that returns an array of numbers in lexicographical order up to n
2const lexicalOrder = (n: number): number[] => {
3 // Initialize the answer array which will hold the numbers in lexicographical order
4 let answer: number[] = [];
5
6 // A depth-first search function to explore each possible number within range
7 const dfs = (current: number) => {
8 // If the current number exceeds n, return since it's out of bounds
9 if (current > n) {
10 return;
11 }
12 // Add the current number to the answer array
13 answer.push(current);
14
15 // Iterate through the next possible digits (0 through 9)
16 for (let i = 0; i < 10; ++i) {
17 // Recursively call dfs with the next potential number
18 dfs(current * 10 + i);
19 }
20 }
21
22 // Start the depth-first search with initial digits (1 through 9)
23 for (let i = 1; i < 10; ++i) {
24 dfs(i);
25 }
26
27 // Return the final array of numbers in lexicographical order
28 return answer;
29};
30
Time and Space Complexity
Time Complexity
The provided algorithm generates numbers in lexicographical order from 1
to n
. For each number, it performs a series of steps to determine the next number in the order. The complexity analysis is as follows:
- The algorithm uses a for loop that runs
n
times (once for each number from 1 ton
). - Inside the loop, if the current number
v
multiplied by 10 is less than or equal ton
, it immediately finds the next number by multiplying by 10, which is a constant time operationO(1)
. - If the current number
v
is not directly preceding a number by multiplication of 10, the algorithm may execute one or more while loop iterations. Each iteration of the loop dividesv
by 10 or incrementsv
by 1, depending on the condition. - In the worst case scenario, the division by 10 occurs at most
O(log n)
times per number becausev
can at most haveO(log n)
digits for a base 10 representation.
However, despite the potential multiple while loop iterations, every number from 1 to n
is processed exactly once, and the while loop adjusts the next start of the sequence. Therefore, each digit is checked a constant number of times.
The overall time complexity is O(n)
. While there are additional O(log n)
operations per element, those operations do not multiply the total complexity, because they relate to the transition between elements rather than processing of individual elements themselves.
Space Complexity
The space complexity of the algorithm includes the space needed for the output as well as any additional data structures used in the computation:
- The output list
ans
containsn
elements, resulting in a space complexity ofO(n)
. - The variable
v
and the loop indexi
are of constant size, addingO(1)
space.
Hence, the total space complexity, considering the space used to store the output, is O(n)
. If the space for the output is not considered as part of the complexity analysis, the space complexity of the algorithm itself is O(1)
.
Learn more about how to find time and space complexity quickly using problem constraints.
How would you design a stack which has a function min
that returns the minimum element in the stack, in addition to push
and pop
? All push
, pop
, min
should have running time O(1)
.
Recommended Readings
https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS
Trie Introduction Imagine you have a magic dictionary where as soon as you start spelling a word it immediately tells you how many words that start with those letters How cool would that be This is exactly the kind of magic a data structure called trie performs What's a Trie
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Want a Structured Path to Master System Design Too? Donāt Miss This!