Leetcode: Copy List with Random Pointer

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

Solution

/**
 * Definition for singly-linked list with a random pointer.
 * class RandomListNode {
 *     int label;
 *     RandomListNode next, random;
 *     RandomListNode(int x) { this.label = x; }
 * };
 */
public class Solution {
    public RandomListNode copyRandomList(RandomListNode head) {
        return copyRandomList(head, new HashMap<RandomListNode, RandomListNode>());
    }
    
    public RandomListNode copyRandomList(RandomListNode head, HashMap<RandomListNode, RandomListNode> cloned)
    {
        if(head == null)
            return null;
        if(cloned.containsKey(head))
            return cloned.get(head);
        RandomListNode node = new RandomListNode(head.label);
        cloned.put(head, node);
        node.next = copyRandomList(head.next, cloned);
        node.random= copyRandomList(head.random, cloned);
        return node;
    }
}

LeetCode: Reorder List

Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…

You must do this in-place without altering the nodes' values.

For example,
Given {1,2,3,4}, reorder it to {1,4,2,3}.

Solution:

We divide the list in two parts for instance 1->2->3->4->5 will become 1->2->3 and 4->5, we have to reverse the second list and give a list that alternates both. The split is done with a slow and fast pointer.

First solution (using a stack for reversing the list):

public class Solution {

    public void reorderList(ListNode head) {

        if(head == null)

            return;

        ListNode slowPointer = head;

        ListNode fastPointer = head.next;

        while(fastPointer!=null && fastPointer.next !=null)

        {

            fastPointer = fastPointer.next.next;

            slowPointer = slowPointer.next;

        }

        ListNode head2 = slowPointer.next;

        slowPointer.next = null;

        LinkedList<ListNode> queue = new LinkedList<ListNode>();

        while(head2!=null)

        {

            ListNode temp = head2;

            head2 = head2.next;

            temp.next =null;

            queue.push(temp);

        }

        while(!queue.isEmpty())

        {

            ListNode temp = queue.pop();

            temp.next = head.next;

            head.next = temp;

            head = temp.next;

        }

    }

}

Second solution (no data structure allowed):

public class Solution {

    public void reorderList(ListNode head) {

        if(head == null)

            return;

        ListNode slowPointer = head;

        ListNode fastPointer = head.next;

        while(fastPointer!=null && fastPointer.next !=null)

        {

            fastPointer = fastPointer.next.next;

            slowPointer = slowPointer.next;

        }

        ListNode head2 = slowPointer.next;

        slowPointer.next = null;

        head2= reverseList(head2);

        alternate (head, head2);

    }

    

    private ListNode reverseList(ListNode head)

    {

        if (head == null)

            return null;

        ListNode reversedList = head;

        ListNode pointer = head.next;

        reversedList.next=null;

        while (pointer !=null)

        {

            ListNode temp = pointer;

            pointer = pointer.next;

            temp.next = reversedList;

            reversedList = temp;

        }

        return reversedList;

    }

    

    private void alternate (ListNode head1, ListNode head2)

    {

        ListNode pointer = head1;

        head1 = head1.next;

        boolean nextList1 = false;

        while(head1 != null || head2 != null)

        {

            if((head2 != null && !nextList1) || (head1==null))

            {

                pointer.next = head2;

                head2 = head2.next;

                nextList1 = true;

                pointer = pointer.next;

            }

            else 

             {

                pointer.next = head1;

                head1 = head1.next;

                nextList1 = false;

                pointer = pointer.next;

            }

        }

    }

}

Leetcode: Insertion Sort List

Sort a linked list using insertion sort.

Solution:

In the previous post we already implement Insertion sort in arrays, now we deal of how to do it in single-linked lists.

We summarize the difference:

• - Traversing a single-linked in the opposite direction is very costly.
• - We can add an element in any position without having to move the next elements.

