Back from the dead

Week: 20th Oct - 26th Oct ‘26#

2089. Find Target Indices After Sorting Array#

Easiest solution thought immediately. Sort initial nums then generate output then sort output.

class Solution {
public:
    vector<int> targetIndices(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        vector<int> output;
        for (int i=0; i<nums.size(); i++){
            if (nums[i]==target) output.push_back(i);
        }
        sort(output.begin(), output.end());
        return output;
    }
};

Time complexity: n.logn + n + n.logn = O(n.logn) Space: O(1) auxilliary

Improvement? Thought for a few seconds then realized I can build the output. Count how many numbers lesser than target, count how many targets there are. Start building the output using them.

class Solution {
public:
    vector<int> targetIndices(vector<int>& nums, int target) {
        int less_than_target = 0;
        int target_freq = 0;
        for (int i =0; i< nums.size(); i++){
            if (nums[i] < target) less_than_target++;
            if (nums[i] == target) target_freq++;
        }
        vector<int> output;
        for (int i=0; i < target_freq; i++){
            output.push_back(less_than_target+i);
        }
        return output;
    }
};

Time complexity: O(n), Space Complexity: O(1) auxiliary