Solution: Find Target Indices After Sorting Array

Let’s solve the Find Target Indices After Sorting Array problem using the Sort and Search pattern.

Statement

You are given a 0-indexed array of positive integers, nums, and a value, target. The target represents an index ii 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:

  • 11 \leq nums.length 100\leq 100

  • 11 \leq nums[i], target 100\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:

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.