Merge k sorted linked lists and return it as one sorted list. The definition of the ListNode class and the signature of the MergeKLists method can't be modified.

Below is my submission to LeetCode which has been accepted and run time is not that bad (better than 55% of the submissions). But I am curious why mine is not in the top 10%. There must be something that can be improved in terms of algorithm performance. Can you please suggest something in this regard?

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace LeetCode23_MergeKSortedList
{

    /// <summary>
    /// This class definition is given as input. And can't be modified.
    /// </summary>
    public class ListNode
    {
        public int val;
        public ListNode next;
        public ListNode(int x) { val = x; }
    }

    /// <summary>
    /// Just so that we can add an Id field
    /// </summary>
    public class ListNodeWithId : ListNode
    {
        public Guid id { get; set; } = Guid.NewGuid();
        public ListNodeWithId (ListNode n): base (n.val)
        {
            next = n.next;
        }
    }
    /// <summary>
    /// To be able to handle duplicate valued nodes
    /// </summary>
    public class DuplicateKeyComparer : IComparer<ListNodeWithId>
    { 
        public int Compare(ListNodeWithId x, ListNodeWithId y)
        {            
            int result = x.val.CompareTo(y.val);

            if (result == 0)
                return x.id.CompareTo(y.id);   // Handle equal valued node as distinct still
            else
                return result;
        }

    }
    public class Solution
    {
        public ListNode MergeKLists(ListNode[] lists)
        {         
            var listSet = new SortedSet<ListNodeWithId>(new DuplicateKeyComparer());
            foreach (var list in lists.Where(x => x != null))
                listSet.Add(new ListNodeWithId(list));

            ListNode mergedListHead = null;
            ListNode mergedListCurrent = null;

            while (listSet.Count() > 0)
            {
                var min = listSet.First();

                int minVal = min.val;
                listSet.Remove(min);

                var nextNode = min.next;
                if ( nextNode != null)
                    listSet.Add(new ListNodeWithId(nextNode));

                var mergedListNode = new ListNode(minVal);

                if (mergedListCurrent != null)
                {
                    mergedListCurrent.next = mergedListNode;
                    mergedListCurrent = mergedListCurrent.next;
                }
                else
                {
                    mergedListHead = mergedListNode;
                    mergedListCurrent = mergedListNode;
                }
            }

            return mergedListHead;
        }
    }
}
  • I write in comments because my note is too small to be an answer. Don't use Count() method. This method iterates entire collection every time the while condition is checked. Instead use Count property of the SortedSet class or Any() method. Although Count() will use Count property if the collection implements ICollection<T> I recommend never use this method for determining if the collection is empty or not. – Maxim Sep 10 '17 at 5:04
    return x.id.CompareTo(y.id);   // Handle equal valued node as distinct still

Your tie-breaker is a high-entropy GUID. The contest inputs may have long runs of monotonic non-decreasing or non-increasing values, for which a boring sequential serial number id might do better at preserving runs than a GUID.

Rather than listSet, which is redundant with the declaration, I would prefer a name of simply lists.

I can't say I'm crazy about trivial definitions like this:

            int minVal = min.val;

At this point:

            var mergedListNode = new ListNode(min.val);

you have a perfectly nice min list node, right? But you discard it, and create a duplicate copy of it? Why? Seems like you're just keeping the GC busy.

I wouldn't mind seeing this happen before the while begins:

            else
            {
                mergedListHead = mergedListNode;
                mergedListCurrent = mergedListNode;
            }

You asked about speed. I think your algorithm is a perfectly good one - relying on SortedSet makes sense. But you do lots of node copying and reallocation, and you do lots of SortedSet operations. It's all in line with N log N, that's good, I'm just saying its more operations than necessary. Recall that Timsort is fast because it preserves runs. (BTW, it's not clear to me that stability is buying you anything, that keeping an ID on the side is helping you.)

Let's try to be lazy. Consider a 2-way merge, where first list has values of 1 to 1e6 (or they could even all be 1e6), and second list has values of million and one up to 2e6 (or they're all 2e6). Minimum amount of work we could possibly do is linear scan of first list, splice its final node to front of second list, scan to end, and return. No SortedSet operations, no deallocation or new allocations. What would you need to attain high speed in that special case? Either peek at minimum value before adding a node back into the set, or else you'd need some way of obtaining first two values so you can keep looping while you're below that 2nd lowest starting value. Good luck!

  • Getting rid of the extra allocation (and reusing min) unfortunately didn't make much improvement in runtime - although I agree it is something that needs to be done regardless. Changing GUID to plain int (incremental) actually improved the runtime quite a bit. Now it is better than 69% of all submissions. I didn't quite follow your last paragraph - but I think I will once I re-read it a few times. Thanks! – Stack crashed Sep 10 '17 at 3:06
  • Oh and the ID is really for making duplicate keys possible with the Set. It's not really about stability. If there are other better ways to use SortedSet with duplicate values, I am interested to hear about them. I am reluctant to write my heapsort from scratch. – Stack crashed Sep 10 '17 at 3:08
  • Guava's TreeMultiset may be of use. (And a heapsort implementation actually comes out fairly small.) My 2e6 thought experiment was just noting that some common workloads will benefit if you cache a target value, in this case a million and one, and do simple comparisons against the target value without incurring function call overhead. It's still O(1) constant time, just with a smaller constant buried by the notation. – J_H Sep 10 '17 at 16:13
  • Are there other ways to use SortedSet with duplicate values? Yes. It's slightly horrible, but you can tack hash-of-node onto the end of the key, to uniqueify it, and strip off that suffix prior to use. Any nonce would do, even a serial number. Bear in mind that using (immutable) strings as keys would run the risk of high interning overhead. – J_H Sep 10 '17 at 16:17

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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