Leetcode: Majority Element II

Difficulty: Medium

Majority Element II

Given an integer array of size n, find all elements that appear more than ⌊n/3⌋ times. The algorithm should run in linear time and in O(1) space.

Runtime Analysis:

Runtime: O(n)

Algorithmic Approach:

This problem can be solved using the Boyer-Moore majority vote algorithm.

Before we are digging into this algorithm, let's see one basic observation:
How many majority elements at most in this problem?
Answer: Two.
Explanation: At most there are 3 elements appear exactly n/3 times. So for more than n/3 times, at most there are 2 elements.

Now we discuss the Moore majority vote algorithm. Quoted from wiki:

"The algorithm is carried out in two steps:

1. Eliminate all elements except one.

Iterating through the array of numbers, maintain a current candidate and a counter initialized to 0. With the current element x in iteration, update the counter and (possibly) the candidate:

If the counter is 0, set the current candidate to x and the counter to 1. If the counter is not 0, increment or decrement the counter based on whether x is the current candidate.

2. Determine if the remaining element is a valid majority element.

With the candidate acquired in step 1, iterate through the array of numbers and count its occurrences. Determine if the result is more than half of the sequence's length. If so, the candidate is the majority. Otherwise, the sequence doesn't contain a majority."

The key idea of this algorithm is "decrement" of the counter when new elements are different from all the current candidates.  This "decrement" operation is to cancel out the elements that do not appear most times in the array. Therefore, after one scan, the candidates are the elements which appear most of the times. The last  step is to check if these candidates are satisfied with the condition of more than n/3 times.

Java Code: 

 public class Solution {





  public List<Integer> majorityElement(int[] nums) {
    if (nums == null || nums.length == 0)
        return new ArrayList<Integer>();
        
    List<Integer> result = new ArrayList<Integer>();
    int number1 = nums[0], number2 = nums[0];
    int count1 = 0, count2 = 0, len = nums.length;
    
    for (int i = 0; i < len; i++) {
        if (nums[i] == number1)
            count1++;
            
        else if (nums[i] == number2)
            count2++;
            
        else if (count1 == 0) {
            number1 = nums[i];
            count1 = 1;
        } 
        
        else if (count2 == 0) {
            number2 = nums[i];
            count2 = 1;
        } 
        
        else {
            count1--;
            count2--;
        }
    }
    
    count1 = 0;
    count2 = 0;
    
    for (int i = 0; i < len; i++) {
        if (nums[i] == number1)
            count1++;
            
        else if (nums[i] == number2)
            count2++;
    }
    
    if (count1 > len / 3)
        result.add(number1);
        
    if (count2 > len / 3)
        result.add(number2);
        
    return result;
}

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

Runtime Analysis:

Since we are given a set of n intervals, to combine them, we need to at least traverse each interval once, thus taking O(n) time where n is the number of intervals. The lower bound of our algorithm must at least be (Omega) Ω(n). 
  
One possible approach would be to sort the list of intervals by:

1. Starting Value
2. Ending Value

In this case, you would get a list of sorted intervals by their starting values. To sort the intervals, you could: 

1. Create your own interval class implementing the Comparable Interface, and providing the appropriate compareTo() method
2. Create a custom Comparator Class implementing the Compare() method. 

Then, simple call sort() on the list (providing your Comparator if you chose (2)). 

One approach could be to visit every possible consecutive pair of intervals in the list and try to combine the pair if they overlap. In a list with N intervals, we have N-1 possible pairs to combine. However, after you traversed each consecutive pair, if you combined at least 1 pair during that loop, it is possible that the new interval made could also overlap with its neighbor, so you would have to continue to loop N-2 times. In the worse case, all intervals overlap with each other or and thus taking O(n2) time.

A quadratic runtime, unfortunately, is not fast enough in this case. There is a better O(n) approach. 

Runtime: O(n)




Algorithmic Approach:

Normally, without sorting the intervals by start, we would have 4 basic cases of intersection:

However, after sorting, we are left with Diagrams (2) and (4) on the right hand side. In both cases, we can apply the following algorithm:

Given interval A, B intersect, our new interval is: [A_start, Max(A_end, B_end)]

The final step would be to determine if our intervals did overlap. 

Given intervals P and D, we know that the intervals intersect if fd < kp. This condition tells us if we need to merge our intervals or not.

Java 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; }
 * }
 */
 
class IntervalComparator implements Comparator<Interval>{
    public int compare(Interval a, Interval b){
        if(a.start < b.start){
            return -1;
        }else if(a.start > b.start){
            return 1;
        }else{
            if(a.end < b.end){
                return -1;
            }else if(a.end > b.end){
                return 1;
            }else{
                return 0;
            }
        }
    }
     
 }
 
public class Solution {
    
    public List<Interval> merge(List<Interval> intervals) {
        
        List<Interval> list = new ArrayList<Interval>();
        
        if(intervals.size() == 0)
            return list;
        
        Collections.sort(intervals, new IntervalComparator());
        
        list.add(intervals.get(0));
        
        for(int i = 1; i < intervals.size(); i++){
            if(intervals.get(i).start <= list.get(list.size()-1).end){
                list.get(list.size()-1).end = Math.max(intervals.get(i).end, list.get(list.size()-1).end);
            }else{
                list.add(intervals.get(i));
            }
        }
        return list;
    }
}