352. Data Stream as Disjoint Intervals

Given a data stream input of non-negative integers a1, a2, ..., an, ..., summarize the numbers seen so far as a list of disjoint intervals.

For example, suppose the integers from the data stream are 1, 3, 7, 2, 6, ..., then the summary will be:

[1, 1]
[1, 1], [3, 3]
[1, 1], [3, 3], [7, 7]
[1, 3], [7, 7]
[1, 3], [6, 7]

Follow up:
What if there are lots of merges and the number of disjoint intervals are small compared to the data stream's size?

Solution:

Use TreeMap to maintain a sorted map, when we return the list, we can simply iterate the treemap to give us the sorted intervals.

I use two maps to track interval start and interval ends respectively, my solution is very easy to understand.

Skip any value has been processed.

Merge intervals if the start map contains val+1 or end map contains val-1. Remove excessive start and end in both maps.

 class SummaryRanges {  
   TreeMap<Integer,Integer> startToEnd;  
   HashMap<Integer,Integer> endToStart;  
   HashSet<Integer> processed;  
   /** Initialize your data structure here. */  
   public SummaryRanges() {  
     startToEnd=new TreeMap<Integer,Integer>();  
     endToStart=new HashMap<Integer,Integer>();  
     processed=new HashSet<Integer>();  
   }  
   public void addNum(int val) {  
     if(!processed.add(val)) return;  
     int newStart=val;  
     int newEnd=val;  
     if(startToEnd.containsKey(val+1)){  
       newEnd=startToEnd.get(val+1);  
       startToEnd.remove(val+1);  
     }  
     if(endToStart.containsKey(val-1)){  
       newStart=endToStart.get(val-1);  
       endToStart.remove(val-1);  
     }  
     startToEnd.put(newStart,newEnd);  
     endToStart.put(newEnd,newStart);  
   }  
   public List<Interval> getIntervals() {  
     List<Interval> res=new ArrayList<Interval>();  
     for(Map.Entry<Integer,Integer> pairs : startToEnd.entrySet()){  
       Interval item=new Interval(pairs.getKey(),pairs.getValue());  
       res.add(item);  
     }  
     return res;  
   }  
 }  

347. Top K Frequent Elements

Given a non-empty array of integers, return the k most frequent elements.

For example,
Given [1,1,1,2,2,3] and k = 2, return [1,2].

Note: 

• You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
• Your algorithm's time complexity must be better than O(n log n), where n is the array's size.

Solution:

HashMap and bucket sort

Use a hashmap to track frequencies of all elements. Because the maximum possible frequencies will be the number of elements, we can use bucket to get all elements that occur certain times. Either an array or a list can present the bucket. 

Finally, we retrieve the top K elements from the top of the bucket.

Time complexity: O(n)

 public List<Integer> topKFrequent(int[] nums, int k) {  
     List<Integer> res=new ArrayList<Integer>();  
     Map<Integer,Integer> map=new HashMap<Integer,Integer>();  
     for(int i=0;i<nums.length;i++){  
       map.put(nums[i],map.getOrDefault(nums[i],0)+1);  
     }  
     List<List<Integer>> frequencies=new ArrayList<List<Integer>>();  
     for(int i=0;i<nums.length;i++) frequencies.add(new ArrayList<Integer>());  
     for(Map.Entry<Integer,Integer> pair : map.entrySet()){  
       frequencies.get(pair.getValue()-1).add(pair.getKey());  
     }  
     for(int i=nums.length-1;i>=0;i--){  
       for(int j:frequencies.get(i)) res.add(j);  
       if(res.size()==k) return res;  
     }  
     return res;  
   }