Find Target Indices After Sorting Array

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 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

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 🙂

Bonus – System Design!

ByteByteGo is by far the best system design resource found on the internet. They are growing like crazy!

We suggest you checkout their course if you really want to dive deep in system design and want to have a killer interview!

Here is the link: ByteByteGo!

Disclaimer: this is a genuine suggestion, but we have some interest too! We get commission if you buy their course. However, there are other courses online which we do not promote. Because we promote only things that are the best in our opinion and those we really feel will be helpful for you.