The only difficulty of this problem is to be very careful with the pointers, in order to avoid creating a loop

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode insertionSortList(ListNode head) {
        if(head==null)
            return null;
        ListNode nodeToInsert = head.next;
        while ( nodeToInsert != null)
        {
            ListNode nextToInsert = nodeToInsert.next;
            nodeToInsert.next = null;
            if(nodeToInsert.val<head.val)
            {
                nodeToInsert.next = head;
                if(head.next == nodeToInsert)
                    head.next =null;
                head = nodeToInsert;
                
            }
            else
            {
                ListNode temp = head;
                while(temp.next!=null && temp.next.val< nodeToInsert.val)
                    temp = temp.next;
                if(temp.next!=nodeToInsert)
                    nodeToInsert.next = temp.next;
                temp.next = nodeToInsert;
            }
            nodeToInsert = nextToInsert;
        }
        return head;
    }
}

Sorting Algorithms

Today we are going to implement the most common typical algorithms and compare their results.  In same cases we will give the common algorithm with some optimizations.

Simple Sorts:

In this section, we deal with 3 of the simplest sorting algorithms: bubble sort, insertion sort (with a variation called binary insertion sort) and selection sort. Bubble sort is usually considered the less efficient of the three.  As we will show insertion sort is generally faster than selection sort, due to fewer comparisons and good performance on almost-sorted data, but in the case that writing operation is much more costly than comparisons then selection sort is preferred.

    Bubble sort:

   public void BubbleSort(E[] array)

   {

for(int i=0; i<array.length; i++)

{

   for(int j=array.length-1; j>i; j--)

   {

      if(array[j].compareTo(array[j-1])<0)

swap(array,j,j-1);

   }

}

   }

    Insertion Sort:

   public void InsertionSort(E[] array)
   {
for(int j=1; j<array.length; j++)
{
            E key= array[j];
    int i=j-1;
    while(i>=0 &&  array[i].compareTo(key)>0)
    {
array[i+1] = array[i];
i = i-1;
    }
    array[i+1] = key;
}
   }

  
An improvement can be done, reducing the number of comparisons to  O(n logn) using binary search to locate where to insert the data. The algorithm still has a running time of O(n^2) on average because of the swaps required for each insertion.

   Binary Insertion Sort

  public void BinaryInsertionSort(E[] array)

  { 

for(int j=1; j<array.length; j++)

{

      E key= array[j];

   //Binary Search (position to insert indicated by imax)

   int imin = 0; 

   int imax = j;

   while(imax>imin)

   {

int midpoint  = (imin+imax)/2;

if(array[midpoint].compareTo(array[j])>0) 

      imax = midpoint;

else

   imin = midpoint +1;

   }

   for(int i=j-1; i>=imax; i--)

array[i+1] = array[i];

   array[imax] = key;

} a

   }

  Selection Sort:

   public void SelectionSort(E[] array)

   {

for(int i=0; i<array.length-1; i++)

{

      int min = i;

   for (int j=i+1; j<array.length; j++)

   {

if(array[min].compareTo(array[j])>0)

      min=j;

   }

   swap(array,i,min);

}

   }

Efficient algorithms:

In this section we implement the sorting algorithms with average complexity (and generally worst-case complexity) O(n log n), of which the most common are heap sort, merge sort, and quicksort. We also provide an improved version of merge sort where the merge uses a temporary array of O(n/2) instead of n elements. 

