Solution: Find Target Indices After Sorting Array

Statement

You are given a 0-indexed array of positive integers, nums, and a value, target. The target represents an index $i$ in the array such that nums[i] == target.

Your task is to return a list of indexes of nums where the value equals target after sorting the array in nondecreasing order. If no such indexes exist, return an empty list. Ensure the returned list is sorted in increasing order.

Constraints:

• $1 \leq$ nums.length $\leq 100$

• $1 \leq$ nums[i], target $\leq 100$

Solution

In this problem, we will utilize the Sort and Search pattern to find the indexes of a target value in a sorted array. The core idea is to first sort the input array, nums, in nondecreasing order, which ensures that we can easily identify the positions of the target value. After sorting, we will search through the sorted array to collect the indexes where target appears. This approach combines sorting to organize the data with a linear search to gather the desired indexes, making it both straightforward and efficient.

Let’s break down the algorithm steps involved in the solution:

1. Sorting the array:

   1. We first sort the input array nums to ensure that the target value’s positions can be easily identified after the array is in a nondecreasing order.

2. Identifying the target indexes:

   1. After sorting the array, we create an empty array result that stores the matching values' indexes.

   2. Next, we find the indexes of the target value in the sorted array. We do this by iterating through the sorted array and checking where the value matches the target.

      1. If it does, we store the index at which the target appears in the result array.

3. Returning the result:

   1. After iterating through nums, we return result containing indexes at which the target appears in the sorted nums array.

Let’s look at the following illustration to get a better understanding of the solution: