You are given an array of integers and another target integer as input. Your task is to return the index or indices of the target integer in the array as if it were sorted, while adhering to a time constraint of O(n).
Example:
Input: [5, 6, 1, 2, 4], Target: 2
Output: [1]
Explanation: In the sorted version of the array [1, 2, 4, 5, 6], the target 2 appears at index 1.Modify your solution to instead find the element or elements that appear most frequently in the array. Return the index or indices of these most frequent elements as if the array were sorted.
Example:
Input: [5, 6, 1, 2, 2, 4]
Output: [1, 2]
Explanation: Since 2 is the most frequent element and appears at indices 1 and 2 in the sorted array [1, 2, 2, 4, 5, 6].Now, you need to return a new array of the same length where the elements are the indices of the original elements in a sorted version of the array.
Example:
Input: [5, 6, 1, 2, 4]
Output: [3, 4, 0, 1, 2]
Explanation: In the sorted array [1, 2, 4, 5, 6], 5, which is the first element of the original array, appears at index 3 in the sorted array, 6 at 4, 1 at 0, 2 at 1, and 4 at 2.This problem is about mapping values to their positions in a sorted order without fully sorting the array when an O(n) solution is required. The first version asks for the index of a target value in the sorted array; the second asks for the indices of the most frequent value(s); and the third asks for the sorted-order index of every original element. A typical approach uses frequency counting plus rank/prefix information, often with a hash map or counting array depending on the value range.
