List Integers in Lexicographical Order
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
# List Integers in Lexicographical Order
Given `n`, return all integers from `1` through `n` in lexicographical order of their usual decimal representations, without leading zeros.
Your algorithm must run in `O(n)` time and use `O(1)` extra space, excluding the returned list.
### Function
`vector<int> lexicalOrder(int n)`
### Example 1
```text
Input: n = 21
Output: [1,10,11,12,13,14,15,16,17,18,19,2,20,21,3,4,5,6,7,8,9]
```
### Example 2
```text
Input: n = 5
Output: [1,2,3,4,5]
```
### Constraints
- `1 <= n <= 50000`.
### Clarifications
For lexicographical comparison, compare the decimal strings character by character. A shorter string comes first when it is a prefix of the other, so `1` precedes `10`, and `19` precedes `2`. Return integers, not strings.
### What a Strong Answer Covers
- Exact ordering and complete coverage without duplicates.
- Decimal-prefix boundaries and the upper limit.
- A correctness argument and the required time/extra-space bounds.
Overview: Practice listing positive integers in decimal lexicographical order with linear time and constant extra space beyond the returned list. Handle prefix and upper-bound transitions.