Search⌘ K
AI Features
Home
Courses
Advanced Data Structures: Implementing Tries in C++ and Java

Sorted Numbers

Explore how to solve the problem of listing numbers from 1 to a given number lexicographically by implementing a trie. Understand insertion of integers into the trie, recursive preorder traversal, and optimization techniques to efficiently generate sorted numbers within specified limits.

We'll cover the following...

Problem statement

Given an integer numnum, return all the numbers in the range [1,num][1, num]sorted in lexicographical order.

Example 1

Sample input

n = 13

Sample output

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

Explanation

Sorting the values lexicographically [1,2,3,4,5,6,7,8,9,10,11,12,13] results in [1,10,11,12,13,2,3,4,5,6,7,8,9]

Example 2

Sample input

n = 3

Sample output

[1,2,3]

Explanation

Sorting the values [1,2,3] lexicographically, results in [1,2,3]

Try it yourself

Try to solve the problem yourself before reading the solution.

C++
Java
#include <iostream>

#include <vector>

using namespace std;



vector<int> lexicalOrder(int num) {

  // your code goes here

  vector<int> result;

  return result;

}
Solve sorted numbers in C++

Intuition

The first idea that strikes the mind is to iterate through all the integers from 11 to numnum, convert them into strings, insert them into a list, and then sort them. Considering the use of a standard sorting algorithm like merge sort, this approach has a time complexity of O(NlogN)O(N log N) and space complexity of O(N)O(N), where NN is the number of integers in the range 11 ...