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 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.
I’d must verify with you here. Which isn’t one thing I normally do! I take pleasure in studying a post that can make people think. Additionally, thanks for permitting me to remark!
I really like your writing style, fantastic information, regards for putting up : D.
To the foolishhungry.com administrator, You always provide great resources and references.
To the foolishhungry.com owner, Keep it up!
Wonderful blog! I found it while surfing around on Yahoo News. Do you have any tips on how to get listed in Yahoo News? I’ve been trying for a while but I never seem to get there! Cheers
I reckon something really interesting about your web site so I saved to favorites.
To the foolishhungry.com admin, Your posts are always well-balanced and objective.
Hi foolishhungry.com webmaster, Thanks for the educational content!
Hi foolishhungry.com owner, You always provide useful information.
As I web site possessor I believe the content material here is rattling great , appreciate it for your efforts. You should keep it up forever! Best of luck.
Some genuinely interesting points you have written.Assisted me a lot, just what I was looking for : D.
Hi foolishhungry.com webmaster, Thanks for the well-researched and well-written post!
Good write-up, I’m regular visitor of one’s blog, maintain up the excellent operate, and It is going to be a regular visitor for a long time.
Hello foolishhungry.com administrator, Your posts are always well written and informative.
naturally like your web-site however you have to test the spelling on quite a few of your posts. Several of them are rife with spelling problems and I find it very troublesome to inform the reality however I’ll surely come again again.
Dear foolishhungry.com webmaster, Thanks for the informative post!
Hi i think that i saw you visited my web site thus i came to Return the favore I am attempting to find things to improve my web siteI suppose its ok to use some of your ideas
Wonderful web site Lots of useful info here Im sending it to a few friends ans additionally sharing in delicious And obviously thanks to your effort
Dear foolishhungry.com administrator, Your posts are always well written and informative.
Can you be more specific about the content of your article? After reading it, I still have some doubts. Hope you can help me. https://www.binance.com/ru-UA/join?ref=DB40ITMB
Thank you for your sharing. I am worried that I lack creative ideas. It is your article that makes me full of hope. Thank you. But, I have a question, can you help me? https://www.binance.com/vi/join?ref=IJFGOAID
Hello foolishhungry.com administrator, Good job!
Thanks for sharing. I read many of your blog posts, cool, your blog is very good. https://www.binance.com/vi/join?ref=PORL8W0Z
I don’t think the title of your article matches the content lol. Just kidding, mainly because I had some doubts after reading the article.
What a fantastic resource! The articles are meticulously crafted, offering a perfect balance of depth and accessibility. I always walk away having gained new understanding. My sincere appreciation to the team behind this outstanding website.
Wow, awesome weblog layout! How long have you ever been blogging for?
you make running a blog glance easy. The total look of your website is
wonderful, let alone the content! You can see similar here najlepszy sklep
Your article helped me a lot, is there any more related content? Thanks!
Thanks for sharing. I read many of your blog posts, cool, your blog is very good.