Is this algorithm O(n) or O(n^2)? Accepted Python Simple Solution


  • 0
    L

    Do we have to use binary search? I think the time complexity of following accepted solution is O(n). But please rectify me if I am wrong.

    class Solution:
        # @param {integer[]} nums
        # @param {integer} target
        # @return {integer[]}
        def searchRange(self, nums, target):
            start = -1
            length = 0
            for i in range(len(nums)):
                if nums[i] == target:
                    start = i
                    break
            for i in range(len(nums) - start - 1):
                if nums[start + i + 1] == target:
                    length += 1
            res = [start, start + length]
            return res

  • 0

    Yes, this is O(n), so it violates the "Your algorithm's runtime complexity must be in the order of O(log n)" requirement.


  • 0
    L

    Thank you for replying. I did leetcode a few months ago, all I was caring about was speed. Now I am doing for the second time and I notice some of my solutions were really stupid..


Log in to reply
 

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