Another very used sorting algorithm based on merge sort is Timsort, that takes advantage of the already sorted sequences, this is the default sorting algorithm for Python and to order array of Objects in Java 7 (previous used merge sort). We will implement Timsort in a future post.

   Heap Sort:

   public void heapSort(E[] array)

   { 

int heapSize = buildHeap(array);

for (int i=0; i<array.length-1; i++)

{

   heapSize--;

   swap(array,0, heapSize);

   maxheapify(array, 0, heapSize);

}

   }

   private void maxheapify(E[]array, int i, int heapSize)

   {

int l = 2*i+1;

int r = 2*i+2;

int largest = i;

if (l<heapSize && array[l].compareTo(array[i])>0)

   largest = l;

if (r<heapSize && array[r].compareTo(array[largest])>0)

   largest = r;

if (largest!=i)

{

    swap(array, i, largest);

    maxheapify(array, largest, heapSize);

}

   }

   private int buildHeap(E[] array)

   {

for(int i=(int) ((array.length-1)/2); i>=0; i--)

   maxheapify(array, i, array.length);

return array.length;

   }

   Quicksort:

   public void quickSort(E[] array)

   {

//Shuffling the array using Fisher–Yates_shuffle can improve the performance when the data is not random

quickSort(array,0,array.length-1);

   }

   private void quickSort(E[] array, int p, int r) 

   {

if (p < r)

{

   int q=partition(array,p,r);

   quickSort(array,p,q-1);

   quickSort(array,q+1,r);

}

   }

   private int partition(E[] array, int p, int r) 

   {

E pivot= array[p];

int i = p;

for(int j=p+1; j<=r; j++)

{

   if (array[j].compareTo(pivot)<)

   {

i++;

swap(array,j,i);

   }

}

swap(array,i,p);

return i;

   }

    Merge sort:

   public void mergeSort(E[] array)

   {

mergeSort(array,0,array.length-1);

   }

   private void mergeSort(E[] array, int p, int r) 

   {

if (p<r)

{

     int q= (p+r)/2;

   mergeSort(array, p, q);

   mergeSort(array, q+1, r);

   merge(array,p,q,r);

}

   }

   private void merge(E[] array, int p, int q, int r)

   {

   //Input: Array E, being E[p...q] and E[q+1...r] in sorted order, with p<=q<=r

   //Output: Array E, with E[p...r] sorted

int n1 = q-p+1;

int n2 = r-q;

Comparable[] array1 = new Comparable [n1];

Comparable[] array2 =  new Comparable [n2];

for(int i=0; i<n1; i++)

   array1[i] = array[p+i];

for(int i=0; i<n2; i++)

   array2[i] = array[q+1+i];

int i=0;

int j=0;

for(int k=p; k<=r; k++)

{

   if((i<n1 && j<n2 && array1[i].compareTo(array2[j])<0) || (j==n2))

   {

array[k]=(E) array1[i++];

   }

   else

   {

array[k]=(E) array2[j++];

   }

}

   }

    Improvement of merge, that only copies the smallest array into a temporary array:

   

   private void merge2(E[] array, int p, int q, int r)

   {

   //Input: Array E, being E[p...q] and E[q+1...r] in sorted order, with p<=q<=r

   //Output: Array E, with E[p...r] sorted

int n1 = q-p+1;

int n2 = r-q;

if(n1<n2)

{

   Comparable[] arrayTemp = new Comparable [n1];

   for(int i=0; i<n1; i++)

arrayTemp[i] = array[p+i];

   int i=0;

   int j=q+1;

   for(int k=p; k<=r; k++)

   {

if((i<n1 && j<=r && arrayTemp[i].compareTo(array[j])<0) || (j==r+1))

{

   array[k]=(E) arrayTemp[i++];

}

else

{

   array[k]=(E) array[j++];

}

   }

}

else

{

   Comparable[] arrayTemp = new Comparable [n2];

   for(int i=0; i<n2; i++)

   arrayTemp[i] = array[q+1+i];

   int i=q;

   int j=n2-1;

   for(int k=r; k>=p; k--)

   {

if((i>=p && j>=0 && arrayTemp[j].compareTo(array[i])>0) || (i==p-1))

{

   array[k]=(E) arrayTemp[j--];

}

else

{

   array[k]=(E) array[i--];

}

   }

}

   }

Results:

Small size

 This experiment compares all the algorithms proposed for arrays of size 1000 or less. We sort a random generated Double array and each experiment is repeated 100,000 times. The next figure shows the average of them.

Big size

This experiment compares only the efficient algorithms proposed for arrays from 1,000 to 10,000,000. Each experiment is repeated 100 times and the rest of the things are identical to the previous experiment.

Conclusions:
We see that in tiny arrays, less than 60 elements, insertion sort is the fastest algorithm. This results seem to confirm the Timsort results[1], that they recommend a minrun between 32 and 64, each minrun is sorted with binary insertion sort. Our experiments seem to indicate that insertion sort has less overhead than binary insertion sort for this small arrays.

Another conclusion is that Quicksort is the fastest algorithm in average for random arrays (this can be guaranteed shuffling the array at the beginning). This happens even quicksort does 39% more comparisons (1.39 n log n vs 1 n log n) , the main reasons for quicksorting performing faster than merge sort and heapsort is that it has a good locality of reference when we do the partition in place, essentially two linear scans are done from both ends of the array, due to this fact it have very few cache misses. This is the also the reason why heapsort performs worse (it takes more than twice the time than quicksort) as it has to access to very distant position of the arrays.

