7
$\begingroup$

Let $A$ be a collection of strings over the alphabet $\{0,\ldots,m-1\}$ that in total contain $n$ symbols.

Your task is to sort each of the strings internally, and then sort the resulting strings in lexicographic order. (Your algorithm doesn't have to operate this way.)

Example:

Input: 33123 15 1 0 54215 21 12

Output: 0 1 12 12 12333 12455 15

I found a way to do it in $O(m+n)$ time and $O(mn)$ space.

The space is larger than the time because I use a smart array that allows you to create an array with size $n$ and sort of giving initial values to all of the cells in $O(1)$.

I used bucket sort in order to sort each string ($O(m+n)$ time and space) and word trees in order to sort the collection $A$ itself ($O(m+n)$ time and $O(mn)$ space). but my solution is too complicated.

Does anyone have a better solution, with $O(m+n)$ time and less space, or faster than $O(m+n)$?

The solution must be deterministic so no hash maps or other statistical algorithms


My solution: A smart array is an array of size $m$ which we can create and "initialize" in $O(1)$:

We create three arrays the size of $m$ without initializing any of them and we also keep a single integer variable called $C$.

The first array contains the data. The second array contains pointers to a cell in the third array. The third array contains pointers to a cell in the second array. $C$ contains the number of cells initialed so far.

Suppose we would like to set the value of cell $i$ (suppose it is the first time we are doing it on this cell). Then we will go to cell $i$ in the first array and set it to the wanted val.

Now we go to cell $i$ in the second array and set it to point at cell $C$ at the third array. Set the cell $C$ in the third array to point at cell $i$ in the second array. Increase $C$ by 1.

Suppose we would like to know if cell $j$ is trash (That means we have yet to set anything to it).

We would go to cell $j$ in the second array and look at the cell number (in the third array) that cell $j$ (in the second array) points to – we will call it $k$.

If $k>C$ then $j$ is trash (because we have only initialized $C$ cells so far and $j$ isn't one of them).

If $k<C$ we will look at what cell $k$ (in the third array) points to. If it is not $j$ then $j$ is trash. Otherwise $j$ isn't trash

That way we can know at each step if we initialized this cell and if not initialize it. So we have created and "initialized" an array of size $m$ in $O(1)$ time.

The main trick is not to initialize the entire array at the start but to find a way to know which cells we've initialized so far and initialize a cell only when we "look" at it. In the RAM model it takes $O(1)$ time to create an array of any size without initializing it.


A word tree of order m is a generalization of a TRIE. Each node contains an array of pointers to its sons. The array size is $m$. Each node also contains a counter to say how many sets there are that are described by this node.

Because we are using smart arrays each time we add a word $A$ (a set) it only takes $O(|A|)$ time and $O(m|A|)$ space.

$\endgroup$
  • 4
    $\begingroup$ Time cannot be smaller than space. You are cheating in some way. $\endgroup$ – Yuval Filmus Dec 16 '16 at 17:01
  • $\begingroup$ Sure it can. Creating an array in size n without reseting it takes O(1). That's true for c and c++. Then you can use a very simple data structure to track which cells you've used and which are garbage $\endgroup$ – Ofer Magen Dec 16 '16 at 17:06
  • 1
    $\begingroup$ I don't care much for C and C++. We usually analyze algorithms under the RAM machine model. In this model time cannot be smaller than space. I'm slightly worried that your smart array doesn't really work in $O(1)$ per access. $\endgroup$ – Yuval Filmus Dec 16 '16 at 17:08
  • 1
    $\begingroup$ RAM model takes O(1) to define an array with size n (the computer only needs to define the start and end pointers). It takes O(n) to reset it to zeroes. C++ IS a ram model language that's why I brought this example $\endgroup$ – Ofer Magen Dec 16 '16 at 17:11
  • $\begingroup$ @YuvalFilmus Time cannot be smaller than space true. You are cheating in some way does not follow from "$O(m+n)$ time and $O(mn)$ space": with $1 \le mn$, $xm + yn + z \in O(mn)$ - the bound on space looks needlessly lax. $\endgroup$ – greybeard May 13 '18 at 4:16
0
$\begingroup$

You can also solve this in $O(n \log n)$ time and $O(n)$ space:

  • First, sort each word using mergesort. The running time of this will be at most $O(n \log n)$, and the space usage is $O(n)$.

  • Then, store all the words in a word trie. The time and space for this will be $O(n)$, if you implement the word trie properly. In particular, at each node of the trie, you should store the set of children as a hashtable (not as an array). In this way, the storage at a node is proportional to the number of children it has, and lookup to find a child can be done in $O(1)$ time. Thus, the running time of this stage is $O(n)$ time and $O(n)$ space.

  • Finally, read out all the words from the trie. This involves taking each hashtable and sorting its contents, say using mergesort. All of those sorting steps will take at most $O(n \log n)$ time.

The resulting data structure seems quite simple. It's especially simple if you implement in a language that has built-in support for hashmaps (e.g., Javascript, Python).

Alternatively, you can replace the hashmap with a balanced binary tree data structure and get a similar running time.


As a general note about "smart arrays":

You can replace your use of "smart arrays" with a hashtable. That way you will preserve the ability to do $O(1)$ (expected) time reads and writes. In particular, instead of setting $A[i] := v$, you store value $v$ at the key $k$ (i.e., add the mapping $k \mapsto v$ to the hashtable). When you want to read the value of $A[i]$, you instead lookup $i$ in the hashtable and return whatever you find there. In this way, the space usage is proportional to the number of initialized entries in the "smart array", and each access takes $O(1)$ (expected) time.

$\endgroup$
  • $\begingroup$ Hashtable are statistical tools and I need a deterministic solution. The use of merge sort isn't needed. You can use bucket sort because those are whole numbers in the range 1 to m and solve it in O (n+m ) $\endgroup$ – Ofer Magen Dec 19 '16 at 5:31
  • $\begingroup$ The smart array however is totally deterministic $\endgroup$ – Ofer Magen Dec 19 '16 at 5:32
  • 2
    $\begingroup$ You asked for faster than $O(n+m)$. $O(n \log n)$ is faster than $O(n+m)$ for some parameters -- but not for others. If you don't want to use a hashtable, use a balanced binary tree data structure, as I suggested in my answer -- that achieves the same $O(n \log n)$ running time and $O(n)$ space bounds, and does so totally deterministically. $\endgroup$ – D.W. Dec 19 '16 at 6:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.