Simple Python O(log N) Solution

        # @param A : tuple of integers
        # @param B : integer
        # @return a list of integers
        def searchRange(self, A, B):
            lo = 0
            hi = len(A) - 1
            starting = -1
            ending = -1
            # search left even if found the indices
            while lo <= hi:
                mid = (lo+hi)//2
                if A[mid] == B:
                    starting = mid
                    hi = mid - 1
                elif A[mid] > B:
                    hi = mid - 1
                else:
                    lo = mid + 1
            lo = 0
            hi = len(A) - 1
            # search right even if found the indices
            while lo <= hi:
                mid = (lo+hi)//2
                if A[mid] == B:
                    ending = mid
                    lo = mid + 1
                elif A[mid] > B:
                    hi = mid - 1
                else:
                    lo = mid + 1
            
            return [starting, ending]

Simply run binary search twice. For the first search, keep searching left side even when the index is found. Second search, keep searching right.

Other approaches posted here that finds one index using simple binary search and walks left and right is O(n) not O(log N) worst case. Think about a case like [2,2,2,2,2,2,2,2,2,2,2].

You can also use Python’s bisect module

    def searchRange(self, A, B):
        starting = bisect.bisect_left(A, B, 0, len(A)-1)
        ending = bisect.bisect_right(A, B, 0, len(A)-1)
        return [starting, ending]

Sure you can use library functions, but the interviewer would reject you if you cannot code it on spot. And by the way, you need to return [starting, ending-1]. Also, check the corner cases when the element is not present.

i coincidently did the same python code, man. But it runs for test cases and not after submitting. There must be some issue in their test cases i guess

Click here to start solving coding interview questions