Find Target Indices After Sorting Array

Without sorting, count smaller and equal elements to derive the target's index range.

Easy
Time O(n) Space O(1)
LeetCode
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#

Find Target Indices After Sorting Array
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;
}
};

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#

Search ESC

Keyboard shortcuts

Shortcuts are disabled while typing in inputs.