Table of contents
 Given problem
 Using bruteforce
 Using Binary Search algorithm
 Using the characteristics of problem
 Wrapping up
Given problem
You are given a 0indexed 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 nondecreasing 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 wherenums[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 wherenums[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 wherenums[i] == 5
is 4.
Constraints:
1 <= nums.length <= 100
1 <= nums[i], target <= 100
Using bruteforce
Our steps to deal with this problem are:
 Sort the current array.

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) {
indices.add(i);
}
}
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)
.forEach(idx > indices.add(idx));
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 totarget
.lessThan
: how many elements that are less thantarget
.
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) {
indices.add(lessThan++);
}
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: