Tree algorithm - arrange integer array numbers to form largest number

Question

I have solved leetcode's Largest Number.

I am asking another question about it here, more from a theory perspective about "if" I had used a tree for the solution. I have a full functioning non-tree based solution that you can refer to my post on code review stack exchange. However, I had another approach that I was going to follow at first; which uses a tree (as described in my post on code review). I am interested in learning about the tree approach from a computer science theory approach.

I will paste here again my graphical explanation of the tree based algorithm I thought of:

It will traverse from leafs to parents following:

concatenate(parent key + greater integer nodes (ie greater than parent)) ---> parent integer value -->concatenate (parent key + smaller integer nodes (ie smaller than parent))

ie in this example 9 5 34 3 30

Questions

- What kind of tree is suitable for this approach (Trie,N-ary, others..) ?
- What traversal algorithm should be used to traverse as I explained above ?

Update

For those interested, here is my implemented solution based on the feedback given by Minko_Minkov below, ie using max heap and heapsort. The code runs in 6ms (compared to 10ms using java sorting comparator).

class LargestNumber { public String largestNumber(int[] nums) { // Build max heap from array: // The max-heap tree will always keep // the biggest number at the top of the tree // then do a heap sort. heapSort(nums); StringBuilder str = new StringBuilder(); // pop backwards: heapsort will sort using our lexical comparator function in an // increasing fashion. But the final string will be printed backward // to match. for (int i = nums.length - 1; i >= 0; i--) str.append(nums[i]); // if we get a string of all zeros, strip to 1 zero. if (str.charAt(0) == '0') return "0"; return str.toString(); } private static void heapSort(int[] A) { buildMaxHeap(A); for (int i = A.length - 1; i > 0; i--) { // Swap A[0] with A[i] swap(0, i, A); heapify(A, 0, i); } } // if ab > ba will return a positive number, and means i1 > i2 // if ab <ba will return a negative number, and means i2 > i1 // if ab = ba , choose any to return private static int LexicallyCompare(int i1, int i2) { String a = Integer.toString(i1); String b = Integer.toString(i2); return (a + b).compareTo(b + a); } // Swap using Xor private static void swap(int x, int y, int[] nums) { nums[x] = nums[x] ^ nums[y]; nums[y] = nums[x] ^ nums[y]; nums[x] = nums[x] ^ nums[y]; } private static void buildMaxHeap(int[] A) { for (int i = (int) (Math.floor((double) A.length / 2) - 1); i >= 0; i--) { heapify(A, i, A.length); } } private static void heapify(int[] A, int i, int max) { int left = (2 * i) + 1; int right = (2 * i) + 2; int largest = i; if (left < max && LexicallyCompare(A[left], A[i]) > 0) largest = left; if (right < max && LexicallyCompare(A[right], A[largest]) > 0) largest = right; if (largest != i) { // swap A[i] with A[largest] swap(i, largest, A); heapify(A, largest, max); } } } 

Answer 1

I'd like to say good work on the soluton!

It's a nice attempt you have converting it to a tree as well, and I think a tree can be used in some way. However, I think using specifically an N-ary tree, or at least the one you've drawn might not work here.

This is because, in the N-ary tree from my understanding, duplicates are not allowed. Which would mean that there's no way to tell if just the digit "3" appeared by itself.

For example the input: [30, 34, 5, 9]

This input would've produced the exact same tree as the one you drew. Which would mean there's no way to tell if the number "3" ever just appeared by itself, and so, this type of tree can't be used.

However, there is a different tree solution called a "max-heap". The max-heap tree will always keep the biggest number at the top of the tree. You can construct a max-heap tree, put all the input numbers in it, while using the custom comparison function you have. You then pop all the numbers from the tree, and it'll always return the biggest number (based on your custom comparison function). This is also known as a "priority-queue." Or a "Heap sort"

In terms of theory, you're still using a custom comparison function, and you're still just sorting. But, you're using a different sorting algorithm that is faster than the algorithm used in Array.Sort(), faster than Java or Python.

The leetcode answer on this Big-O complexity can be misleading. Python and Java use Quicksort as the in-built sorting algorithm which is O(N log N) on average as Leetcode says, but it's O(N^2) in the worst case. Java's quick-sort is slightly better than Python's, cause they do something fancy called a "double pivot quicksort", but this is still guaranteed to be slower than a heap sort or a merge sort for a million numbers.

Sorts like merge sort and heap sort have a complexity of N log N (always), which is probably the fastest solution possible you can get for this problem.