Java: Wouldn't the in-place approach degrade to O(N^2) when input is an ArrayList ?


  • 0
    S

    The inplace approach mainly uses an iterator and calls its remove() method when an overlapping occurs. If the input list is implemented as a linked list, this is a very smart approach because remove() in linked list costs O(1). Thus removing at most N times leads to a time complexity of O(N) and space complexity of O(1). However, if the input list is actually an arraylist, then each remove() will cost O(N) due to copying array elements, in the worst case we need O(N) removes, so the overall complexity will be O(N2). Is my understanding correct?


  • 0
    A

    I think you are right. Today, I used my in-place method to solve this problem, however, I got a LTE when the super long inputs coming in. In my method, the first step is to iterate all the Intervals and marked those need be removed. The second step is removing all the marked Intervals. My method should be O(n). So the point you mentioned is the reason why I got LTE in my idea.

    public class Solution {
        public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
            int size=intervals.size();
            if(size==0) return intervals;
            
            int start=newInterval.start;
            int end=newInterval.end;
            boolean addnew=true;
            
            List<Integer> removeindexs=new ArrayList<Integer> ();
            for(int i=0;i<size;i++)
            {
                Interval temp=intervals.get(i);
                int ithstart=temp.start;
                int ithend=temp.end;
                
                if(start>=ithstart&&start<=ithend&&ithend<=end)
                {
                    removeindexs.add(i);
                    start=ithstart;
                }
                else if(end>=ithstart&&end<=ithend&&ithstart>=start)
                {
                    removeindexs.add(i);
                    end=ithend;
                }
                else if(ithstart>=start&&ithend<=end)
                {
                    removeindexs.add(i);
                }
                else if(start>=ithstart&&end<=ithend)
                {
                    addnew=false;
                    break;
                }
            }
            
            int removesize=removeindexs.size();
            for(int i=removesize-1;i>=0;i--)
            {
                intervals.remove(removeindexs.get(i));
            }
            if(addnew)
               intervals.add(new Interval(start,end));
               
            return intervals;
        }
    }

Log in to reply
 

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