Table of Contents

Leetcode 2089. Find Target Indices After Sorting Array

##### 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*. The returned list must be sorted in

**empty**list**increasing**order.

**Example 1:**

Input:nums = [1,2,5,2,3], target = 2Output:[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 = 3Output:[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 = 5Output:[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`

Source: Leetcode 2089. Find Target Indices After Sorting Array

##### Solution

In a simplest way, we can sort the array and check each element one by one. If an element = target is found, we can collect the index of that element in an array and finally return that array. This is pretty straight forward with **O(nlogn)** complexity (sorting will take nlogn time).

But there is another approach which will take only **O(n)** complexity.

In this approach, we do not need to sort the array.

Let’s take a variable **index = 0**. Then start from the beginning of that array and check if an **element < target** or not. Now, think about it. Let’s imagine we have the array in sorted form. If an element is smaller than target, that element’s index should also be smaller than target’s index, right? In other words, **target’s index is greater than an element that’s value < target**. If there is one element smaller than target, target’s index will be +1 from the beginning, right? For two elements smaller than target, target’s index will be +2 from the beginning.

With this idea in mind, we can loop through the array (without sorting) and count number of elements smaller than target. If we find 4 elements smaller than target, that means index 0, 1, 2 and 3 are occupied by those 4 elements and our target is in index 4. That way we can find the index of target without sorting.

How about if we have target multiple times in the array? For that, we can count the frequency of target and assign index = 4 for the first target, index = 4 + 1 for the second target and so on until we do this for all frequency.

Below is the code for your understanding.

###### C++ Code

class Solution { public: vector<int> targetIndices(vector<int>& nums, int target) { vector<int> ans; int index = 0; int frequency = 0; for(int i = 0; i < nums.size(); i++){ if(nums[i] < target) index++; else if(nums[i] == target) frequency++; } while(frequency > 0){ ans.push_back(index); frequency--; index++; } return ans; } };

##### Conclusion

If you are confused with the solution, please let us know in the comment section! Happy Coding 🙂