Leetcode: Why this algorithm is slow?

Question

So I am trying to solve this problem: http://oj.leetcode.com/problems/merge-intervals/

My solution is:

public class Solution {

public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
    // Start typing your Java solution below
    // DO NOT write main() function
    // ArrayList<Interval> result = new ArrayList<Interval>();

    //First sort the intervals
    Collections.sort(intervals,new Comparator<Interval>(){
        public int compare(Interval interval1, Interval interval2) {
            if(interval1.start >  interval2.start) return 1;
            if(interval1.start == interval2.start) return 0;
            if(interval1.start <  interval2.start) return -1;
            return 42;
        }
    });

    for(int i = 0; i < intervals.size() - 1; i++){
        Interval currentInterval = intervals.get(i);
        Interval nextInterval = intervals.get(i+1);
        if(currentInterval.end >= nextInterval.start){
            intervals.set(i,new Interval(currentInterval.start,nextInterval.end));
            intervals.remove(i+1);
            i--;
        }
    }

    return intervals;   
}
}

I have seen some blogs using exactly the same solution but get accepted but mine is rejected because it takes too long. Can you enlighten me why it takes longer than expected? Cheers

EDIT: solved, remove is too costly, using a new arraylist to store the result is faster

This question appears to be off-topic because it is about is about [codereview](http://codereview.stackexchange.com/). — Sirko, Sep 18 '13 at 14:26
Removing from the head->middle of an arraylist is quite costly, because the underlying array must be copied at every call. But a @SpongeBobFan told, you should verify this with a profiler. — Thomas Jungblut, Sep 18 '13 at 14:27
I have not used a java profiler before, okay I will try that, thanks — Bob Fang, Sep 18 '13 at 14:30
@Sirko I think this question is fine here, since it's trying to address a problem with the code - namely, the execution time. — Adam Lear, Sep 18 '13 at 14:30
@AnnaLear From codereview's help: "What topics can I ask about here? - If you are looking for feedback on [...] Performance [...], then you are in the right place!". — Sirko, Sep 18 '13 at 14:35
@sirko Just because you can ask about something elsewhere doesn't make it off-topic here. — dcaswell, Oct 22 '13 at 06:02

score 2 · Accepted Answer · edited May 23 '17 at 12:11

2

Initially you are sorting all your intervals - due to javadocs, this operation has complexity O(N*log(N))

But, after that, as I have noticed - you are iterating over ArrayList, and sometimes removing elements from it.

But removing some element from ArrayList has complexity O(N) (as underlying implementation of ArrayList is plain array - removing any elemnt from the middle of array, requires shifting of the entire right part of this array).

As you do that in loop - finally, complexity of your algirithm would be O(N^2).

I'd suggest you to use LinkedList instead of ArrayList in this case.

edited May 23 '17 at 12:11

Community

1
1

answered Sep 18 '13 at 14:33

stemm

5,960
2
34
64

2

Or maybe even smarter: Instead of just checking the following item, he can check as long as he finds a mergable element and then put the resulting merged interval into a new list. That's I guess where the `//ArrayList result = new ArrayList();` comes from. – Thomas Jungblut Sep 18 '13 at 14:35
2

Solved using what @ThomasJungblut has suggested, store it in a new ArrayList, thanks all :) – Bob Fang Sep 18 '13 at 14:41

score 1 · Answer 2 · answered Sep 18 '13 at 14:28

1

You could improve your sorting by using one computation instead of 3 comparisons:

Collections.sort(intervals,new Comparator<Interval>(){
    public int compare(Interval interval1, Interval interval2) {
        return interval1.start - interval2.start;
    }
});

answered Sep 18 '13 at 14:28

Sirko

72,589
19
149
183

Improve in which way? – Boris Treukhov Sep 18 '13 at 14:30
@BorisTreukhov Less operations. Internally each comparison will likely be at least one computation like the one I used. So reducing the number of operations here, should improve run time overall. – Sirko Sep 18 '13 at 14:31
2

TimSort worst case is n*logn, obviously the problem is with removing from the middle of the array – Boris Treukhov Sep 18 '13 at 14:32

Leetcode: Why this algorithm is slow?

2 Answers2