[LeetCode Java Solution] – sort/ two pointers/ merge- Merge k Sorted Lists

Problem:

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

Method 1:

MergeSort. This is a very typical implementation for MergeSort by using array.

Code for method 1:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;
        return helper(lists, 0, lists.length-1);
    }
    
    public ListNode helper (ListNode[] lists, int l, int h){
        if (l < h){
             int mid = (l + h)/2;
             return merge(helper(lists, l, mid), helper(lists, mid+1, h));
        }
        return lists[l];
    }
    
    public ListNode merge(ListNode l1, ListNode l2){
        ListNode dummy = new ListNode(0);
        ListNode temp = dummy;
        while (l1 != null && l2 != null){
            if (l1.val < l2.val){
                temp.next = l1;
                temp = temp.next;
                l1 = l1.next;
            }else{
                temp.next = l2;
                temp = temp.next;
                l2 = l2.next;
            }
        }
        if (l1 != null){
            temp.next = l1;
        }
        if (l2 != null){
            temp.next = l2;
        }
        return dummy.next;
    }
}

Analysis for time complexity:

Suppose there are k lists, and there are n elements inside each list. The time complexity is O(nklogk).

Method 2:

Use heap. Suppose we have k lists, and for each list, there are at most n elements.

Maintain a list of k elements. And always remove the first element from the list. After removing an element, add the element after it to the heap.

Code for method 2:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> heap = new PriorityQueue<ListNode>(10, new Comparator<ListNode>(){
            public int compare (ListNode l1, ListNode l2){
                return l1.val - l2.val;
            }
        });
        
        for (int i = 0; i < lists.length; i++){
            ListNode temp = lists[i];
            if (temp != null){
                heap.offer(temp);
            }
        }
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        
        while (heap.size() != 0){
            ListNode n = heap.poll();
            cur.next = n;
            cur = cur.next;
            if (n.next != null){
                heap.offer(n.next);
            }
        }
        return dummy.next;
    }
}

Analysis for time complexity:

We have to insert at most k*n nodes, and for each node to be in order in the heap, we need log(k) time (“Bottom Up Insertion”). So total time complexity is also knlog(k).

[LeetCode] – sort, merge – Merge Intervals

Problem:

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

Method 1:

Use the code for ‘Insert Intervals’.

Code for Method 1:

