Find Target Indices After Sorting Array

easy binary search sorting

Problem

You are given an array of integers nums and an integer target. Imagine the array is sorted in non-decreasing order. A target index is any position in this sorted array that holds the value target. Return a list of all target indices, sorted in increasing order. If target does not appear in nums, return an empty list.

Inputnums = [1, 2, 5, 2, 3], target = 2

Output[1, 2]

Sorted, nums becomes [1, 2, 2, 3, 5]. The value 2 sits at positions 1 and 2, so the target indices are [1, 2].

nums (comma-separated)

target

def target_indices(nums, target):
    nums.sort()
    lo, hi = 0, len(nums)
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    res = []
    while lo < len(nums) and nums[lo] == target:
        res.append(lo)
        lo += 1
    return res

function targetIndices(nums, target) {
  nums.sort((a, b) => a - b);
  let lo = 0, hi = nums.length;
  while (lo < hi) {
    const mid = (lo + hi) >> 1;
    if (nums[mid] < target) lo = mid + 1;
    else hi = mid;
  }
  const res = [];
  while (lo < nums.length && nums[lo] === target) {
    res.push(lo);
    lo += 1;
  }
  return res;
}

class Solution {
    public List<Integer> targetIndices(int[] nums, int target) {
        Arrays.sort(nums);
        int lo = 0, hi = nums.length;
        while (lo < hi) {
            int mid = (lo + hi) >>> 1;
            if (nums[mid] < target) lo = mid + 1;
            else hi = mid;
        }
        List<Integer> res = new ArrayList<>();
        while (lo < nums.length && nums[lo] == target) {
            res.add(lo);
            lo += 1;
        }
        return res;
    }
}

vector<int> targetIndices(vector<int>& nums, int target) {
    sort(nums.begin(), nums.end());
    int lo = 0, hi = (int)nums.size();
    while (lo < hi) {
        int mid = (lo + hi) / 2;
        if (nums[mid] < target) lo = mid + 1;
        else hi = mid;
    }
    vector<int> res;
    while (lo < (int)nums.size() && nums[lo] == target) {
        res.push_back(lo);
        lo += 1;
    }
    return res;
}

Explanation

The question asks where the value target would land if the array were sorted. The most direct way to answer that is to actually sort the array first. Once sorted, every copy of target sits together in one contiguous block, so the answer is simply the run of indices covering that block.

To find where that block begins we use a lower-bound binary search. We keep a window [lo, hi) and repeatedly look at the middle element. If the middle value is smaller than the target, the first target (if any) must be to the right, so we move lo past it. Otherwise the answer is at mid or to its left, so we pull hi down to mid. When the window collapses, lo points at the first position whose value is at least the target.

From that first position we walk forward while the value still equals target, collecting each index. Because the array is sorted, these indices are already increasing, which is exactly the order the problem wants.

Example: nums = [1, 2, 5, 2, 3], target = 2. After sorting we get [1, 2, 2, 3, 5]. The binary search stops at lo = 1 (the first value that is at least 2). We then scan forward: index 1 is a 2 and index 2 is a 2, but index 3 is a 3, so we stop. The answer is [1, 2].

If the target never appears, the forward scan adds nothing and we return an empty list. The dominant cost is the sort; the binary search and scan are cheap by comparison.

Time: O(n log n) Space: O(1)