Merge Intervals (LeetCode Sort)

Question: Given a collection of intervals, merge all overlapping intervals.
For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].

Idea: First sort the intervals according to their start point. Then use a variable to cache the previous interval and scan the list from left to right (ascending order). If the previous interval does not overlap with the current interval, append previous interval to the result, otherwise merge the previous interval and the current interval and store the new interval in the variable previous. When the loop is done, do not forget the last interval is not appended to result, since there is no current interval now.

Time: O(nlgn) Space: O(1)

Code:

 public class Solution {  
   public Comparator<Interval> comp=new Comparator<Interval>()  
   {  
     public int compare(Interval i1, Interval i2)  
     {  
       if(i1==null)  
         return 1;  
       else if(i2==null)  
         return -1;  
       else  
         return i1.start-i2.start;  
     }  
   };  
   public List<Interval> merge(List<Interval> intervals) {  
     if(intervals.size()<=1)  
       return intervals;  
     List<Interval> result=new ArrayList<Interval>();  
     Collections.sort(intervals,comp);  
     Interval pre=intervals.get(0);  
     for(int i=1;i<intervals.size();i++)  
     {  
       if(pre.end<intervals.get(i).start)  
       {  
         result.add(pre);  
         pre=intervals.get(i);  
       }  
       else  
       {  
         pre.start=Math.min(pre.start,intervals.get(i).start);  
         pre.end=Math.max(pre.end,intervals.get(i).end);  
       }  
     }  
     result.add(pre);  
     return result;  
   }  
 }  

Maximum Gap (LeetCode Sort)

Question: Given an unsorted array, find the maximum difference between the successive elements in its sorted form.
Try to solve it in linear time/space.
Return 0 if the array contains less than 2 elements.
You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.

Idea: Bucket sort. Assume there are n elements, we construct n-1 buckets and put the n-2 elements (without the max and the min) into the bucket. For each bucket, we only keep the bucketMax and the bucketMin value. Due to pigeon hole theory, there must be at least one empty buckets. The potential max gap is on the two sides of the empty buckets.

Time: O(n) Space: O(n)

Code:

 public class Solution {  
   public int maximumGap(int[] num) {  
     if(num.length<2)  
       return 0;  
     int maxValue=num[0];  
     int minValue=num[0];  
     for(int i=0;i<num.length;i++)  
     {  
       maxValue=Math.max(maxValue,num[i]);  
       minValue=Math.min(minValue,num[i]);  
     }  
     if(maxValue==minValue)  
       return 0;  
     int numBucket=num.length-1;  
     int bucketSize=(int)Math.ceil(((double)(maxValue-minValue))/numBucket);  
     int[] bucketMax=new int[numBucket];  
     int[] bucketMin=new int[numBucket];  
     Arrays.fill(bucketMax,Integer.MIN_VALUE);  
     Arrays.fill(bucketMin,Integer.MAX_VALUE);  
     for(int i=0;i<num.length;i++)  
     {  
       if(num[i]==maxValue||num[i]==minValue)  
         continue;  
       int whichBucket=(num[i]-minValue)/bucketSize;  
       bucketMax[whichBucket]=Math.max(bucketMax[whichBucket],num[i]);  
       bucketMin[whichBucket]=Math.min(bucketMin[whichBucket],num[i]);  
     }  
     int maxGap=Integer.MIN_VALUE;  
     int pre=minValue;  
     for(int i=0;i<numBucket;i++)  
     {  
       if(bucketMax[i]==Integer.MIN_VALUE&&bucketMin[i]==Integer.MAX_VALUE)  
         continue;  
       maxGap=Math.max(maxGap,bucketMin[i]-pre);  
       pre=bucketMax[i];  
     }  
     maxGap=Math.max(maxGap,maxValue-pre);  
     return maxGap;  
   }  
 }  

Largest Number (LeetCode Sort)

Question: Given a list of non negative integers, arrange them such that they form the largest number.
For example, given [3, 30, 34, 5, 9], the largest formed number is 9534330.
Note: The result may be very large, so you need to return a string instead of an integer.

