Python O(n) Time Complexity, O(max(interval)) Space Complexity. No Sorting - Passes All Tests.


  • 0
    S
    # class Interval(object):
    #     def __init__(self, s=0, e=0):
    #         self.start = s
    #         self.end = e
    
    class Solution(object):
        def merge(self, intervals):
            """
            :type intervals: List[Interval]
            :rtype: List[Interval]
            """
            if intervals == []:
                return []
               
            # Find max value 
            mx = -1 * float("inf")
            for i in intervals:
                 mx = max(max(i.start, i.end), mx)
    
            # Create array of that length. Array represents the whole span
            # of time which can be blocked into intervals
            res = [0] * (mx+1)
            
            
            for i in intervals:
                # If an interval is just one spot and is not part of any other 
                # interval, mark it with a 2
                if i.start == i.end:
                    if res[i.end]==0:
                        res[i.end] = 2
                else:
                     # Mark the slot an interval fills with all 1s except for the last spot
                    res[i.start:i.end] = [1] * (i.end - i.start)
                     # If the last spot is not part of an existing interval
                     # set it to -1
                    if res[i.end]!=1:
                        res[i.end] = -1
                
            result = []    
            i = 0
            # iterates over time array. Saves continuous blocks of 1s as intervals
            # Saves 2s as a single interval block on their own
            while i < len(res):
                if res[i] == 1:
                    start = i
                    while res[i] == 1:
                        i += 1
                    end = i - 1
                    result.append(Interval(start, end+1))
                elif res[i] == 2:
                    result.append(Interval(i, i))
                i += 1
            return result
    

  • 0
    L

    You are wrong.

    Take the time of space allocation into account, time complexity can be no smaller than space complexity.


  • 0
    S

    @lv.zheng.2015 Initializing a python list of a certain size takes roughly constant time:

    python -m timeit -n 1000 -s "[0]*100"
    1000 loops, best of 3: 0.01 usec per loop
    python -m timeit -n 1000 -s "[0]*1000"
    1000 loops, best of 3: 0.011 usec per loop
    python -m timeit -n 1000 -s "[0]*100000"
    1000 loops, best of 3: 0.011 usec per loop
    python -m timeit -n 1000 -s "[0]*1000000"
    1000 loops, best of 3: 0.0119 usec per loop
    

    Also, in python I believe replacing a subset of a list with another list as I am doing takes O(1), as the internal list implementation uses a doubly linked list, see Python list documentation. So it should still be O(n) time complexity.


Log in to reply
 

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