Leetcode: Largest Number

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.

Credits:
Special thanks to @ts for adding this problem and creating all test cases.

Understand the problem:
The problem suggests to sort the array first according to the lexco order. The sorting rule is if two strings a and b, we compares ab and ba, and sort it in descending order.

The only thing needs to take care is the leading zeros in the final results. If there are leading zeros, it must be the case like 0, 0, 0, 0 ... i.e all array elements must be 0. In this case, return "0".

Code (Java):

public class Solution {
    public String largestNumber(int[] nums) {
        if (nums == null || nums.length == 0) {
            return "";
        }
        String[] strs = new String[nums.length];
        for (int i = 0; i < strs.length; i++) {
            strs[i] = String.valueOf(nums[i]);
        }
        
        Arrays.sort(strs, new StringComparator());
        
        StringBuffer sb = new StringBuffer();
        
        for (String str : strs) {
            sb.append(str);
        }
        
        if (sb.charAt(0) == '0') {
            return "0";
        }
        
        return sb.toString();
    }
    
    public class StringComparator implements Comparator<String> {
        @Override
        public int compare (String str1, String str2) {
            String ab = str1 + str2;
            String ba = str2 + str1;
            return ba.compareTo(ab);
        }
    }
}

Leetcode: Maximum Gap

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.

Understand the problem:
We problem is not clearly defined. We can use an example to show.  e.g. 
A[] = {1, 7, 3, 4}
In the sorted form, it is 1 3 4 7, and the maximum gap is between 4 and 7, which is 3. 

Since the problem asks for O(n) time and space solution, we need to think of using a bucket sorting. 

 -- Step 1: Calculate the ave. interval. We calculate the min and max of the array A[], and the maximum gap should be in the upper bound of (max - min) / (N - 1). For example, for the example shown above, if the number is uniformly distributed, the gap is (7 - 1) / 3 = 2, i.e, the array should be 1 3 5 7. 
Since now the number may not be uniformly distributed, the maximum gap might be greater than 2. 
 -- Step 2: Determine the number of buckets, which should be (max - min) / interval + 1. The number of buckets should be equal to the range of numbers / range per bucket. 
  -- Step 3: Determine which number is in which bucket, which equals to (A[i] - min) / interval. e.g. (7 - 1) / 2 = 3, in bucket[3]. 
  -- Step 4: We only need to maintain the min and max value for each bucket. The maximum gap must between two adj. buckets instead of within a bucket. That is because the maximum gap inside of a bucket is interval - 1. However, in the step 1 we have already known that the the maximal gap must be greater than interval. 
  -- Step 5. After we calculated the min and max value in each bucket, we then iterate through the buckets and get the maximal gap between buckets. Be very careful that buckets might be empty. 

Code (Java):

public class Solution {
    public int maximumGap(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return 0;
        }
        
        // Step 1: find max and min element
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for (int num : nums) {
            if (num > max) {
                max = num;
            }
            
            if (num < min) {
                min = num;
            }
        }
        
        int len = nums.length;
        
        // Step 2: calculate the intervals and number of buckets. 
        int interval = (int) Math.ceil((double) (max - min) / (len - 1));

        if (interval == 0) {
            interval = 1;
        }
        int numBuckets = (max - min) / interval + 1;
        Bucket[] buckets = new Bucket[numBuckets];
        for (int i = 0; i < numBuckets; i++) {
            buckets[i] = new Bucket();
        }
        
        // Step 3: iterate through the nums and assign the number into the buckets. 
        for (int num : nums) {
            int bucketNum = (num - min) / interval;
            if (num > buckets[bucketNum].max) {
                buckets[bucketNum].max = num;
            }
            
            if (num < buckets[bucketNum].min) {
                buckets[bucketNum].min = num;
            }
        }
        
        // Step 4: iterate through the buckets and get the maximal gap
        int prev = buckets[0].max;
        int maxGap = 0;
        for (int i = 1; i < numBuckets; i++) {
            if (prev != Integer.MIN_VALUE && buckets[i].min != Integer.MAX_VALUE) {
                maxGap = Math.max(maxGap, buckets[i].min - prev);
                prev = buckets[i].max;
            }
        }
        
        return maxGap;
    }
    
    private class Bucket {
        public int min;
        public int max;
        
        public Bucket() {
            min = Integer.MAX_VALUE;
            max = Integer.MIN_VALUE;
        }
    }
}

