Lexicographical Numbers

They be recycling daily questions already??!??!? (this was the daily question on 21/09/2024)

This question is just a simple recursion problem. You can see that in the example provided with n = 13 we get:

• [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9]

as the lexicographical order.

In it, it hints that the recursion equation should be, for any given i, we should have a function that iterates through all the possible digits in the ones column. Example:

• for i = 1, we have 1 to 9
• for i = 130, we have 130 to 139
• for i = 40, we have 40 to 49

Then, during this recursive function, while we iterate through all the possible digits in the ones column.

• add i to the ans array
• if i * 10 <= n, then that is the next lexicographically smallest integer and, at that moment in time, we should run the recursive function starting at value i * 10
  • example, if we have i = 1 and 10 <= n, then 10 must be the next lexicographically smallest integer, so we should run the recursive function starting at value i = 10 etc.

code

class Solution {
public:
    void addLexicographicalSmallest(vector<int>& ans, int current, int n) {
        for (int i = current; i <= min(current + 9, n); ++i) {
            ans.push_back(i);
            if ((i * 10) <= n) {
                addLexicographicalSmallest(ans, i*10, n);
            }
        }
    }
    vector<int> lexicalOrder(int n) {
        vector<int> ans;
        for (int i = 1; i <= min(9, n); ++i) {
            ans.push_back(i);
            if ((i * 10) <= n) {
                addLexicographicalSmallest(ans, i*10, n);
            }
        }
        return ans;
    }
};

complexity

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

time taken

• 9 minutes and 1 seconds