Given an integer n, return all the numbers in the range [1, n] sorted in lexicographical order.
You must write an algorithm that runs in O(n) time and uses O(1) extra space.
Example 1:
Input: n = 13 Output: [1,10,11,12,13,2,3,4,5,6,7,8,9]
Example 2:
Input: n = 2 Output: [1,2]
Constraints:
1 <= n <= 5 * 104The idea is to perform a depth-first search (DFS) to generate numbers in lexicographical order. Starting from the number 1, we explore all numbers that can be formed by appending digits from 0 to 9 as long as the generated number is less than or equal to n. If we reach a number greater than n, backtrack and explore the next number at the same level and repeat the process.
This C implementation uses a helper function dfs to execute the depth-first search. It explores each tree node by multiplying the current number by 10 and adding digits from 0 to 9, ensuring the number remains within the limit n. The results are stored in an array which is printed in the main function.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), Space Complexity: O(1) (excluding the output array).
This iterative approach attempts to simulate the depth-first search behavior using an iterative procedure. It begins by using a number and incrementally moving to the next lexicographical number by clever digit manipulations. If a number reaches an immediate boundary, it backs off accordingly to stay within valid digits.
This C code leverages a simple iterative method to achieve lexical order. By multiplying the current index by 10, or adjusting on digit boundaries, this code manages to efficiently iterate through lexical numbers.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), Space Complexity: O(1) (ignoring return array).
| Approach | Complexity |
|---|---|
| DFS Approach | Time Complexity: O(n), Space Complexity: O(1) (excluding the output array). |
| Iterative Approach | Time Complexity: O(n), Space Complexity: O(1) (ignoring return array). |
Compute The Next Permutation of A Numeric Sequence - Case Analysis ("Next Permutation" on Leetcode) • Back To Back SWE • 116,578 views views
Watch 9 more video solutions →Practice Lexicographical Numbers with our built-in code editor and test cases.
Practice on FleetCode