Update on 5/20/19:

public class Solution {
    /**
     * @param nums: an array of integers
     * @return: the maximun difference
     */
    public int maximumGap(int[] nums) {
        // write your code here
        if (nums == null || nums.length < 2) {
            return 0;
        }
        
        int[] minMax = findMinMax(nums);
        int min = minMax[0];
        int max = minMax[1];
        int numBuckets = nums.length;
        
        Bucket[] buckets = new Bucket[numBuckets];
        for (int i = 0; i < numBuckets; i++) {
            buckets[i] = new Bucket();
        }
        int capacity = (int)Math.ceil(((double)max - min + 1) / numBuckets);
        
        for (int num : nums) {
            int bucketIdx = (num - min) / capacity;
            
            if (buckets[bucketIdx].min == -1 || buckets[bucketIdx].min > num) {
                buckets[bucketIdx].min = num;
            }
            
            if (buckets[bucketIdx].max == -1 || buckets[bucketIdx].max < num) {
                buckets[bucketIdx].max = num;
            }
        }
        
        int maxGap = 0;
        Bucket prevBucket = buckets[0];
        for (int i = 1; i < numBuckets; i++) {
            if (buckets[i].min == - 1 || buckets[i].max == -1) {
                continue;
            }
            
            maxGap = Math.max(maxGap, buckets[i].max - buckets[i].min);
            if (prevBucket.min != -1 && prevBucket.max != -1) {
                maxGap = Math.max(maxGap, buckets[i].min - prevBucket.max);
            }
            
            prevBucket = buckets[i];
            
        }
        
        return maxGap;
    }
    
    private int[] findMinMax(int[] nums) {
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        
        for (int num : nums) {
            max = Math.max(max, num);
            min = Math.min(min, num);
        }
        
        int[] ans = new int[2];
        ans[0] = min;
        ans[1] = max;
        
        return ans;
    }
}

class Bucket {
    int min;
    int max;
    public Bucket() {
        min = -1;
        max = -1;
    }
}

Data Structure & Algorithms : Sorting

Quick Sort:

public class Quick {
    public void quickSort(int[] A) {
        if (A == null || A.length <= 1) {
            return;
        }
        
        //Collections.shuffle(A);
        quickSortHelper(A, 0, A.length - 1);
    }

    private void quickSortHelper(int[] A, int lo, int hi) {
        if (lo >= hi) {
            return;
        }

        int j = partition(A, lo, hi);
        quickSortHelper(A, lo, j - 1);
        quickSortHelper(A, j + 1, hi);
    }
    
     //  partition the subarray a[lo..hi] so that a[lo..j-1] <= a[j] <=
     //  a[j+1..hi]
     //  and return the index j.
    private int partition(int[] A, int lo, int hi) {
        int pivot = A[lo];
        int i = lo + 1;
        int j = hi;

        while (i <= j) {
            while (i <= j && A[i] < pivot) {
                i++;
            }

            while (i <= j && A[j] > pivot) {
                j--;
            }
            if (i <= j) {
                swap(A, i, j);
            }
        }

        // swap the pivot 
        swap(A, lo, j);

        return j;
    }

    private void swap(int[] A, int i, int j) {
        int temp = A[i];
        A[i] = A[j];
        A[j] = temp; 
    }
    
    public static void main(String[] args) {
         int[] A = new int[]{-5,4,2,-6};

         Quick quick = new Quick();
         quick.quickSort(A);

         for (int i = 0; i < A.length; i++) {
            System.out.print(A[i] + " ");
         }

         System.out.println();
    }
}

Follow-up:
When is the quick sort has time complexity of O(n^2)?

The Quick sort performs worst ie, at O(n^2) when all the values of the pivot chosen is either the largest or smallest of the taken set. Consider this example.

1 2 3 4 5

The pivot chosen say is 1, you will have 4 elements on the right side of the pivot and no elements on the left side. Applying this same logic recursively and the pivot chosen is 2, 3, 4, 5 respectively, we have attained a situation where this sort has performed at its worst possible time.

It has been recommended and proven that Quicksort performs well if the input is shuffled well.

