Lexicographical Numbers

XXX. Lexicographical Numbers

Math

DFS-like

Problem Statement:

Given an integer n, return a list of integers from 1 to n ordered lexicographically. Lexicographical order is where numbers are ordered based on their string representation (e.g., "1", "10", "11", "12", "2", "3").

• Input is a positive integer n
• Output should contain all numbers from 1 to n
• Numbers should be ordered as strings would be in a dictionary

Algorithm:

1. **Pattern Recognition**:
   • Each number can either grow by adding a digit (x10)
   • Or increment within same number of digits
   • Or backtrack when reaching limits
2. **Number Transitions**:
   • If curr*10 ≤ n: Add a zero (go deeper)
   • If curr+1 ≤ n and not ending in 9: Increment
   • Otherwise: Backtrack and move to next branch

Complexity:

Time Complexity: O(n), we visit each number exactly once
Space Complexity: O(1) excluding output array

Implementation:

Java Solution:

public List lexicalOrder(int n) {
    List list = new ArrayList<>(n);
    int curr = 1;
    
    for (int i = 1; i <= n; i++) {
        list.add(curr);
        if (curr * 10 <= n)                        // Can add a digit
            curr *= 10;
        else if (curr % 10 != 9 && curr + 1 <= n)  // Can increment
            curr++;
        else {                                     // Need to backtrack
            while ((curr / 10) % 10 == 9)          // Skip trailing nines
                curr /= 10;
            curr = curr / 10 + 1;                  // Move to next branch
        }
    }
    return list;
}
                

Python Solution:

def lexicalOrder(self, n: int) -> List[int]:
    result = []
    curr = 1
    
    for _ in range(n):
        result.append(curr)
        if curr * 10 <= n:                         # Can add a digit
            curr *= 10
        elif curr % 10 != 9 and curr + 1 <= n:     # Can increment
            curr += 1
        else:                                      # Need to backtrack
            while (curr // 10) % 10 == 9:          # Skip trailing nines
                curr //= 10
            curr = curr // 10 + 1                  # Move to next branch
    
    return result
                

C++ Solution:

vector lexicalOrder(int n) {
    vector result;
    result.reserve(n);
    int curr = 1;
    
    for (int i = 1; i <= n; i++) {
        result.push_back(curr);
        if (curr * 10 <= n)                        // Can add a digit
            curr *= 10;
        else if (curr % 10 != 9 && curr + 1 <= n)  // Can increment
            curr++;
        else {                                     // Need to backtrack
            while ((curr / 10) % 10 == 9)          // Skip trailing nines
                curr /= 10;
            curr = curr / 10 + 1;                  // Move to next branch
        }
    }
    return result;
}
                

Explanation:

• **Main Logic**:
  • Start with 1 and build numbers sequentially
  • Three possible moves at each step
  • Priority: Add digit → Increment → Backtrack
• **Number Generation**:
  • Multiply by 10 to add a digit (1 → 10)
  • Add 1 to get next number (11 → 12)
  • Backtrack when hitting limits (19 → 2)
• **Edge Cases**:
  • Check bounds before multiplication (curr * 10 ≤ n)
  • Handle numbers ending in 9 specially
  • Multiple backtrack steps for consecutive nines