Introduction

Finding an element in an array is a common programming task, but what happens when the required answer is not the element itself, but every position where it appears after sorting?

In LeetCode 2089 – Find Target Indices After Sorting Array, the array must first be arranged in non-decreasing order. After sorting, the goal is to return the indices where the specified target value appears. If the target occurs multiple times, every matching index must be included in the result.

The solution is straightforward: sort the array, scan it from left to right, and store each index whose value matches the target. Because the array is already sorted, the collected indices naturally appear in increasing order.

Problem Statement

Given a zero-indexed integer array nums and an integer target, return a list containing all indices i such that nums[i] == target after sorting nums in non-decreasing order.

If the target does not appear in the array, return an empty list.

Problem link: LeetCode 2089 – Find Target Indices After Sorting Array

Example 1

After sorting, the array becomes:

The target 2 appears at indices 1 and 2, so the result is [1, 2].

Example 2

After sorting, the value 3 appears at index 3.

Example 3

The largest value, 5, appears at index 4 after sorting.

Approach: Sort the Array and Find Matching Indices

The main observation is that the target's position can change when the array is sorted. Therefore, checking the original array without sorting would not necessarily return the required indices.

The solution uses two simple steps.

Step 1: Sort the array

Java's Arrays.sort() arranges the integers in ascending order. Equal values become adjacent, making it easy to identify every occurrence of the target.

Step 2: Traverse the sorted array

The loop checks every position. Whenever the current value equals target, its index is added to the result list.

Since the traversal moves from index 0 toward the end of the array, the resulting indices are automatically in increasing order. There is no need to sort the result list separately.

Java Solution

The following implementation uses the submitted approach with Arrays.sort() and an ArrayList to collect the matching indices.

Step-by-Step Dry Run

Consider the following input:

1. Sort the array

After calling Arrays.sort(nums), the array becomes:

The result list is initially empty:

2. Check each index

Both occurrences of 2 are collected.

The final result is:

What If the Target Is Missing?

Suppose the sorted array is:

and the target is 4.

No element matches the target, so the loop never adds an index to the list. The method returns:

This also handles the case where the target appears only once or appears multiple times.

Complexity Analysis

Let n be the number of elements in the array.

Time complexity: O(n log n)

1. Sorting the array takes O(n log n) time.
2. Traversing the array takes O(n) time.

Sorting dominates the overall time complexity, making the total O(n log n).

Auxiliary space: The result list requires O(k) space, where k is the number of target occurrences. Java's sorting implementation may also use additional internal space.

Interview Tip

When a problem asks for indices after sorting, first determine whether the positions refer to the original array or the sorted array. In this problem, the indices belong to the sorted array.

Also, repeated target values must all be included. A solution that returns immediately after finding the first match would fail when the target occurs more than once.

For this implementation, a full traversal is simple and reliable. Because equal values are grouped together after sorting, a binary-search-based solution could also identify the target's first and last positions, although that additional complexity is unnecessary for the given constraints.

Conclusion

LeetCode 2089 is a useful exercise in sorting, array traversal, and handling duplicate values. By sorting the array first and collecting every index where nums[i] == target, the solution produces the required result without needing additional index-ordering logic.

The key takeaway is to perform operations in the order required by the problem: sort first, then find and return all matching indices.