# Find Target Indices After Sorting Array
**Difficulty:** EASY
[External](https://leetcode.com/problems/find-target-indices-after-sorting-array)
Canonical: https://scaleengineer.com/dsa/problems/find-target-indices-after-sorting-array
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search), [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
**Companies:** [TikTok](https://scaleengineer.com/companies/tiktok)
---
## Problem
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 <= 100`
* `1 <= nums[i], target <= 100`

# Approaches
## Brute Force: Sort and Scan
This approach directly follows the problem statement. First, we sort the input array `nums` in non-decreasing order. Then, we iterate through the sorted array to find all indices where the element is equal to the `target` and add these indices to a result list.
**Time:** O(N log N), where N is the number of elements in `nums`. The dominant operation is sorting the array. The subsequent linear scan takes O(N) time, which is overshadowed by the sorting time. · **Space:** O(K) or O(N) in the worst case. The space required for the output list is O(K), where K is the number of occurrences of the target. In the worst case, all elements could be the target, making it O(N). Additionally, the sorting algorithm might use O(log N) to O(N) space, depending on the implementation.
**Pros:** Simple and straightforward to understand and implement.; Directly translates the problem description into code.
**Cons:** Not the most efficient solution due to the O(N log N) time complexity of sorting.
### Explanation
The algorithm consists of two main steps:

1.  **Sorting:** We use a standard library function, like `Arrays.sort()` in Java, to sort the input array `nums`. This operation has a time complexity of O(N log N), where N is the number of elements in the array.

2.  **Scanning:** After sorting, we perform a linear scan through the array from index 0 to N-1. During the scan, we check if the element at the current index `i` is equal to the `target`. If `nums[i] == target`, we add the index `i` to our result list. Since we are iterating in increasing order of indices, the resulting list of indices will also be sorted.

```java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public List<Integer> targetIndices(int[] nums, int target) {
        // Step 1: Sort the array
        Arrays.sort(nums);
        
        List<Integer> result = new ArrayList<>();
        
        // Step 2: Scan the sorted array to find target indices
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target) {
                result.add(i);
            }
        }
        
        return result;
    }
}
```
### Algorithm
- Create an empty list, `result`, to store the target indices.
- Sort the input array `nums` in non-decreasing order.
- Iterate through the sorted `nums` array with an index `i` from 0 to `nums.length - 1`.
- Inside the loop, if `nums[i]` is equal to `target`, add the index `i` to the `result` list.
- After the loop finishes, return the `result` list.

## Single Pass Counting
A more efficient approach is to avoid the O(N log N) sorting step. We can determine the final indices of the target elements by counting two things in a single pass: the number of elements smaller than the target and the number of elements equal to the target. The first target index will be the count of smaller elements, and the subsequent indices will follow consecutively.
**Time:** O(N), where N is the number of elements in `nums`. We perform a single pass through the array to count the elements, and another loop to build the result list which runs `K` times (where K is the count of the target). In the worst case, K=N, but the total time is still proportional to N. · **Space:** O(K), where K is the number of occurrences of the target. This space is used for the output list. In the worst case, K=N, making the space complexity O(N).
**Pros:** More efficient with a linear time complexity.; Avoids the overhead of a full sort operation.
**Cons:** Slightly less intuitive than the direct sorting approach, as it requires an insight about the position of elements in a sorted array.
### Explanation
This method leverages a key insight: after sorting, all occurrences of the `target` will form a contiguous block. The starting index of this block is determined by the number of elements that are strictly smaller than the `target`.

The algorithm is as follows:

1.  Initialize two counters: `lessThanCount = 0` and `targetCount = 0`.
2.  Iterate through the original `nums` array once. For each element `num`:
    *   If `num < target`, increment `lessThanCount`.
    *   If `num == target`, increment `targetCount`.
3.  After the pass, `lessThanCount` gives us the starting index for the target values in the sorted array.
4.  Create an empty result list.
5.  Add the indices to the result list by running a loop `targetCount` times. In each iteration, add `lessThanCount + i` (where `i` is the loop variable from 0 to `targetCount - 1`) to the list.

This way, we construct the final sorted list of indices without ever actually sorting the array.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<Integer> targetIndices(int[] nums, int target) {
        int lessThanCount = 0;
        int targetCount = 0;
        
        // Step 1: Count elements smaller than and equal to target
        for (int num : nums) {
            if (num < target) {
                lessThanCount++;
            } else if (num == target) {
                targetCount++;
            }
        }
        
        List<Integer> result = new ArrayList<>();
        
        // Step 2: Construct the result list based on counts
        // The first index of target will be at lessThanCount
        for (int i = 0; i < targetCount; i++) {
            result.add(lessThanCount + i);
        }
        
        return result;
    }
}
```
### Algorithm
- Initialize two integer variables: `lessThanCount = 0` and `targetCount = 0`.
- Iterate through the input array `nums` once.
- For each element `num` in `nums`:
  - If `num < target`, increment `lessThanCount`.
  - If `num == target`, increment `targetCount`.
- Create an empty list, `result`.
- Run a loop from `i = 0` to `targetCount - 1`.
- In each iteration, add the index `lessThanCount + i` to the `result` list.
- Return the `result` list.

# Solutions
### Java

```java
class Solution {
public
  List<Integer> targetIndices(int[] nums, int target) {
    Arrays.sort(nums);
    List<Integer> ans = new ArrayList<>();
    for (int i = 0; i < nums.length; ++i) {
      if (nums[i] == target) {
        ans.add(i);
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> targetIndices(vector<int> &nums, int target) {
    sort(nums.begin(), nums.end());
    vector<int> ans;
    for (int i = 0; i < nums.size(); ++i) {
      if (nums[i] == target) {
        ans.push_back(i);
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def targetIndices(self, nums: List[int], target: int) -> List[int]: nums . sort() return [i for i, v in enumerate(nums) if v == target]

```