Find Target Indices After Sorting Array
Without sorting, count smaller and equal elements to derive the target's index range.
3 min read
counting sorting
Problem#
After sorting nums non-decreasingly, return all indices where the value equals target.
Examples#
nums = [1,2,5,2,3], target = 2→[1,2]nums = [1,2,5,2,3], target = 3→[3]nums = [1,2,5,2,3], target = 5→[4]
Constraints#
1 <= nums.length <= 100,1 <= nums[i], target <= 100.
Approach#
Sorting is not actually required. Count how many elements are strictly less than target (this is the first index) and how many equal target (this is the count). Build the output range.
Solution#
class Solution {public: vector<int> targetIndices(vector<int>& nums, int target) { int less = 0, eq = 0; for (int x : nums) { if (x < target) ++less; else if (x == target) ++eq; } vector<int> ans; ans.reserve(eq); for (int i = 0; i < eq; ++i) ans.push_back(less + i); return ans; }};func targetIndices(nums []int, target int) []int { less, eq := 0, 0 for _, x := range nums { if x < target { less++ } else if x == target { eq++ } } ans := make([]int, 0, eq) for i := 0; i < eq; i++ { ans = append(ans, less+i) } return ans}from typing import List
class Solution: def targetIndices(self, nums: List[int], target: int) -> List[int]: less = eq = 0 for x in nums: if x < target: less += 1 elif x == target: eq += 1 return [less + i for i in range(eq)]var targetIndices = function(nums, target) { let less = 0, eq = 0; for (const x of nums) { if (x < target) less++; else if (x === target) eq++; } const ans = []; for (let i = 0; i < eq; i++) ans.push(less + i); return ans;};class Solution { public List<Integer> targetIndices(int[] nums, int target) { int less = 0, eq = 0; for (int x : nums) { if (x < target) less++; else if (x == target) eq++; } List<Integer> ans = new ArrayList<>(eq); for (int i = 0; i < eq; i++) ans.add(less + i); return ans; }}function targetIndices(nums: number[], target: number): number[] { let less = 0, eq = 0; for (const x of nums) { if (x < target) less++; else if (x === target) eq++; } const ans: number[] = []; for (let i = 0; i < eq; i++) ans.push(less + i); return ans;}Editorial#
After sorting, all elements < target come first (occupying indices 0..less-1), then equal elements occupy less..less+eq-1. Counting in one pass avoids the O(n log n) sort.
Complexity#
- Time: O(n).
- Space: O(1) extra.
Concept revision#
Related#