Java TreeMap O(1) add and O(n) get Solution with Explanation


  • 0
    M

    The basic idea is to use two map to store intervals. One map stores the start of each interval and its length; the other map stores the end of each interval and its length. When a new value is added, check whether (val+1) or (val -1) is the start or end of one interval, if so, merge and update both maps.

    public class SummaryRanges {
    
    TreeMap<Integer, Integer> fromLeft;
    TreeMap<Integer, Integer> fromRight;
    
    /** Initialize your data structure here. */
    public SummaryRanges() {
    	fromLeft = new TreeMap<>();
    	fromRight = new TreeMap<>();
    }
    
    public void addNum(int val) {
    	if (fromRight.containsKey(val) || fromLeft.containsKey(val)) {
    		return;
    	}
    
    	int leftLen = fromLeft.getOrDefault(val + 1, 0) + 1;
    	int rightLen = fromRight.getOrDefault(val - 1, 0) + 1;
    
    	fromLeft.put(val, leftLen + rightLen - 1);
    	fromRight.put(val + leftLen - 1, leftLen + rightLen - 1);
    
    	fromRight.put(val, leftLen + rightLen - 1);
    	fromLeft.put(val - rightLen + 1, leftLen + rightLen - 1);
    }
    
    public List<Interval> getIntervals() {
    
    	List<Interval> ans = new ArrayList<>();
    	int limit = Integer.MIN_VALUE;
    	for (int key : fromLeft.keySet()) {
    		if (key > limit) {
    			limit = key + fromLeft.get(key) - 1;
    			ans.add(new Interval(key, limit));
    		}
    	}
    
    	return ans;
    }
    

    }


  • 0

    What makes you think those TreeMap operations are O(1)?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.