Moreover, selection of a sort usually depends on a clear knowledge about the input domain. For example, if the input is huge, then there is something called as external sort which may use external memory. If the input size is very small, we may go for a merge sort but not for medium and huge input sets since it uses extra memory. The main advantage of Quick sort is its "in-place"ness meaning, no extra memory is being used for the input data. Its worst case time on paper is O(n^2) but still is widely preferred and used. My point here is, sorting algorithms can be changed based on the knowledge on the input set and its a matter of preference.

Merge Sort:

public class MergeSort {
    public void mergeSort(int[] A) {
        if (A == null || A.length <= 1) {
            return;
        }
        
        int[] Aux = new int[A.length];

        divide(A, Aux, 0, A.length - 1);
    }

    private void divide(int[] A, int[] Aux, int lo, int hi) {
        if (lo >= hi) {
            return;
        }

        int mid = lo + (hi - lo) / 2;

        divide(A, Aux, lo, mid);
        divide(A, Aux, mid + 1, hi);

        merge(A, Aux, lo, mid, hi);
    }

    private void merge(int[] A, int[] Aux, int lo, int mid, int hi) {
        // copy A to Aux
        for (int k = lo; k <= hi; k++) {
            Aux[k] = A[k];
        }

        int i = lo;
        int j = mid + 1;

        for (int k = lo; k <= hi; k++) {
            if (i > mid) {
                A[k] = Aux[j++];
            } else if (j > hi) {
                A[k] = Aux[i++];
            } else if (Aux[i] <= Aux[j]) {
                A[k] = Aux[i++];
            } else {
                A[k] = Aux[j++];
            }
        }
    }

    public static void main(String[] args) {
         int[] A = new int[]{3,1};

         MergeSort merge = new MergeSort();
         merge.mergeSort(A);

         for (int i = 0; i < A.length; i++) {
            System.out.print(A[i] + " ");
         }

         System.out.println();
    }
}

Leetcode: Insertion Sort List

Sort a linked list using insertion sort.
Understand the problem:
The crux of the problem is to understand what is the insertion sort. Basically, the idea of the insertion sort is for a partially sorted list, say, A[] = {1 3 4 5}, and we wanna insert 2 to the list at an appropriate position. In general, the idea of the insertion sort is for a given point i, we wanna make sure its left noes are well sorted. How to achieve this? compare A[i] with A[i -1], if less, swap. 

Solution:

