This is our solution and implementation to problem #2089: Find Target Indices After Sorting Array on LeetCode.
Our code is written in Java. If you want to code your solution in a different language, no worries, as the core concepts will carry over from language to language. This page includes our analysis of the problem, our implementation strategy a breakdown on the space and time complexity, and the full code implementation.
If you would like to view the original problem and solve it, please visit: Find Target Indices After Sorting Array on LeetCode.
Problem Analysis
The problem asks us to sort the input list, then return the indices of all elements from that sorted list which are equal to the target. This could be done simply by using a built-in sorting algorithm to sort the input, then iterate over it once. Alternatively, you could hand-write a sorting algorithmn. However, you can find the list of indices without actually sorting the list at all.
Implementation Strategy
Iterate over the input list and count the number of elements that are lower or higher than the target in two separate variables. Once you have the counts, you know that the first occurrence of the target must be the same as the number of smaller elements. The number of occurrences of the target is equal to the input length minus the number of occurences of lesser and greater elements, so you can calculate the total number of target inputs from that. Then, iterate and create a list of elements with the corresponding indices.
Space and Time Complexity
The time complexity is O(n) as this iterates through the input list once and iterates at most n times again to create the output list. The space complexit is O(n) as this uses a constant number of variables for calculation, but then must have a list of up to n elements to return the requested output of the function.
Full Code
Our solution is given in the Java code below:
All of our solutions are hosted on GitHub. The code on this page was pulled from the repo.