Problem Description

You are given an integer array nums (0-indexed) and a target value target.

The task is to:

1. Sort the array nums in non-decreasing order (ascending order)
2. Find all indices where the value equals target in the sorted array
3. Return these indices as a list

Key points:

• A target index is defined as an index i where nums[i] == target
• The array must be sorted first before finding the target indices
• If no elements equal the target, return an empty list
• The returned list of indices must be in increasing order (which naturally happens since we're checking indices sequentially)

For example:

• If nums = [1, 2, 5, 2, 3] and target = 2
• After sorting: nums = [1, 2, 2, 3, 5]
• The value 2 appears at indices 1 and 2
• Return [1, 2]

The solution approach is straightforward:

1. Sort the array using nums.sort()
2. Use list comprehension to iterate through the sorted array with enumerate() to get both index and value
3. Include indices where the value equals the target: [i for i, v in enumerate(nums) if v == target]

Intuition

The problem asks us to find indices of a target value after sorting. The most direct approach is to do exactly what the problem states: sort first, then find the indices.

Why does this work? When we sort an array, all occurrences of the same value will be grouped together consecutively. This means if the target value exists in the array, all instances of it will appear in a continuous block after sorting.

For example, if we have [5, 2, 3, 2, 1] with target 2, after sorting we get [1, 2, 2, 3, 5]. Notice how both 2s are now adjacent at indices 1 and 2.

Since we're iterating through the sorted array from left to right (index 0 to n-1), and checking each element against the target, we naturally collect the indices in increasing order. This eliminates the need for any additional sorting of the result.

The beauty of this approach lies in its simplicity - we don't need to overthink it. We could try to count elements less than the target to predict where it would appear after sorting, but that would be more complex and error-prone. Instead, we:

1. Sort the array (which Python does efficiently with sort())
2. Walk through it once with enumerate() to get index-value pairs
3. Filter for values that match our target

This gives us a clean one-liner solution after sorting: [i for i, v in enumerate(nums) if v == target].

Learn more about Binary Search and Sorting patterns.

Solution Approach

The implementation follows a two-step process:

Step 1: Sort the array

nums.sort()

This uses Python's built-in sort() method which sorts the list in-place in non-decreasing order. The time complexity of this operation is O(n log n) where n is the length of the array.

Step 2: Find and collect target indices

return [i for i, v in enumerate(nums) if v == target]

This step uses a list comprehension with enumerate() to achieve multiple things simultaneously:

• enumerate(nums) creates pairs of (index, value) for each element in the sorted array
• for i, v in enumerate(nums) unpacks each pair into index i and value v
• if v == target filters to only include indices where the value matches our target
• The list comprehension [i ...] collects all matching indices into a new list

The enumerate function iterates through the array exactly once, making this step O(n) in time complexity.

Why this works: After sorting, if the target exists in the array, all occurrences will be consecutive. As we iterate from index 0 to n-1, we encounter these occurrences in order, naturally producing a sorted list of indices.

Overall Complexity:

• Time Complexity: O(n log n) dominated by the sorting step
• Space Complexity: O(k) where k is the number of occurrences of the target (for the output list)

The solution is elegant in its simplicity - it directly implements what the problem asks for without any unnecessary complications.

Example Walkthrough

Let's walk through a concrete example to see how the solution works step by step.

Example: nums = [5, 3, 2, 3, 1] and target = 3

Step 1: Sort the array

• Original array: [5, 3, 2, 3, 1]
• After nums.sort(): [1, 2, 3, 3, 5]
• Notice how both occurrences of 3 are now adjacent at positions 2 and 3

Step 2: Find target indices using enumerate Let's trace through the list comprehension [i for i, v in enumerate(nums) if v == target]:

Result: [2, 3]

The indices are automatically in increasing order because we iterate through the sorted array from left to right. Both occurrences of the target value 3 are found at indices 2 and 3 in the sorted array.

Edge Case Example: nums = [4, 1, 2] and target = 5

• After sorting: [1, 2, 4]
• No element equals 5, so the list comprehension produces an empty list []

This walkthrough demonstrates how the two-step approach (sort, then find) efficiently solves the problem with clean, readable code.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n log n)

• The nums.sort() operation uses Python's Timsort algorithm, which has a time complexity of O(n log n) where n is the length of the array
• The list comprehension [i for i, v in enumerate(nums) if v == target] iterates through all elements once, taking O(n) time
• The overall time complexity is dominated by the sorting step: O(n log n) + O(n) = O(n log n)

Space Complexity: O(n)

• The nums.sort() operation sorts the list in-place, requiring O(1) auxiliary space in Python (though technically Timsort can use up to O(n) space in worst case for its merge operations)
• The list comprehension creates a new list to store the result indices, which in the worst case (when all elements equal target) can contain n elements, requiring O(n) space
• Therefore, the overall space complexity is O(n)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Assuming the Original Array Indices are Needed

A common misunderstanding is thinking we need to track the indices from the original unsorted array. Some might try to create index mappings before sorting or use more complex data structures.

Why it's wrong: The problem specifically asks for indices in the sorted array, not the original array.

Incorrect approach example:

# Wrong: Trying to preserve original indices
original_indices = [(nums[i], i) for i in range(len(nums))]
original_indices.sort()
# This tracks wrong indices!

Correct understanding: Simply sort first, then find indices in the sorted array.

2. Using Binary Search Unnecessarily

Since the array is sorted, some might think binary search is required to find the target efficiently.

Why it's a pitfall: While binary search can find one occurrence of the target in O(log n), you still need to check neighboring elements to find all occurrences, which could be O(n) in the worst case (when all elements equal target). The simple linear scan is cleaner and has the same worst-case complexity.

Overly complex approach:

# Unnecessary complexity with binary search
import bisect
nums.sort()
left = bisect.bisect_left(nums, target)
right = bisect.bisect_right(nums, target)
return list(range(left, right))

Better approach: The simple list comprehension is more readable and equally efficient.

3. Forgetting that sort() Modifies In-Place

Some might not realize that nums.sort() modifies the original list and try to use the unsorted nums afterward.

Incorrect pattern:

nums.sort()
# Later trying to use original order
return [i for i, v in enumerate(original_nums) if v == target]  # original_nums doesn't exist!

Solution: If you need to preserve the original array for any reason, create a copy first:

sorted_nums = sorted(nums)  # Creates a new sorted list
# OR
sorted_nums = nums.copy()
sorted_nums.sort()

4. Not Handling Edge Cases Mentally

While the given solution handles these correctly, it's important to verify:

• Empty array: nums = [] returns []
• Target not in array: returns []
• All elements equal target: returns [0, 1, 2, ..., n-1]
• Single element: works correctly

The beauty of the list comprehension approach is that it naturally handles all these cases without special checks.