Java O(nlogn) time and O(1) space using Iterator to do in-place merge

  • 0

    Using Iterator to do in-place merge by re-using the input list to achieve O(1) space.
    However, in the real world, one should be aware that the input list could be an UnmodifiableList that fail this in-place merge. Modifiability check would be needed to choose between the O(1) (in-place) and O(n) (new list) space implementations.

    public List<Interval> merge(List<Interval> intervals) {
        if (intervals == null || intervals.size() <=1) {
            return intervals;
        intervals.sort((v1, v2) ->, v2.start));
        Interval merged = intervals.get(0);
        Iterator<Interval> iterator = intervals.iterator();;
        while (iterator.hasNext()) {
            Interval v =;
            if (v.start >= merged.start && v.start <= merged.end) {
                merged.end = Math.max(merged.end, v.end);
            } else {
                merged = v;
        return intervals;

Log in to reply

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