LeetCode 2089: Find Target Indices After Sorting Array

link

Sort around pivot = target and along the way discover the range containing target.

Time: \mathcal{O}(n), space: \mathcal{O}(\texttt{output-size}).

class Solution:
    def sort_around_pivot(self, nums, pivot) -> Tuple[int, int]:
        i, j, k = -1, 0, len(nums)
        while j < k:
            if nums[j] == pivot:
                j += 1
                continue

            if nums[j] < pivot:
                i += 1
                nums[i], nums[j] = nums[j], nums[i]
                j += 1
            else:
                k -= 1
                nums[j], nums[k] = nums[k], nums[j]

        return i+1, k

    def targetIndices(self, nums: List[int], target: int) -> List[int]:
        begin, end = self.sort_around_pivot(nums, target)
        return list( range(begin, end) )

Leave a comment