[1] Peters, Tim "python_timsort", http://bugs.python.org/file4451/timsort.txt

Implementation of a Fibonacci Heap in Java

Today, we show the implementation of a Fibonacci heap. We will show that even theoretically they perform better than a binary heap, e.g.  fibonacci heap inserts in O(1) vs O(log n)  of a binary heap.  In a practical application, its constant factors make them less desirable than a binary heap for most of the applications.

The implementation follows [1, Chapter 19] or [2, Chapter 20].

Implementation:

import java.util.AbstractQueue;
import java.util.Comparator;
import java.util.ConcurrentModificationException;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;


public final class FibonacciHeap<E>  extends AbstractQueue<E> {

public static final class Node<E> {
int degree = 0;
boolean mark = false;
private Node<E> parent = null;
private Node<E> child = null;

private Node<E> left = null;
private Node<E> right = null;
private E element;

public E getElement(){return element;}
public void setElement(E element){this.element=element;}

public Node (E elem)
{
this.element=elem;
left = right = this;
}
}

private class DefaultComparator implements Comparator<E>
    {
        public int compare (Object o1, Object o2)
        {
        if(o1==null && o2 ==null)
        return 0;
        if(o1==null)
        return -1;
        if(o2==null)
        return 1;
            return ((Comparable) o1).compareTo(o2);
        }
    }

