2089. Find Target Indices After Sorting Array

EasyView on LeetCode

Array Binary Search Sorting

Time: O(n)

Space: O(1)

Problem Overview

Sorting the array would put every value smaller than target first, then every copy of target in one contiguous block.

Intuition

Sorting the array would put every value smaller than target first, then every copy of target in one contiguous block. The indices of that block are completely determined by how many values are smaller and how many equal the target, so the array never needs to be sorted. One pass counts both quantities, and the answer is the consecutive indices that start at the smaller-count.

Algorithm

1Scan nums once. Count values strictly less than target and values equal to target.
2Presize a list to the equal count.
3Append less, less + 1, ..., less + eq - 1.
4Return that list, which is empty when the target never appears.

Example Walkthrough

Input: nums = [1,2,5,2,3], target = 2

1.One value is less than 2, and two values equal 2.
2.After a conceptual sort the twos sit at indices 1 and 2.
3.The answer list is therefore [1, 2].

Output: [1, 2]

Common Pitfalls

•Do not sort. Counting smaller and equal values is enough and stays linear.
•Indices are 0-based and must be returned in increasing order, which the consecutive range already gives.
•Values greater than target never affect the answer indices.
•If the target is missing, the equal count is 0 and the result is an empty list.

2089.cs

// Approach: After sorting, every value smaller than target comes first, then
// every copy of target in a contiguous block. One pass counts how many values
// are less than target and how many equal it; the answer indices are then
// lessCount, lessCount+1, ..., lessCount+eqCount-1. Sorting is unnecessary.
// Time: O(n) Space: O(1) besides the output

public class Solution
{
    public IList<int> TargetIndices(int[] nums, int target)
    {
        int less = 0, eq = 0;
        foreach (int num in nums)
        {
            if (num < target)
                less++;
            else if (num == target)
                eq++;
        }

        var ans = new List<int>(eq);
        for (int i = 0; i < eq; i++)
            ans.Add(less + i);
        return ans;
    }
}

Was this solution helpful?