/**
 * 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(List<Interval> intervals) {
        ArrayList<Interval> res = new ArrayList<Interval>();
        for (int i = 0; i < intervals.size(); i++){
            res = insert(res, intervals.get(i));
        }
        return res;
    }
    
    public ArrayList<Interval> insert(List<Interval> intervals, Interval newInterval){
        ArrayList<Interval> res = new ArrayList<Interval>();
        ArrayList<Interval> resb = new ArrayList<Interval>();
        if (intervals.size() == 0 ){
            res.add(newInterval);
            return res;
        }
        
        for (Interval i: intervals){
            if (i.end < newInterval.start) res.add(i);
            else if (newInterval.end < i.start) resb.add(i);
            else {
                newInterval.start = Math.min (i.start, newInterval.start);
                newInterval.end = Math.max (i.end, newInterval.end);
            }
        }
        res.add(newInterval);
        res.addAll(resb);
        return res;
    }
}

Method 2:

First, sort all the intervals according to their starting values. Then, add one into res. (We always keep last one in the res to be unsure. ) Every time, we get the last element of res, compare it with the current Interval in the set intervals. Basically only compare the “end” value.
Code for method 2:

/**
 * 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(List<Interval> intervals) {
        ArrayList<Interval> res = new ArrayList<Interval>();
        if (intervals == null || intervals.size() == 0) return res;
        
        Comparator<Interval> comp = new Comparator<Interval>(){
            public int compare(Interval i1, Interval i2){
                if (i1.start > i2.start) return 1;
                else if (i1.start < i2.start) return -1;
                else return 0;
            }
        };
        Collections.sort(intervals, comp);
        
        res.add(intervals.get(0));
        
        for (int i = 1; i < intervals.size(); i++){
            if (res.get(res.size()-1).end >= intervals.get(i).start){
                res.get(res.size()-1).end = Math.max(res.get(res.size()-1).end, intervals.get(i).end);
            }else{
                res.add(intervals.get(i));
            }
        }
        return res;
    }
}

[LeetCode] -sort, merge – Insert Interval

Problem:

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

Method:

1. Iterate through the intervals set.

• If this.end < newInterval.start. No overlap, add this to res;
• If this.start > newInterval.end. No overlap, add this to res;
• If this.end >=newInterval.start || this.start <=newInterval.end. Merge and then add new interval to res.

Code:

/**
 * 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(List<Interval> intervals, Interval newInterval) {
        ArrayList<Interval> res = new ArrayList<Interval>();
        ArrayList<Interval> resb = new ArrayList<Interval>();
        
        if (intervals.size() == 0) {
            res.add(newInterval);
            return res;
        }
        
        for (Interval i: intervals){
            if (i.end < newInterval.start) res.add(i);
            else if (i.start > newInterval.end) resb.add(i);
            else if (i.end >= newInterval.start || i.start <= newInterval.end){
                newInterval.start = Math.min(i.start,newInterval.start);
                newInterval.end = Math.max(i.end,newInterval.end);
            }
        }
        res.add(newInterval);
        res.addAll(resb);
        
        return res;
    }
}

[LeetCode] – Sort/ Two pointers/Merge – Merge Two Sorted List

Problem:

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Method 1:

1. Use two pointers to move through the two lists. Compare and link the smaller one to the result list.

2. Use a dummy node to avoid choosing head for the new list.

3. To save space, do not have to create new node.

Code for method 1:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null && l2 == null) return null;
   
        ListNode dummy = new ListNode(1);
        ListNode temp0 = dummy;
        ListNode temp1 = l1;
        ListNode temp2 = l2;
        
        while (temp1 != null && temp2 != null){
            if (temp1.val <= temp2.val){
              //  ListNode item = new ListNode(temp1.val);
              // to save space, do not have to create new object
                temp0.next = temp1;
                temp1 = temp1.next;
                temp0 = temp0.next;
            }else{
            //    ListNode item = new ListNode(temp2.val);
                temp0.next = temp2;
                temp2 = temp2.next;
                temp0 = temp0.next;
            }
        }
        if (temp1 != null){
            temp0.next = temp1;
        }
        if (temp2 != null){
            temp0.next = temp2;
        }
        return dummy.next;
    }
}

[LeetCode] – Sort / Two pointer – Two sum

Problem:

Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

Method 1:

Use two for loops. Time complexity is O(n^2). Bad and slow.

Code for method 1:

public class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] res = new int[2];
        int id1 = 0;
        int id2 = 0;
        
        for (id1 = 0; id1 < nums.length; id1++){
            for (id2 = id1 + 1; id2< nums.length; id2++){
                if (nums[id1] + nums[id2] == target){
                    res[0] = id1+1;
                    res[1] = id2+1;
                    return res;
                }
            }
        }
        
        return res;
    }
}

Method 2: by Hash Table

This is a very cool method!!!

Key: the numbers in the array

Value: index

When we encounter a value nums[i], we want to know if we already encountered (target-nums[i]). Hash table helps to quick look it up.

Time complexity: O(n)

Code for method 2: 

public class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] res = new int[2];
        if (nums == null || nums.length < 2 ) return res;
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        
        for (int i = 0; i < nums.length; i++){
            if (!map.containsKey(target - nums[i])){
                map.put(nums[i],i);
            }else{
                res[0] = map.get(target - nums[i]) + 1 ;
                res[1] = ++i;
                break;
            }
        }
        return res;
    }
}

Method 3:

By using two pointers.

• Copy the array to a new array and sort it . Details: System.arraycopy(nums,0, sorted, 0,nums.length);  Arrays.sort(sorted)
• Have two points, one at the beginning, one at the end. And then move then towards the center of the array.
• Once find the two numbers adding up to target, go on to find their index in the original array.
• Sort the result array.

Time complexity:

O(nlogn)

Code for method 3:

public class Solution {
    public int[] twoSum(int[] nums, int target) {
        // copy and sort the original array;
        int[] sorted = new int[nums.length];
        System.arraycopy(nums, 0, sorted, 0, nums.length);
        Arrays.sort(sorted);
        
        int first = 0;
        int second = nums.length-1;
        
        while (first < second){
            if (sorted[first] + sorted[second] < target){
                first ++;
                continue;  
            }else if (sorted[first] + sorted[second] > target){
                second --;
                continue;
            }else{
                break;
            }
        }
        // find the indexs for sorted[first] and sorted[second]
        int index1 = -1;// so that we knwo whether it has to be copyed or not
        int index2 = -1;
        for (int i = 0; i < nums.length; i++){
            if (nums[i] == sorted[first] || nums[i] == sorted[second]){
                if (index1 == -1){
                    index1 = i+1;
                }else{
                    index2 = i+1;
                }
            }
        }
        // remeber to sort the result. 
        int[] res = {index1, index2};
        Arrays.sort(res);
        return res;
    }
}

[LeetCode] – Sorting – Sort Colors

Problem:

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.

Analyze:

Method 1:

Counting sort. First run, we count how many 0, 1 and 2 respectively. Then, just update the array.

Method 2:

In order to do it in one run, keep two tracker: ‘red’ and ‘blue’.

When i is red: swap i and ‘red’, and move ‘red’ forward one step.

When i is blue: swap i and ‘blue’, and move ‘blue’ backward one step.

When i is white: i++.

Code:

public class Solution {
    public void sortColors(int[] A) {
        int red = 0;
        int blue = A.length - 1;
        int temp;
        int i = 0;

        while (i <= blue){  // notice this: must have a equal sign
            if (A[i] == 0){
                temp = A[red];
                A[red] = A[i];
                A[i] = temp;
                red ++;
                i++;  // note: why have i++ here
            }else if (A[i] == 2){
                temp = A[blue];
                A[blue] = A[i];
                A[i] = temp;
                blue--;
                // note: why do not have i++
            }else{
                i++;

            }
        }

    }
}

[LeetCode] – Sorting – Merge two sorted list

Questions:

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Analyze:

Very easy and typical question.

Every time, we get one from each list, then compare them. Insert the smaller one to the new list. But don’t forget to add the left-over. (Only one list has left-over)

Code:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
       if (l1 == null && l2 == null){
           return null;
       }
       if (l1 == null) return l2;
       if (l2 == null) return l1;
       
       ListNode dummy = new ListNode(1);
       ListNode temp1 = l1;
       ListNode temp2 = l2;
       ListNode temp = dummy;
       
       while (temp1 != null && temp2 != null){
           ListNode item;
           if (temp1.val < temp2.val){
               item = new ListNode(temp1.val);
               temp1 = temp1.next;
           }else{
               item = new ListNode(temp2.val);
               temp2 = temp2.next;
           }
            temp.next = item;
            temp = temp.next;
       }
       if (temp1 != null){
           temp.next = temp1;
       }else{
           temp.next = temp2;
       }
       return dummy.next;
        
    }
}