You are given a 0-indexed integer array nums and a target element target.
A target index is an index i such that nums[i] == target.
Return a list of the target indices of nums after sorting nums in non-decreasing order. If there are no target indices, return an empty list. The returned list must be sorted in increasing order.
Example 1:
Input: nums = [1,2,5,2,3], target = 2 Output: [1,2] Explanation: After sorting, nums is [1,2,2,3,5]. The indices where nums[i] == 2 are 1 and 2.
Example 2:
Input: nums = [1,2,5,2,3], target = 3 Output: [3] Explanation: After sorting, nums is [1,2,2,3,5]. The index where nums[i] == 3 is 3.
Example 3:
Input: nums = [1,2,5,2,3], target = 5 Output: [4] Explanation: After sorting, nums is [1,2,2,3,5]. The index where nums[i] == 5 is 4.
Constraints:
1 <= nums.length <= 1001 <= nums[i], target <= 100Problem 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.
This approach involves first sorting the array, then performing a linear search to find all indices of the target element. Since we are sorting the array, the resulting indices will naturally be in increasing order, as required.
This C solution uses the qsort function from the C standard library to sort the array. After sorting, it traverses the sorted array linearly to collect indices where the target value occurs. The results are stored in an array and printed.
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) ignoring result array storage, as sorting is done in place.
This approach utilizes counting sort to efficiently count occurrences of each number up to the target value, allowing determination of the starting index of the target in the sorted array without fully sorting it. This approach leverages the constraint of numbers being less than 101 for optimal performance.
In C, this solution utilizes a counting array to tally occurrences of each number so that it calculates the start index of the target in a potential sorted order directly.
Time Complexity: O(n + m), where n is the number of elements, and m is the range (here 101).
Space Complexity: O(m) due to the counting array.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Approach 1: Sorting and Linear Search | Time Complexity: O(n log n) due to sorting. |
| Approach 2: Counting Sort and Offset Calculation | Time Complexity: O(n + m), where n is the number of elements, and m is the range (here 101). |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting and Linear Search | O(n log n) | O(1) to O(n) | Simple and direct solution when sorting is acceptable or already required elsewhere. |
| Counting and Offset Calculation | O(n) | O(1) | Best choice when you want optimal performance without sorting the array. |
LeetCode 2089 | Find Target Indices After Sorting Array | Day 31 | 100 Days LeetCode Challenge | DSA • edSlash • 4,498 views views
Watch 9 more video solutions →Practice Find Target Indices After Sorting Array with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor