While the most direct approach is to sort the array (O(n log n)) and then iterate to find the indices, we can actually solve this in linear time (O(n)) without sorting the entire array.
The O(n) Counting Strategy:
Count smaller elements: Count how many numbers in the array are strictly less than the target. This count tells us the starting index of the target in a sorted version of the array.
Count occurrences: Count how many times the target itself appears in the array.
Generate result: Starting from the "smaller elements" count, append consecutive integers to our result list for as many times as the target occurred.
class Solution:
def targetIndices(self, nums: list[int], target: int) -> list[int]:
count_smaller = 0
count_target = 0
for num in nums:
if num < target:
count_smaller += 1
elif num == target:
count_target += 1
# The first index of target will be count_smaller.
# We generate indices starting from count_smaller for count_target times.
return [i for i in range(count_smaller, count_smaller + count_target)]