LeetCode Problem 2089

Difficulty: 🟢 Easy
Topics: Array, Binary Search, Sorting

Solution

LeetCode 2089, Find Target Indices After Sorting Array

Problem Understanding

The problem gives us an integer array nums and an integer target. We must sort the array in non-decreasing order and then return every index where the value equals target.

A target index is simply an index i such that:

$nums[i] = target$

The important detail is that the indices must be returned after sorting the array, not based on the original order.

For example, if:

nums = [1,2,5,2,3]
target = 2

After sorting:

[1,2,2,3,5]

The value 2 appears at indices 1 and 2, so the answer is:

[1,2]

The input array length is at most 100, and every value is also between 1 and 100. These constraints are very small, which means even a straightforward sorting solution is perfectly acceptable.

The output must contain all valid indices in increasing order. Since the array becomes sorted, the indices naturally appear in ascending order when scanned from left to right.

Several edge cases are important to consider:

• The target may not exist in the array at all, in which case we return an empty list.
• Every element in the array may equal the target, meaning every index becomes part of the answer.
• The target may appear only once.
• The array may already be sorted or completely unsorted, but our algorithm must behave correctly in all cases.

Approaches

Brute Force Approach

The most direct solution is:

1. Sort the array.
2. Iterate through the sorted array.
3. Collect every index where the value equals target.

This approach works because sorting places all equal values together, making it easy to identify every occurrence of the target.

Even though this solution is simple, it is already efficient enough for the problem constraints. The array size is tiny, so sorting costs very little.

Better Observation

We can improve the reasoning slightly without explicitly relying on the sorted array values themselves.

After sorting:

• Every number smaller than target will appear before the target.
• Every occurrence of target will appear consecutively.

Therefore:

• The first target index equals the count of numbers smaller than target.
• The number of target indices equals the count of numbers equal to target.

If:

smaller = count of numbers < target
equal = count of numbers == target

Then the answer becomes:

[smaller, smaller + 1, ..., smaller + equal - 1]

This avoids sorting entirely and produces the answer in linear time.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n log n)	O(1) or O(n)	Sort the array, then scan for target indices
Optimal	O(n)	O(1) excluding output	Count smaller and equal elements directly

Algorithm Walkthrough

Optimal Algorithm

1. Initialize two counters:

• smaller_count, to count numbers strictly smaller than target
• equal_count, to count numbers equal to target

2. Traverse the array once from left to right.
3. For each number:

• If the number is smaller than target, increment smaller_count.
• If the number equals target, increment equal_count.

4. After processing the array:

• The first target index in the sorted array is smaller_count.
• Since there are equal_count copies of the target, the indices will be:

smaller_count
smaller_count + 1
...
smaller_count + equal_count - 1

1. Build the result list using this range of indices.
2. Return the result list.

Why it works

Sorting places all values smaller than target before every occurrence of target. Therefore, the number of elements smaller than target directly determines the first target position.

Since all equal values become consecutive after sorting, the target occupies exactly equal_count positions starting from smaller_count. This guarantees that the constructed index list exactly matches the indices of target in the sorted array.

Python Solution

from typing import List

class Solution:
    def targetIndices(self, nums: List[int], target: int) -> List[int]:
        smaller_count = 0
        equal_count = 0

        for num in nums:
            if num < target:
                smaller_count += 1
            elif num == target:
                equal_count += 1

        return list(range(smaller_count, smaller_count + equal_count))

The implementation begins by initializing two counters. The first counter tracks how many numbers are strictly smaller than the target, while the second counter tracks how many numbers equal the target.

The loop processes each number exactly once. Using an elif ensures that a number equal to the target is not also counted as smaller.

After the traversal finishes, we know exactly where the target block starts in the sorted array and how long it is. The range call generates every valid target index, and converting it to a list produces the required return type.

If the target does not exist, equal_count becomes 0, and the range is empty, correctly returning an empty list.

Go Solution

func targetIndices(nums []int, target int) []int {
	smallerCount := 0
	equalCount := 0

	for _, num := range nums {
		if num < target {
			smallerCount++
		} else if num == target {
			equalCount++
		}
	}

	result := make([]int, 0, equalCount)

	for i := 0; i < equalCount; i++ {
		result = append(result, smallerCount+i)
	}

	return result
}

