## Given 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: ``
• 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: ``
• 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`

## Using brute-force

Our steps to deal with this problem are:

1. Sort the current array.
2. Find elements that are equal to the `target`.

• First way, iterate all elements of the array.

In this section, we will use this way.

• Second way, using binary search algorithm to find the upper bound and lower bound of the target. Then, iterate from lower bound to upper bound to get indices.

``````class Solution {

public List<Integer> targetIndices(int[] nums, int target) {
Arrays.sort(nums);

ArrayList<Integer> indices = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
if (nums[i] == target) {
}
}

return indices;
}
}
``````

The complexity of this solution is:

• Time complexity: `O(nlogn)`.
• Space complexity: `O(n)`.

## Using Binary Search algorithm

``````class Solution {
public List<Integer> targetIndices(int[] nums, int target) {
Arrays.sort(nums);
System.out.println(Arrays.toString(nums));

List<Integer> indices = new ArrayList<>();

int lowerPoint = lowerBound(nums, target);
if (lowerPoint == -1) {
return indices;
}

int upperPoint = upperBound(nums, target);
IntStream.rangeClosed(lowerPoint, upperPoint)

return indices;
}

private static int lowerBound(int[] nums, int target) {
int left = 0;
int right = nums.length;

while (left + 1 < right) {
int mid = left + (right - left) / 2;

if (nums[mid] >= target) {
right = mid;
} else {
left = mid;
}
}

if (nums[left] == target) {
return left;
}

if (right < nums.length && nums[right] == target) {
return right;
}

return -1;
}

private static int upperBound(int[] nums, int target) {
int left = 0;
int right = nums.length;

while (left + 1 < right) {
int mid = left + (right - left) / 2;

if (nums[mid] <= target) {
left = mid;
} else {
right = mid;
}
}

if (nums[left] == target) {
return left;
}

if (right < nums.length && nums[right] == target) {
return right;
}

return -1;
}
}
``````

The complexity of this solution is:

• Time complexity: `O(nlogn)`.

• The time complexity of sorting algorithm is O(nlogn).
• The time complexity of binary search algorithm is O(logn).
• Space complexity: `O(n)`.

## Using the characteristics of problem

In this way, we will make the most of the characteristics of this problem. To understand it, we need to state our problem again:

``````Find the indices of elements that are equal to target after sorting.
``````

Definitely, after sorting the arrary, we only need to take care the last index of element that is less than `target`. Then, the elements’ index that are equal to the target will be increased by 1 based on that element.

``````.. idx_less_element target ..
``````

Therefore, we will use two variable to indicate them.

• `count`: how many elements that are equal to `target`.
• `lessThan`: how many elements that are less than `target`.

Below is our source code for this problem:

``````public class Solution {
public static List<Integer> targetIndicesV2(int[] nums, int target) {
List<Integer> indices = new ArrayList<>();

int count = 0;
int lessThan = 0;

for (int n : nums) {
if (n == target) {
count++;
continue;
}

if (n < target) {
lessThan++;
}
}

for (int i = 0; i < count; ++i) {
}

return indices;
}
}
``````

The complexity of this solution is:

• Time complexity: `O(n)`.
• Space complexity: `O(n)`.

## Wrapping up

• The first step is that try to simulate the problem.

Refer:

2089. Find Target Indices After Sorting Array