    private Comparator<E> myComp = new DefaultComparator();
private int size=0;
private Node<E> min=null;

public boolean offer(E e) {
if (e==null)
return false;
Node<E> x = new Node<E>(e);
if (min == null)
{
min = x;
}
else
{
min = mergeLists(min, x);
}
size++;
return true;
}

public boolean isEmpty() {
        return min == null;
    }

public void union(FibonacciHeap<E> h2)
{
min=mergeLists(this.min, h2.min);
this.size += h2.size;
//destroy the added one
h2.min=null;
h2.size=0;
}

public E poll() {
Node<E> z = min;
if (z!=null)
{
if(z.child!=null)
{
Node<E> current =z.child;
do
{
current.parent = null;
current = current.right;
}
while(current != z.child);
}
mergeLists(min, z.child);
if(z.right!=z)
{
z.right.left = z.left;
z.left.right = z.right;
min = z.right;
consolidate();
}
else
min = null;

}
size--;
return z.getElement();
}

private void consolidate() 
{
Object[] A = new Object[(int)(Math.log(size)/Math.log(2))+2];
Node<E> current = min;
HashSet<Node<E>> used = new HashSet<Node<E>>();
do
{
Node<E> x = current;
used.add(x);
current = current.right;
int d = x.degree;
while(A[d] != null)
{
Node<E> y = (Node<E>) A[d];
if (myComp.compare(x.element, y.element)>0)
{
Node<E> temp =x;
x=y;
y=temp;
}
fibHeapLink(y,x);
A[d] = null;
d = d+1;
}
A[d] = x;
}
while(!used.contains(current));


min=null;
for (int i=0; i<A.length; i++)
{
if(A[i] != null)
{
if(min==null)
min=(Node<E>) A[i];
else
min = (Node<E>) (myComp.compare(min.element, ((Node<E>) A[i]).element)<0 ? min : A[i]);
}
}

}

private void fibHeapLink(Node<E>y, Node<E>x)
{
//It cannot be than y is the only one in root list as x has to be too

y.right.left = y.left;
y.left.right = y.right;
y.right=y;
y.left=y;
if(x.child!=null)
{
x.child = mergeLists(x.child, y);
}
else
x.child = y;
x.degree += 1;
y.mark = false;
}

public E peek() {
if(size==0)
return null;
return min.getElement();
}

public int size() {
return size;
}
    
    
private Node<E> mergeLists(Node<E> list1, Node<E> list2) 
{
          if (list1 == null && list2 == null) {
              return null;
          }
          if ( list2 == null) {
              return list1;
          }
          if (list1 == null ) {
              return list2;
          }
          else { 
            // Both non-null; actually do the splice.
            /* The idea is that we'll have two lists that look like this:
             *
             * +----+     +----+     +----+
             * |    |--R->| l1 |--R->|l1R |
             * |    |<-L--|    |<-L--|    |
             * +----+     +----+     +----+
             *
             *
             * +----+     +----+     +----+
             * |    |--R->| l2 |--R->|    |
             * |    |<-L--|    |<-L--|    |
             * +----+     +----+     +----+
             *
             * And we want to relink everything to get
             *
             * +----+     +----+     +----+---+
             * |    |--R->| l1 |     |l1R |   |
             * |    |<-L--|    |     |    |<+ |
             * +----+     +----+<-\  +----+ | |
             *                  \  R        | |
             *                   L  \       R |
             * +----+     +----+  \->+----+ | |
             * |    |--R->| l2 |     |    | | |
             * |    |<-L--|    |     |    | | L
             * +----+     +----+     +----+ | |
             *              ^ |             | |
             *              | +-------------+ |
             *              +-----------------+
             *
             */
            Node<E> l1R = list1.right;
            list1.right = list2.right;
            list1.right.left =list1;
            list2.right = l1R;
            list2.right.left = list2;

            /* Return a pointer to whichever is smaller. */
            return myComp.compare(list1.element, list2.element)<0 ? list1 : list2;
        }
    }

private void print(Node<E> node, String prefix, boolean start)
{
if(node == null)
return;
System.out.println(prefix + node.getElement().toString());
print(node.child, prefix+"\t", true);
if(start)
{
Node<E> current=node.right;
while(current!=node)
{
print(current, prefix, false);
current = current.right;
}
}
}

public void print()
{
print(min);
}

private void print(Node<E> e)
{
print(e, "", true);
}

public void decreaseKey(Node<E> x, E val)
{
if(myComp.compare(val,x.getElement())>0)
throw new IllegalArgumentException("New key is greater than current");
x.setElement(val);
Node<E> y = x.parent;
if (y != null && myComp.compare(x.getElement(), y.getElement())<0)
{
cut(x,y);
cascadingCut(y);
}
if(myComp.compare(x.getElement(), min.getElement())<0)
min=x;
}

private void cut(Node<E> x, Node<E> y)
{
if(x.right==x)
y.child = null;
else
{
x.left.right = x.right;
x.right.left = x.left;
if (y.child == x)
y.child = x.right;
x.right = x.left = x;
}
min = mergeLists(x, min);
x.parent = null;
x.mark = false;
}

private void cascadingCut(Node<E> y) 
{
Node<E> z = y.parent;
if (z != null)
{
if(y.mark == false)
y.mark=true;
else
{
cut(y,z);
cascadingCut(z); 
}
}
}



public Iterator<E> iterator() {
Iterator<E> it = new Iterator<E>() {
public boolean hasNext() {
return visited.size()<size;
}

public E next() {
E value = current.getElement();
visited.add(current);
if(hasNext())
{
if(current.child!=null)
{
stack.push(current);
current = current.child;
}
else
{
while(visited.contains(current.right))
{
if(!stack.isEmpty())
current = stack.pop();
else
throw new ConcurrentModificationException();
}
current = current.right;
}
}
return value;
}

public void remove() {
throw new UnsupportedOperationException("remove not implemented");
}
Node<E> current = min;
LinkedList<Node<E>> stack = new LinkedList<Node<E>>();
HashSet<Node<E>> visited = new HashSet<Node<E>>(); 
};
        
return it;
}
 
public void delete(Node<E> node)
{
decreaseKey(node, null); // We use null to indicate -Inf
poll();
}
}


We also make two experiments to check the know problem of the constant factor. The first one consists on generating 1,000,000 random numbers and add them to a heap and after extract all of them, the second we just extract one of them. We compare the Fibonacci heap here implemented with a binary heap (PriorityQueue class)

Results:

                                Binary Heap           Fibonacci Heap
Experiment 1            685.396 ms             4707.570 ms
Experiment 2             82.292 ms              1231.942 ms




[1] T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, "Introduction to Algorithms", McGraw-Hill, 3rd Edition.

[2] T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, "Introduction to Algorithms", McGraw-Hill, 2nd Edition.