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.
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; }}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.