Find Target Indices After Sorting Array

LeetCode 2210 | Difficulty: Easy

Easy

Problem Description

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 <= 100`

- `1 <= nums[i], target <= 100`

Topics: Array, Binary Search, Sorting

---

Approach

Binary Search

Binary search reduces the search space by half at each step. The key insight is identifying the monotonic property — what condition lets you decide to go left or right?

When to use

Sorted array, or searching for a value in a monotonic function/space.

Sorting

Sort the input to bring related elements together or enable binary search. Consider: does sorting preserve the answer? What property does sorting give us?

When to use

Grouping, finding closest pairs, interval problems, enabling two-pointer or binary search.

---

Solutions

Solution 1: C# (Best: 177 ms)

Metric	Value
Runtime	177 ms
Memory	42 MB
Date	2022-02-16

Solution

public class Solution {
    public IList<int> TargetIndices(int[] nums, int target) {
        int count1 = 0, count2 = 0, count3 = 0;
    for (int i = 0; i < nums.Length; i++)
    {
        if (nums[i] < target) count1++;
        else if (nums[i] == target) count2++;
        else count3++;
    }
    return Enumerable.Range(count1, count2).ToList();
    }
}

📜 1 more C# submission(s)

Submission (2022-02-16) — 189 ms, 42 MB

public class Solution {
    public IList<int> TargetIndices(int[] nums, int target) {
        int count1 = 0, count2 = 0;
    for (int i = 0; i < nums.Length; i++)
    {
        if (nums[i] < target) count1++;
        else if (nums[i] == target) count2++;
    }
    return Enumerable.Range(count1, count2).ToList();
    }
}

---

Complexity Analysis

Approach	Time	Space
Binary Search	$O(log n)$	$O(1)$
Sort + Process	$O(n log n)$	$O(1) to O(n)$

---

Interview Tips

Key Points

• Start by clarifying edge cases: empty input, single element, all duplicates.
• Precisely define what the left and right boundaries represent, and the loop invariant.
• LeetCode provides 2 hint(s) for this problem — try solving without them first.

💡 Hints

Hint 1: Try "sorting" the array first.

Hint 2: Now find all indices in the array whose values are equal to target.