The Go solution follows the exact same logic as the Python version. Since Go does not have a built-in range-to-list conversion like Python, we explicitly create a slice and append each index manually.

The result slice is initialized with capacity equalCount, which avoids unnecessary reallocations during appends.

If the target does not appear in the array, equalCount becomes 0, and the function correctly returns an empty slice.

Worked Examples

Example 1

nums = [1,2,5,2,3]
target = 2

Step-by-step traversal

Current Number	smaller_count	equal_count	Explanation
1	1	0	1 is smaller than 2
2	1	1	Found target
5	1	1	Ignore
2	1	2	Found another target
3	1	2	Ignore

Now:

smaller_count = 1
equal_count = 2

The target indices are:

[1, 2]

Example 2

nums = [1,2,5,2,3]
target = 3

Current Number	smaller_count	equal_count
1	1	0
2	2	0
5	2	0
2	3	0
3	3	1

Now:

smaller_count = 3
equal_count = 1

Result:

[3]

Example 3

nums = [1,2,5,2,3]
target = 5

Current Number	smaller_count	equal_count
1	1	0
2	2	0
5	2	1
2	3	1
3	4	1

Now:

smaller_count = 4
equal_count = 1

Result:

[4]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	We traverse the array once
Space	O(1) excluding output	Only two counters are used

The algorithm performs a single pass through the input array, so the running time grows linearly with the array size.

The auxiliary memory usage is constant because only two integer counters are maintained. The returned result list is not counted toward auxiliary space complexity.

Test Cases

from typing import List

class Solution:
    def targetIndices(self, nums: List[int], target: int) -> List[int]:
        smaller_count = 0
        equal_count = 0

        for num in nums:
            if num < target:
                smaller_count += 1
            elif num == target:
                equal_count += 1

        return list(range(smaller_count, smaller_count + equal_count))

sol = Solution()

assert sol.targetIndices([1, 2, 5, 2, 3], 2) == [1, 2]  # example 1
assert sol.targetIndices([1, 2, 5, 2, 3], 3) == [3]  # example 2
assert sol.targetIndices([1, 2, 5, 2, 3], 5) == [4]  # example 3

assert sol.targetIndices([1], 1) == [0]  # single element equal to target
assert sol.targetIndices([1], 2) == []  # single element not equal to target

assert sol.targetIndices([2, 2, 2], 2) == [0, 1, 2]  # all elements are target
assert sol.targetIndices([5, 4, 3, 2, 1], 6) == []  # target does not exist

assert sol.targetIndices([4, 4, 4, 1, 2], 4) == [2, 3, 4]  # duplicates after sorting
assert sol.targetIndices([10, 9, 8, 7], 7) == [0]  # target becomes first element
assert sol.targetIndices([1, 2, 3, 4], 4) == [3]  # target becomes last element

assert sol.targetIndices([3, 1, 3, 2, 3], 3) == [2, 3, 4]  # multiple targets

Test Summary

Test	Why
[1,2,5,2,3], target=2	Standard duplicate target case
[1,2,5,2,3], target=3	Single target occurrence
[1,2,5,2,3], target=5	Target at end after sorting
[1], target=1	Smallest valid input
[1], target=2	Target absent
[2,2,2], target=2	Every element equals target
[5,4,3,2,1], target=6	Target larger than all elements
[4,4,4,1,2], target=4	Multiple duplicates after sorting
[10,9,8,7], target=7	Target becomes first index
[1,2,3,4], target=4	Target becomes last index
[3,1,3,2,3], target=3	Multiple scattered target values

Edge Cases

Target Does Not Exist

A common source of bugs is forgetting to handle the case where the target never appears. In this situation, equal_count remains 0.

For example:

nums = [1,2,3]
target = 4

The generated range becomes:

range(3, 3)

which correctly produces an empty list.

All Elements Equal the Target

If every value equals the target, then no values are smaller than the target.

For example:

nums = [2,2,2]
target = 2

Here:

smaller_count = 0
equal_count = 3

The algorithm correctly generates:

[0,1,2]

This verifies that the implementation properly handles consecutive target positions beginning at index 0.

Target Appears Only Once

Single-occurrence cases can expose off-by-one mistakes in range generation.

For example:

nums = [5,1,3]
target = 3

After counting:

smaller_count = 1
equal_count = 1

The generated indices become:

range(1, 2)

which correctly produces [1].

This confirms that the upper bound in the range construction is handled properly.