Find Target Indices After Sorting Array
EasyPrompt
You are given a 0-indexed integer array nums and a target element target.
A target index is an index i such that nums[i] == target.
Return a list of the target indices of nums after sorting nums in non-decreasing order. If there are no target indices, return an empty list. The returned list must be sorted in increasing order.
Example 1:
Input: nums = [1,2,5,2,3], target = 2
Output: [1,2]
Explanation: After sorting, nums is [1,2,2,3,5].
The indices where nums[i] == 2 are 1 and 2.Example 2:
Input: nums = [1,2,5,2,3], target = 3
Output: [3]
Explanation: After sorting, nums is [1,2,2,3,5].
The index where nums[i] == 3 is 3.Example 3:
Input: nums = [1,2,5,2,3], target = 5
Output: [4]
Explanation: After sorting, nums is [1,2,2,3,5].
The index where nums[i] == 5 is 4.
Constraints:
1 <= nums.length <= 1001 <= nums[i], target <= 100
Approaches
2 approaches with complexity analysis and trade-offs.
This approach directly follows the problem statement. First, we sort the input array nums in non-decreasing order. Then, we iterate through the sorted array to find all indices where the element is equal to the target and add these indices to a result list.
Algorithm
- Create an empty list,
result, to store the target indices. - Sort the input array
numsin non-decreasing order. - Iterate through the sorted
numsarray with an indexifrom 0 tonums.length - 1. - Inside the loop, if
nums[i]is equal totarget, add the indexito theresultlist. - After the loop finishes, return the
resultlist.
Walkthrough
The algorithm consists of two main steps:
-
Sorting: We use a standard library function, like
Arrays.sort()in Java, to sort the input arraynums. This operation has a time complexity of O(N log N), where N is the number of elements in the array. -
Scanning: After sorting, we perform a linear scan through the array from index 0 to N-1. During the scan, we check if the element at the current index
iis equal to thetarget. Ifnums[i] == target, we add the indexito our result list. Since we are iterating in increasing order of indices, the resulting list of indices will also be sorted.
import java.util.ArrayList;import java.util.Arrays;import java.util.List; class Solution { public List<Integer> targetIndices(int[] nums, int target) { // Step 1: Sort the array Arrays.sort(nums); List<Integer> result = new ArrayList<>(); // Step 2: Scan the sorted array to find target indices for (int i = 0; i < nums.length; i++) { if (nums[i] == target) { result.add(i); } } return result; }}Complexity
Time
O(N log N), where N is the number of elements in `nums`. The dominant operation is sorting the array. The subsequent linear scan takes O(N) time, which is overshadowed by the sorting time.
Space
O(K) or O(N) in the worst case. The space required for the output list is O(K), where K is the number of occurrences of the target. In the worst case, all elements could be the target, making it O(N). Additionally, the sorting algorithm might use O(log N) to O(N) space, depending on the implementation.
Trade-offs
Pros
Simple and straightforward to understand and implement.
Directly translates the problem description into code.
Cons
Not the most efficient solution due to the O(N log N) time complexity of sorting.
A more efficient approach is to avoid the O(N log N) sorting step. We can determine the final indices of the target elements by counting two things in a single pass: the number of elements smaller than the target and the number of elements equal to the target. The first target index will be the count of smaller elements, and the subsequent indices will follow consecutively.
Algorithm
- Initialize two integer variables:
lessThanCount = 0andtargetCount = 0. - Iterate through the input array
numsonce. - For each element
numinnums:- If
num < target, incrementlessThanCount. - If
num == target, incrementtargetCount.
- If
- Create an empty list,
result. - Run a loop from
i = 0totargetCount - 1. - In each iteration, add the index
lessThanCount + ito theresultlist. - Return the
resultlist.
Walkthrough
This method leverages a key insight: after sorting, all occurrences of the target will form a contiguous block. The starting index of this block is determined by the number of elements that are strictly smaller than the target.
The algorithm is as follows:
- Initialize two counters:
lessThanCount = 0andtargetCount = 0. - Iterate through the original
numsarray once. For each elementnum:- If
num < target, incrementlessThanCount. - If
num == target, incrementtargetCount.
- If
- After the pass,
lessThanCountgives us the starting index for the target values in the sorted array. - Create an empty result list.
- Add the indices to the result list by running a loop
targetCounttimes. In each iteration, addlessThanCount + i(whereiis the loop variable from 0 totargetCount - 1) to the list.
This way, we construct the final sorted list of indices without ever actually sorting the array.
import java.util.ArrayList;import java.util.List; class Solution { public List<Integer> targetIndices(int[] nums, int target) { int lessThanCount = 0; int targetCount = 0; // Step 1: Count elements smaller than and equal to target for (int num : nums) { if (num < target) { lessThanCount++; } else if (num == target) { targetCount++; } } List<Integer> result = new ArrayList<>(); // Step 2: Construct the result list based on counts // The first index of target will be at lessThanCount for (int i = 0; i < targetCount; i++) { result.add(lessThanCount + i); } return result; }}Complexity
Time
O(N), where N is the number of elements in `nums`. We perform a single pass through the array to count the elements, and another loop to build the result list which runs `K` times (where K is the count of the target). In the worst case, K=N, but the total time is still proportional to N.
Space
O(K), where K is the number of occurrences of the target. This space is used for the output list. In the worst case, K=N, making the space complexity O(N).
Trade-offs
Pros
More efficient with a linear time complexity.
Avoids the overhead of a full sort operation.
Cons
Slightly less intuitive than the direct sorting approach, as it requires an insight about the position of elements in a sorted array.
Solutions
Solution
class Solution {public List<Integer> targetIndices(int[] nums, int target) { Arrays.sort(nums); List<Integer> ans = new ArrayList<>(); for (int i = 0; i < nums.length; ++i) { if (nums[i] == target) { ans.add(i); } } return ans; }}class Solution {public: vector<int> targetIndices(vector<int> &nums, int target) { sort(nums.begin(), nums.end()); vector<int> ans; for (int i = 0; i < nums.size(); ++i) { if (nums[i] == target) { ans.push_back(i); } } return ans; }};class Solution: def targetIndices(self, nums: List[int], target: int) -> List[int]: nums . sort() return [i for i, v in enumerate(nums) if v == target]Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.