Sort around pivot = target and along the way discover the range containing target.
Time: , space:
.
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