DEV Community

Cover image for 386. Lexicographical Numbers
MD ARIFUL HAQUE
MD ARIFUL HAQUE

Posted on

386. Lexicographical Numbers

386. Lexicographical Numbers

Difficulty: Medium

Topics: Depth-First Search, Trie

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: 4
  • Explanation: [1,2]

Constraints:

  • 1 <= n <= 5 * 104

Solution:

We can approach it using a Depth-First Search (DFS)-like strategy.

Key Insights:

  • Lexicographical order is essentially a pre-order traversal over a virtual n-ary tree, where the root node starts at 1, and each node has up to 9 children, which are formed by appending digits (0 to 9).
  • We can simulate this pre-order traversal by starting with 1 and repeatedly appending numbers, ensuring we don't exceed the given n.

Approach:

  1. Start with the number 1 and attempt to go deeper by multiplying by 10 (i.e., the next lexicographical number with the next digit).
  2. If going deeper (multiplying by 10) is not possible (i.e., exceeds n), increment the number, ensuring that it doesn’t introduce an invalid jump across tens (i.e., going from 19 to 20).
  3. We backtrack when the current number cannot be extended further and move to the next valid number.
  4. Continue until all numbers up to n are processed.

Let's implement this solution in PHP: 386. Lexicographical Numbers

<?php
/**
 * @param Integer $n
 * @return Integer[]
 */
function lexicalOrder($n) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage
$n1 = 13;
print_r(lexicalOrder($n1));

$n2 = 2;
print_r(lexicalOrder($n2));
?>
Enter fullscreen mode Exit fullscreen mode

Explanation:

  • We maintain a current number and try to go as deep as possible by multiplying it by 10 to get the next lexicographical number.
  • When we can't multiply (because it would exceed n), we increment the number. We handle cases where the increment leads to numbers like 20, 30, etc., by checking for trailing zeros and adjusting the current number accordingly.
  • The loop continues until we've added all numbers up to n in lexicographical order.

Example Walkthrough:

Input: n = 13

  1. Start at 1.
  2. Multiply 1 by 10 -> 10.
  3. Add 11, 12, 13.
  4. Backtrack to 2 and continue incrementing up to 9.

Output:

[1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9]
Enter fullscreen mode Exit fullscreen mode

Input: n = 2

  1. Start at 1.
  2. Move to 2.

Output:

[1, 2]
Enter fullscreen mode Exit fullscreen mode

Time Complexity:

  • O(n) since each number from 1 to n is processed exactly once.

Space Complexity:

  • O(1) extra space is used (disregarding the space used for the result array).

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

Image of AssemblyAI tool

Challenge Submission: SpeechCraft - AI-Powered Speech Analysis for Better Communication

SpeechCraft is an advanced real-time speech analytics platform that transforms spoken words into actionable insights. Using cutting-edge AI technology from AssemblyAI, it provides instant transcription while analyzing multiple dimensions of speech performance.

Read full post

Top comments (0)

AWS Security LIVE!

Tune in for AWS Security LIVE!

Join AWS Security LIVE! for expert insights and actionable tips to protect your organization and keep security teams prepared.

Learn More

👋 Kindness is contagious

Discover a treasure trove of wisdom within this insightful piece, highly respected in the nurturing DEV Community enviroment. Developers, whether novice or expert, are encouraged to participate and add to our shared knowledge basin.

A simple "thank you" can illuminate someone's day. Express your appreciation in the comments section!

On DEV, sharing ideas smoothens our journey and strengthens our community ties. Learn something useful? Offering a quick thanks to the author is deeply appreciated.

Okay