/**
 * 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 || head.next == null) {
            return head;
        }
        
        ListNode newHead = new ListNode(Integer.MIN_VALUE);
        ListNode prev = newHead;
        ListNode curr = head;
        
        while (curr != null) {
            prev = newHead;
            ListNode next = curr.next;
            
            while (prev.next != null && prev.next.val < curr.val) {
                prev = prev.next;
            }
            
            curr.next = prev.next;
            prev.next = curr;
            
            curr = next;
        }
        
        return newHead.next;
    }

}

Leetcode: Sort List

Sort a linked list in O(n log n) time using constant space complexity.
Understand the problem:
The problem is very straight-forward. The only requirement is O(n logn) time complexity, so it indicates to use quick sort or merge sort. 

In this question we choose the merge sort because quick sort requires many swap operations, which are relatively complicated in the linked list structure. 

Solution:

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        
        // find the middle point
        ListNode slow = head;
        ListNode fast = head;
        
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        
        ListNode leftHead = head;
        ListNode rightHead = slow.next;
        
        slow.next = null;
        
        // recursively merge
        leftHead = sortList(leftHead);
        rightHead = sortList(rightHead);
        
        ListNode mergeHead = merge(leftHead, rightHead);
        
        return mergeHead;
    }
    
    private ListNode merge(ListNode leftHead, ListNode rightHead) {
        ListNode newHead = new ListNode(0);
        ListNode curr = newHead;
        
        while (leftHead != null || rightHead != null) {
            if (leftHead == null) {
                curr.next = rightHead;
                break;
            }
            
            if (rightHead == null) {
                curr.next = leftHead;
                break;
            }
            
            if (leftHead.val <= rightHead.val) {
                curr.next = leftHead;
                leftHead = leftHead.next;
                curr = curr.next;
            } else {
                curr.next = rightHead;
                rightHead = rightHead.next;
                curr = curr.next;
            }
        }
        
        return newHead.next;
    }
}

Summary:
The take-away message for this problem is to be very familiar with common sorting algorithms. 

Leetcode: Sort Colors

Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note:
You are not suppose to use the library's sort function for this problem.

click to show follow up.

Follow up:
A rather straight forward solution is a two-pass algorithm using counting sort.
First, iterate the array counting number of 0's, 1's, and 2's, then overwrite array with total number of 0's, then 1's and followed by 2's.

Could you come up with an one-pass algorithm using only constant space?

Understand the problem:
The problem reads likes an application problem. However, if you can abstract from it, it actually gives you an arrays of integers, with the number 0, 1, and 2. For example, 1, 1, 2, 0, 1, 0, 1. Then you are asked to sort it out. Note that you are not allowed to use any sorting libraries like quick sort. 

Naive Solution:
Since you know that the array is composed by only 0s, 1s and 2s. You should naturally think about the bucket sort. There are three buckets, of each contains 0s, 1s, and 2s. The most straight-forward solution is first to count the number of 0s, 1s and 2s respectively. Then in the second pass fill the original array with the number of 0, 1, and 2. 

Code (Java):

public class Solution {
    public void sortColors(int[] A) {
        if (A == null || A.length <= 1) {
            return;
        }
        
        int num0 = 0;
        int num1 = 0;
        int num2 = 0;
        
        for (int i = 0; i < A.length; i++) {
            switch(A[i]) {
                case 0: ++num0;
                        break;
                case 1: ++num1;
                        break;
                case 2: ++num2;
                        break;
            }
        }
        
        int j = 0;
        for (j = 0; j < num0; j++) {
            A[j] = 0;
        }
        
        for (j = 0; j < num1; j++) {
            A[num0 + j] = 1;
        }
        
        for (j = 0; j < num2; j++) {
            A[num0 + num1 + j] = 2;
        }
    }
}

A better approach:
The question asks for solving the problem using only one pass of the array. Since the array is only composed of 0, 1, and 2, we can naturally think of using two pointers approach. We use two pointers, red and blue, points to the starting and end of the array initially. Then iterate index i from 0 to the end of the array. If A[i] == 0, move it to red pointer. If A[i] == 2, move it to blue pointer. Else move on. 

Code (Java):

public class Solution {
    public void sortColors(int[] A) {
        if (A == null || A.length <= 1) {
            return;
        }
        
        int red = 0;
        int blue = A.length - 1;
        
        int i = 0;
        while (i <= blue) {
            if (A[i] == 0) {
                swap(A, i, red);
                red++;
                i++;
            } else if (A[i] == 2) {
                swap(A, i, blue);
                blue--;
            } else {
                i++;
            }
        }
    }
    
    private void swap(int[] A, int i, int j) {
        int temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }
}

Discussion:
Note that the increase of index i. For A[i] == 0, we must increase the index of i once we swap A[i] and A[red], because i cannot be less than red. For the A[i] == 2, we don't need to increase i, since now A[i] could be possible 0 since it is swapped with 2. We need to check that number.

Summary:
This problem is actually a 3-way partition problem. 

Leetcode: Search in Rotated Sorted Array

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

Understand the problem:
The problem gives a sorted array which is rotated at some pivot, search for a target value. This problem clearly indicates that we do find the number in O(logn) time, just as binary search. 

One naive idea is to find the pivot and rotate the array back, then we can apply the binary search. But rotating the array would take on average O(n) time, which is not allowed in this problem. 

Solution:
The solution is very similar to binary search. Note that no matter how we rotated the array, there must be at least one part which is sorted. If the target is at the sorted part, we just search that part until we found; else we go the unsorted part. 

Code (Java):

public class Solution {
    public int search(int[] A, int target) {
        if (A == null || A.length == 0) {
            return -1;
        }
        
        int lo = 0;
        int hi = A.length - 1;
        
        while (lo <= hi) {
            int mid = (lo + hi) / 2;
            if (A[mid] == target) {
                return mid;
            }
            
            if (A[lo] <= A[mid]) {
                if (target >= A[lo] && target < A[mid]) {
                    hi = mid - 1;
                } else {
                    lo = mid + 1;
                }
            } else {
                if (A[mid] < target && target <= A[hi]) {
                    lo = mid + 1;
                } else {
                    hi = mid - 1;
                }
            }
        }
        return -1;
    }
}

Discussion:
Now let's analyze the complexity. If the target just falls into the sorted part, the complexity could be O(logn). How about the worst case, where target is always not in the sorted part, then we have to iterate all the data of the array, then the complexity becomes O(n). So on average, we can see that the complexity is O(logn).

Summary:
This is an extension of the binary search. So it is very important that you got familiar with the binary search. 

Update on 9/29/14:

public class Solution {
    public int search(int[] A, int target) {
        if (A == null || A.length == 0) {
            return -1;
        }
        
        int lo = 0;
        int hi = A.length - 1;
        
        while (lo + 1 < hi) {
            int mid = lo + (hi - lo) / 2;
            if (A[mid] == target) {
                return mid;
            }
            
            if (A[lo] <= A[mid]) {
                if (A[lo] <= target && target < A[mid]) {
                    hi = mid;
                } else {
                    lo = mid;
                }
            } else {
                if (A[mid] < target && target <= A[hi] ) {
                    lo = mid;
                } else {
                    hi = mid;
                }
            }
        }
        
        if (target == A[lo]) {
            return lo;
        }
        
        if (target == A[hi]) {
            return hi;
        }
        
        return -1;
        
    }
}

Update on 7/13/18:

class Solution {
    public int search(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        
        int ans = -1;
        
        int lo = 0;
        int hi = nums.length - 1;
        
        while (lo + 1 < hi) {
            int mid = lo + (hi - lo) / 2;
            if (nums[mid] == target) {
                return mid;
            } else {
                // case 1: left half is sorted
                //
                if (nums[lo] < nums[mid]) {
                    if (target >= nums[lo] && target < nums[mid]) {
                        hi = mid - 1;
                    } else {
                        lo = mid + 1;
                    }
                } else if (nums[mid] < nums[hi]) {
                    if (target > nums[mid] && target <= nums[hi]) {
                        lo = mid + 1;
                    } else {
                        hi = mid - 1;
                    }
                }
            }
        }
        
        if (nums[lo] == target) {
            return lo;
        }
        
        if (nums[hi] == target) {
            return hi;
        }
        
        return -1;
    }
}

Leetcode: Insert Interval

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

Example 1:
Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].

Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].

This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].

Understand the Problem:

This problem is very similar to merge interval. The question asks for given a set of non-overlapping intervals, insert a new interval into the intervals, and merge them, if necessary. 

So the question can be divided by two steps: insert and merge. 

Also note that the intervals has already been sorted initially.

Solution:
Since the problem can be divided by two steps, insert and merge, we can do it step by step. Insertion is very simple, we just need to scan the input intervals and compare the start value until we found one is larger than the insert interval. Then we insert the token into the ArrayList. The merge process will be exactly the same as the Merge Interval problem. 

Code (Java):

/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
public class Solution {
    public ArrayList<Interval> insert(ArrayList<Interval> intervals, Interval newInterval) {
        ArrayList<Interval> result = new ArrayList<Interval>();
        
        // check if the list is empty or null
        if (intervals == null || newInterval == null) return result;
        
        if (intervals.isEmpty()) {
            result.add(newInterval);
            return result;
        }
        
        // find the insertion point and insert the new newInterval
        for (int i = 0; i < intervals.size(); i++) {
            if (intervals.get(i).start > newInterval.start) {
                intervals.add(i, newInterval);
                break;
            }
        }
        // insert at end of the list
        intervals.add(newInterval);
        
        // merge the overlapped intervals
        Interval prev = intervals.get(0);
        for (int i = 1; i < intervals.size(); i++) {
            Interval curr = intervals.get(i);
            if (isOverlapped(prev, curr)) {
                Interval temp = new Interval();
                temp.start = prev.start;
                temp.end = Math.max(prev.end, curr.end);
                prev = temp;
            } else {
                result.add(prev);
                prev = curr;
            }
        }
        result.add(prev);
        
        return result;
    }
    
    private boolean isOverlapped(Interval prev, Interval curr) {
        return curr.start <= prev.end;
    }
}

Discussion:
Note the method add(int index, E element) inserts the elements into the current index.  Shifts the element currently at that position (if any) and any subsequent elements to the right (adds one to their indices). That's why we could use add() instance method and no worry it is replace the value in the insertion position. In addition, when we insert a value, take care if the value is greater than the largest one in the list. In this case, we have to insert the value at the end of the end, as is shown in Line 30 of the code. This is a tricky bug we are easily to forget. 

Note that this solution has two downsides. First of all, intervals.add() will modify the input parameters, which is sometimes not allowed. Second, insert an number at middle will cause the shift of all its right elements. 



A Better Solution:
Does there exist a better solution without needing to modify the input parameters? The answer is yes. Re-think the question. We are not actually required to insert an interval into the original. We are only asked to return the final merged list. 

Following this idea, we could decide when we insert an internal, what needs to be inserted into the result list. There are three cases:
1. For the current interval is less than the newInterval, i.e, the end of current interval is less than the start of newInterval. Then there must have no overlapping. In this case, we only need to insert the current interval into the result list. 
2. For the current interval is greater than the newInterval. That is, the start of the current interval is greater than the end of newInterval. In this case, we insert the newInterval into the result list, and update the newInterval as current interval. 
3. For other cases where we have overlapped regions. We merge the two intervals and update the newInterval. 

Code (Java):

/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
public class Solution {
    public ArrayList<Interval> insert(ArrayList<Interval> intervals, Interval newInterval) {
        ArrayList<Interval> result = new ArrayList<Interval>();
        
        if (newInterval == null) return intervals;
        
        if (intervals == null || intervals.size() == 0) {
            result.add(newInterval);
            return result;
        }
        
        Interval prev = newInterval;
        
        for (Interval curr : intervals) {
            // if curr interval is greater than prev
            if (curr.start > prev.end) {
                result.add(prev);
                prev = curr;
            } else if (curr.end < prev.start) {
                result.add(curr);
            } else {
                prev.start = Math.min(prev.start, curr.start);
                prev.end = Math.max(prev.end, curr.end);
            }
        }
        result.add(prev);
        return result;
    }
}

Summary:
The problem is not hard at the first glance, but very tricky to come out the second solution. If you follow the hint of the question you will insert then merge. Then you have to modify the input array to insert the new inserted point.  A smarter way is to compare each interval from the input array with the insertion interval, and determine if they overlapped. We only need to insert the interval when they are not overlapped. This is quite close to the merge interval question. 

Leetcode: Merge Intervals

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].

Understand the problem:
For question asks for given a collection of intervals, merge all overlapping intervals. So the crux of the problem is to understand "what is the overlapping intervals"? Let's take look at several examples:

For the intervals [1, 3], [2, 6], they are overlapped, because the left boundary of the second token is less than the right boundary of the first token. 

For the intervals [2, 6], [8, 10], they are not overlapped, because again, the left boundary of the second token is greater than the right boundary of the first token. 

Therefore, one method to know if two intervals are overlapped is to first sort the list of intervals according to the left boundary, then compare the left boundary of the second interval with the right boundary of the first interval.

Then, the next question is after we decided two intervals overlapped, how can we merge them together? A easy way is to choose the minimum value of the left boundary, and maximum value of the right boundary. For example, for [1, 3] and [2, 6], the merged interval is [1, 6]. 

Solution:
According to the analysis above, the solution is quite straight-forward. We first sort the array list according to the start value of the Interval. Then check if two intervals are overlapped, if yes, merge together.

Code (Java):

/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
public class Solution {
    public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
        ArrayList<Interval> result = new ArrayList<Interval>();
        if (intervals == null || intervals.size() == 0) {
            return result;
        }
        
        Collections.sort(intervals, new IntervalComparator());
        
        Interval prev = intervals.get(0);
        for (int i = 1; i < intervals.size(); i++) {
            Interval curr = intervals.get(i);
            if (isOverlapped(curr, prev)) {
                prev.start = prev.start;
                prev.end = Math.max(curr.end, prev.end);
            } else {
                result.add(prev);
                prev = curr;
            }
        }
        
        result.add(prev);
        return result;
    }
    
    private boolean isOverlapped(Interval curr, Interval prev) {
        return curr.start <= prev.end;
    }
    
    private class IntervalComparator implements Comparator<Interval> {
        public int compare(Interval a, Interval b) {
            return a.start - b.start;
        }
    }
}

Discussion:
Since we sort the list once before, the time complexity bounded by O(nlogn). For the space complexity, we only allocated a new list to store the results, so the space complexity at worst case is O(n). That is the best space complexity we can do required by this question.

Summary:
The take away message of the solution is to utilize the advantage of sorted array. Also, make sure you are familiar with sorting objects in Java.