Problem statement

Sort nums in non-decreasing order. A target index is an index i of the sorted array with nums[i] == target.

Return all target indices in increasing order, or an empty array if target does not occur.

Example 1

Input: nums = [6,3,6,1], target = 6
Output: [2,3]
Explanation: Sorted: [1,3,6,6]; the 6s sit at indices 2 and 3.

Example 2

Input: nums = [5,9,2], target = 4
Output: []

Example 3

Input: nums = [7,7,7], target = 7
Output: [0,1,2]

Constraints

• 1 <= nums.length <= 100
• 1 <= nums[i], target <= 100

Hints for Find Target Indices After Sorting Array

1. Hint 1

   After sorting, all copies of target form one contiguous block.

2. Hint 2

   Where does that block start? Exactly after every element smaller than target.

3. Hint 3

   Count less (elements below target) and equal (copies of target); the answer is less, less + 1, ..., less + equal - 1 — no sort needed.

How to solve Find Target Indices After Sorting Array

In the sorted array the copies of target occupy a single block that begins right after all smaller elements, so two counts determine the answer without sorting.

Approach

1. Count less, the elements smaller than target, and equal, the elements equal to it.
2. Return the indices less through less + equal - 1.

Why it works

Sorting places every element smaller than target before every copy of target, and every larger element after them. So the copies of target fill positions less to less + equal - 1 exactly, regardless of the original order.

Complexity

• Time — O(n)
• Space — O(1) besides the output

Pitfalls

• Return indices of the sorted array, not of the original array.
• When equal == 0, return an empty array.
• Sorting and scanning also works (O(n log n)) — just do not sort the caller's array in place where it matters.

Reference solution

Python

from typing import List

def targetIndices(nums: List[int], target: int) -> List[int]:
    less = sum(1 for x in nums if x < target)
    equal = nums.count(target)
    return list(range(less, less + equal))

Java

public static int[] targetIndices(int[] nums, int target) {
    int less = 0, equal = 0;
    for (int v : nums) {
        if (v < target) less++;
        else if (v == target) equal++;
    }
    int[] out = new int[equal];
    for (int k = 0; k < equal; k++) out[k] = less + k;
    return out;
}

C++

vector<int> targetIndices(vector<int>& nums, int target) {
    int less = 0, equal = 0;
    for (int v : nums) {
        if (v < target) less++;
        else if (v == target) equal++;
    }
    vector<int> out;
    for (int k = 0; k < equal; k++) out.push_back(less + k);
    return out;
}

JavaScript

var targetIndices = function(nums, target) {
    var less = 0, equal = 0;
    for (var i = 0; i < nums.length; i++) {
        if (nums[i] < target) less++;
        else if (nums[i] === target) equal++;
    }
    var out = [];
    for (var k = 0; k < equal; k++) out.push(less + k);
    return out;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Brightest String of Diyas Easy
• Design Neighbor Sum Service Easy
• Design an Ordered Stream Easy
• Design HashMap Easy
• Design HashSet Easy
• Range Sum Query - Immutable Easy