algoadvance

Leetcode 386. Lexicographical Numbers

Problem Statement

Given an integer n, return 1 - n in lexicographical order.

Example:

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

Clarifying Questions

1. What is the range of integer n?
   • Typically this would be specified in the problem. Assuming constraints typical for such problems, it might go up to (10^5).
2. Are there any specific constraints or performance requirements?
   • The goal here would be to generate the sequence in lexicographical order efficiently without sorting.
3. Is there a specific requirement on the method signature?
   • Typically, it would look like public List<Integer> lexicalOrder(int n).

Strategy

Approach

To achieve lexicographical order without sorting, a good approach is to utilize Depth-First Search (DFS). Starting from 1 and moving forward by always trying to append the next digit:

1. Start from 1 and go as deep as possible before incrementing the prefix.
2. If the current number x can append another digit without exceeding n, recurse into x*10.
3. If the current number x is less than n and not ending with a 9 (allows the next increment), increment x by 1.

Steps

1. Initialize an empty list to hold the result.
2. Iterate through the base numbers from 1 to 9 and perform a DFS on each.
3. In each DFS iteration:
   • Add the current number to the list.
   • Try to generate the next number by appending digits until it exceeds n.

Code

import java.util.ArrayList;
import java.util.List;

public class LexicographicalNumbers {

    public List<Integer> lexicalOrder(int n) {
        List<Integer> result = new ArrayList<>();
        for (int i = 1; i < 10; i++) {
            dfs(i, n, result);
        }
        return result;
    }

    private void dfs(int current, int n, List<Integer> result) {
        if (current > n) {
            return;
        }
        result.add(current);
        for (int i = 0; i < 10; i++) {
            if (10 * current + i > n) {
                return;
            }
            dfs(10 * current + i, n, result);
        }
    }

    public static void main(String[] args) {
        LexicographicalNumbers lexiNumbers = new LexicographicalNumbers();
        int n = 13;
        System.out.println(lexiNumbers.lexicalOrder(n));  // Output: [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9]
    }
}

Time Complexity

• Time Complexity: (O(n))
  • Each number from 1 to n is visited exactly once, resulting in an (O(n)) complexity.
• Space Complexity: (O(n))
  • The space complexity is also (O(n)) due to the storage used for the result list. The recursive DFS stack could go as deep as the number of digits in n. Hence, for n up to (10^5), the stack depth would handle up to 5 levels.

This solution provides an efficient way to generate numbers in lexicographical order without the need to sort them explicitly.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?