Idea: First convert the numbers to string format. Then sort the strings following the rule: if "put string s1 in front of s2" makes a bigger number than "put string s2 in front of s1", place s1 after s2 in the sorted string array. Then scan the array from the last string to construct the output result.
Since the input may be "0" "0" "0" -> "000", we need to remove the leading zeros.

Time: O(nlgn) Space: O(n^2) (assume there are n integers each with n digits)

Code:

 public class Solution {  
   public Comparator<String> comp=new Comparator<String>()  
   {  
    public int compare(String s1,String s2)  
    {  
      String firstBig=s1+s2;  
      String secondBig=s2+s1;  
      for(int i=0;i<firstBig.length();i++)  
      {  
        char c1=firstBig.charAt(i);  
        char c2=secondBig.charAt(i);  
        if(c1>c2)  
        {  
          return 1;  
        }  
        if(c1<c2)  
        {  
          return -1;  
        }  
      }  
      return 0;  
    }  
   };  
   public String largestNumber(int[] num) {  
     String[] strings=new String[num.length];  
     for(int i=0;i<num.length;i++)  
       strings[i]=Integer.toString(num[i]);  
     Arrays.sort(strings,comp);  
     StringBuilder builder=new StringBuilder();  
     for(int i=strings.length-1;i>=0;i--)  
       builder.append(strings[i]);  
     int index=0;  
     while(builder.charAt(index)=='0'&&index<builder.length()-1)  
       index++;  
     return builder.substring(index);  
   }  
 }  

Swap Nodes in Pairs (LeetCode Linked List)

Question: Given a linked list, swap every two adjacent nodes and return its head.
For example,
Given 1->2->3->4, you should return the list as 2->1->4->3.
Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.

Idea: I used recursion. First recursively swap the sub-list starting from head.next.next. Then swap head.next and head.

Time: O(n) Space: O(1)

Code: 

 public class Solution {  
   public ListNode swapPairs(ListNode head) {  
     if(head==null||head.next==null)  
       return head;  
     head.next.next=swapPairs(head.next.next);  
     ListNode newHead=head.next;  
     head.next=head.next.next;  
     newHead.next=head;  
     return newHead;  
   }  
 }  

Sort List (LeetCode)

Question: Sort a linked list in O(n log n) time using constant space complexity.

Idea: I used merge sort. If the list is longer than 2, split it to two halves at length/2, then sort the two halves individually, finally merge. I implemented a version with an extra parameter length to indicate the current length of the list. Therefore we do not need to calculate the length when a new recursion is evolved. This will not reduce the time complexity in big O notation, but it will make the algorithm to run faster in reality.

