Lexicographical order

Moderate

0/80

Average time to solve is 35m

16 upvotes

Asked in companies

Problem statement

You are given a positive integer N. Your task is to return a list of integers containing integers from 1 to N (both inclusive) in lexicographically ascending order.

For example:- Given 3 numbers 1, 3 and 10, the lexicographical ascending order will be 1, 10 and 3.

Detailed explanation ( Input/output format, Notes, Images )

Input format:

The first and only line of input contains a single integer N.

Output format:

The only line of output contains N single space-separated integers i.e integers from 1 to N in lexicographical order.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= N <=10^6

Time Limit: 1 sec

Sample Input 1:

Sample Output 1:

1 10 11 12 13 14 15 2 3 4 5 6 7 8 9

Sample Input 2:

Sample Output 2:

1 10 11 12 13 14 15 16 17 18 19 2 20 21 22 23 24 3 4 5 6 7 8 9

Hint 1

Hint 2

Hint 3

First off, observe that the question is basically a sorting question but won’t work the way integer array does that. We need to focus on data type other than integer so as to sort the numbers.

Approaches (3)

Approach 1

Approach 2

Approach 3

Brute Force(Sorting)

Initialize a list of strings and add numbers from 1 to N in it.
Now, all we need to do is sort the list and return it

Time Complexity

O(N * log(N)), where N is the input integer, and also the size of the array.

In the worst case, we need to sort the array of size N which takes O(N * log(N)) time.

Space Complexity

O(N) where N is the size of the array.

In the worst case, we need to store N strings in the array.

(100% EXP penalty)

Lexicographical order

Console