C# Clean O(N) time complexity with O(N) space


  • 0
    D

    I wrote a simple algorithm for this problem. Since we are merging with a list of intervals, we know that, at a minimum, the time complexity is O(N) regardless of the language to implement it. Now the O(N) space requirement is there so that we can return a new result rather than mutate the original list, and, more importantly, to keep the algorithm at O(N) time complexity. So we gave time complexity a higher priority than the space complexity. In C#, List.Remove has a O(N) time complexity on its own so we avoided the use of that. Finally, I believe the algorithm is pretty clean and understandable but comments are welcome.


    /// <summary>
    /// Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).
    /// You may assume that the intervals were initially sorted according to their start times.
    /// </summary>
    /// <example>
    /// Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].
    /// This is because the new interval[4, 9] overlaps with[3, 5],[6,7],[8,10].
    /// </example>
    public class Solution
    {
        public IList<Interval> Insert(IList<Interval> intervals, Interval newInterval)
        {
            IList<Interval> result = new List<Interval>();
            int length = intervals.Count;
            bool merged = false;
    
            //We are going to need to loop at least once
            for (int i = 0; i < length; i++)
            {
                if (merged || newInterval.start > intervals[i].end)
                {
                    result.Add(intervals[i]);
                }
                else if(newInterval.end < intervals[i].start)
                {
                    merged = true;
                    result.Add(newInterval);
                    result.Add(intervals[i]);
                }
                else
                {
                    if(intervals[i].start < newInterval.start)
                    {
                        newInterval.start = intervals[i].start;
                    }
                    if(intervals[i].end > newInterval.end)
                    {
                        newInterval.end = intervals[i].end;
                    }
                }
            }
    
            //Satifies condition when newInterval will be last interval
            if (!merged)
            {
                result.Add(newInterval);
            }
    
            return result;
        }
    }

Log in to reply
 

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