Time: O(nlgn) Space: O(lgn) (Since we need a stack to store the pointers when we keep splitting the list to halves until the real sort begins when the list has less than 3 nodes.

Code:

 public class Solution {  
   public ListNode sortList(ListNode head) {  
     int len=getLength(head);  
     return mergeSort(head,len);  
   }  
   public ListNode mergeSort(ListNode head,int length)  
   {  
     if(length<=1)  
       return head;  
     if(length==2)  
     {  
       if(head.val<=head.next.val)  
         return head;  
       ListNode dummy=new ListNode(0);  
       dummy.next=head.next;  
       head.next=null;  
       dummy.next.next=head;  
       return dummy.next;  
     }  
     ListNode pre=head;  
     for(int i=0;i<length/2-1;i++)  
       pre=pre.next;  
     ListNode secondHead=pre.next;  
     pre.next=null;  
     return merge(mergeSort(head,length/2),mergeSort(secondHead,length-length/2));  
   }  
   public ListNode merge(ListNode head1,ListNode head2)  
   {  
     if(head1==null)  
       return head2;  
     if(head2==null)  
       return head1;  
     ListNode dummy=new ListNode(0);  
     ListNode cur=dummy;  
     while(head1!=null&&head2!=null)  
     {  
       int val1=head1.val;  
       int val2=head2.val;  
       if(val1<=val2)  
       {  
         cur.next=head1;  
         head1=head1.next;  
       }  
       else  
       {  
         cur.next=head2;  
         head2=head2.next;  
       }  
       cur=cur.next;  
     }  
     if(head1!=null)  
       cur.next=head1;  
     if(head2!=null)  
       cur.next=head2;  
     return dummy.next;  
   }  
   public int getLength(ListNode head)  
   {  
     int counter=0;  
     while(head!=null)  
     {  
       counter+=1;  
       head=head.next;  
     }  
     return counter;  
   }  
 }  

Merge k Sorted Lists (LeetCode Linked List)

Question:  Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Idea: I tried to make use of merge 2 sorted linked lists. However it gets exceed time limits error in Java. So I have to use heap sort. First insert all the heads of the lists to the heap. Pop the root of the heap and insert the root's next to the heap, until the heap becomes empty.

Time: O(n^2lgn) Space: O(n). Assume we have n lists each of which has n elements.

Code:

 public class Solution {  
   public Comparator<ListNode> comp=new Comparator<ListNode>()  
   {  
     public int compare(ListNode left,ListNode right)  
     {  
       if(left==null)  
         return 1;  
       else if(right==null)  
         return -1;  
       else  
         return left.val-right.val;  
     }  
   };  
   public ListNode mergeKLists(List<ListNode> lists) {  
     if(lists.size()==0)   
       return null;  
     Queue<ListNode> heap=new PriorityQueue<ListNode>(lists.size(),comp);  
     for(ListNode head:lists)  
     {  
       if(head!=null)  
         heap.add(head);  
     }  
     ListNode dummy=new ListNode(0);  
     ListNode tail=dummy;  
     while(!heap.isEmpty())  
     {  
       ListNode tmp=heap.poll();  
       tail.next=tmp;  
       tail=tail.next;  
       if(tmp.next!=null)  
         heap.add(tmp.next);  
     }  
     return dummy.next;  
   }  
 }  

Insertion Sort List (LeetCode Linked List)

Question: Sort a linked list using insertion sort.

Idea: Create a constant dummy head. Then traversal the linked list. Whenever a node, say node i, is visited, initial a pointer to start from the dummy head and find the position to insert the node i.  After finishing the traversal, the sort is done. Return the dummy head's next node.

Time: O(n^2)  Space: O(1)

Code:

 public class Solution {  
   public ListNode insertionSortList(ListNode head) {  
     ListNode dummy=new ListNode(Integer.MIN_VALUE);  
     while(head!=null)  
     {  
       ListNode tmp=dummy;  
       while(tmp.next!=null&&tmp.next.val<head.val)  
         tmp=tmp.next;  
       ListNode nextNode=head.next;  
       head.next=tmp.next;  
       tmp.next=head;  
       head=nextNode;  
     }  
     return dummy.next;  
   }  
 }  

First Missing Positive (LeetCode Array)

Question:  Given an unsorted integer array, find the first missing positive integer.
For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.
Your algorithm should run in O(n) time and uses constant space.

Idea: Assume there is a perfect array without any missing number in the middle, e.g. [1,2,3,4,5,6,..., n-1,n], the first missing positive number is n+1. However, some of the values in the perfect array may be missing and some numbers in the range (-infinite,0) and (n+1, +infinite) may be mixed together with the perfect array.

So the idea of looking for the first missing positive is to reconstruct the perfect array.  Assume the length of the input array is N, the corresponding perfect array is (1,2,...,N). Then we scan the input array from left to right, and try to put the numbers i from perfect array to index i-1, e.g. number 1 to index 0. Finally we scan the modified array to test whether there is an number missing from the perfect array, where missing means number i is not at index i-1, e.g. 1 is not at index 0.

Time: O(n) Space: O(1)

Code:  

 public class Solution {  
   public int firstMissingPositive(int[] A) {  
     bucketSort(A);  
     for(int i=0;i<A.length;i++)  
     {  
       if(A[i]!=i+1)  
         return i+1;  
     }  
     return A.length+1;  
   }  
   public void bucketSort(int[] A)  
   {  
     for(int i=0;i<A.length;i++)  
     {  
       while(A[i]!=i+1)  
       {  
         if(A[i]<=0||A[i]>A.length||A[i]==A[A[i]-1])  
           break;  
         else  
           swap(A,i,A[i]-1);  
       }  
     }  
   }  
   public void swap(int[] A,int i,int j)  
   {  
     int tmp=A[i];  
     A[i]=A[j];  
     A[j]=tmp;  
   }  
 }