Find Target Indices After Sorting Array - Video Solutions

Problem Overview: You receive an integer array nums and a value target. After sorting the array in non‑decreasing order, return all indices where target appears. The key detail: the returned indices must correspond to the positions of target in the sorted array, not the original one.

Approach 1: Sorting and Linear Search (Time: O(n log n), Space: O(1) to O(n))

The most direct solution sorts the array first, then scans it once to collect positions where the value equals target. Start by calling a standard sorting routine (such as quicksort or mergesort). After sorting, iterate through the array from index 0 to n-1. Each time you encounter nums[i] == target, push i into the result list. Sorting dominates the runtime at O(n log n), while the scan is O(n). Extra space depends on the sorting implementation—some languages use in‑place sorting with O(1) auxiliary space while others allocate O(n). This approach is easy to reason about and mirrors the problem statement directly. It relies heavily on standard sorting operations and simple iteration over an array.

Approach 2: Counting and Offset Calculation (Time: O(n), Space: O(1))

The sorted order of elements reveals an important property: all values smaller than target appear before it, and all larger values appear after it. You do not actually need to sort the array to determine where target would land. Instead, iterate through the array once and count two values: how many numbers are strictly less than target, and how many are equal to it. If less is the count of elements smaller than the target and equal is the number of occurrences of the target, then in the sorted array the target will occupy indices from less to less + equal - 1. Generate that range directly. This removes sorting entirely, giving linear time O(n) and constant space O(1). The idea is similar to the counting phase of counting sort, where relative order is determined by frequency counts instead of comparisons.

Even though the problem is tagged with binary search, binary search becomes useful only if the array is already sorted. Here, the counting insight eliminates both sorting and searching.

Recommended for interviews: Start with the sorting approach to demonstrate that you correctly interpret the problem and can implement the straightforward solution. Then point out that sorting is unnecessary. The counting method shows stronger algorithmic thinking because it derives the final indices mathematically in O(n) time and O(1) space.