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

Sorted Numbers

Solve a medium-level problem of sorting numbers in range in lexicographical order using tries.

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 to NN.

Analyzing this problem closely, we can observe that all the numbers starting with 11 ...