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.