Skip to main content
Talentd

Find Target Indices After Sorting Array - Solution & Explanation

EasyArrayBinary SearchSorting12 min readAsked at: Amazon, Meta, Google
Practice this problem

Problem Statement

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

Approach Overview

Problem Overview: You receive an integer array nums and a value target. After sorting the array in non‑decreasing order, return all indices where target appears. The key detail: the returned indices must correspond to the positions of target in the sorted array, not the original one.

Approach 1: Sorting and Linear Search (Time: O(n log n), Space: O(1) to O(n))

The most direct solution sorts the array first, then scans it once to collect positions where the value equals target. Start by calling a standard sorting routine (such as quicksort or mergesort). After sorting, iterate through the array from index 0 to n-1. Each time you encounter nums[i] == target, push i into the result list. Sorting dominates the runtime at O(n log n), while the scan is O(n). Extra space depends on the sorting implementation—some languages use in‑place sorting with O(1) auxiliary space while others allocate O(n). This approach is easy to reason about and mirrors the problem statement directly. It relies heavily on standard sorting operations and simple iteration over an array.

Approach 2: Counting and Offset Calculation (Time: O(n), Space: O(1))

The sorted order of elements reveals an important property: all values smaller than target appear before it, and all larger values appear after it. You do not actually need to sort the array to determine where target would land. Instead, iterate through the array once and count two values: how many numbers are strictly less than target, and how many are equal to it. If less is the count of elements smaller than the target and equal is the number of occurrences of the target, then in the sorted array the target will occupy indices from less to less + equal - 1. Generate that range directly. This removes sorting entirely, giving linear time O(n) and constant space O(1). The idea is similar to the counting phase of counting sort, where relative order is determined by frequency counts instead of comparisons.

Even though the problem is tagged with binary search, binary search becomes useful only if the array is already sorted. Here, the counting insight eliminates both sorting and searching.

Recommended for interviews: Start with the sorting approach to demonstrate that you correctly interpret the problem and can implement the straightforward solution. Then point out that sorting is unnecessary. The counting method shows stronger algorithmic thinking because it derives the final indices mathematically in O(n) time and O(1) space.

Approach 1: Approach 1: Sorting and Linear Search

This approach involves first sorting the array, then performing a linear search to find all indices of the target element. Since we are sorting the array, the resulting indices will naturally be in increasing order, as required.

This C solution uses the qsort function from the C standard library to sort the array. After sorting, it traverses the sorted array linearly to collect indices where the target value occurs. The results are stored in an array and printed.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) ignoring result array storage, as sorting is done in place.

Try this approach in the editor →

Approach 2: Approach 2: Counting Sort and Offset Calculation

This approach utilizes counting sort to efficiently count occurrences of each number up to the target value, allowing determination of the starting index of the target in the sorted array without fully sorting it. This approach leverages the constraint of numbers being less than 101 for optimal performance.

In C, this solution utilizes a counting array to tally occurrences of each number so that it calculates the start index of the target in a potential sorted order directly.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n + m), where n is the number of elements, and m is the range (here 101).
Space Complexity: O(m) due to the counting array.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Sorting and Linear Search

Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) ignoring result array storage, as sorting is done in place.

Approach 2: Counting Sort and Offset Calculation

Time Complexity: O(n + m), where n is the number of elements, and m is the range (here 101).
Space Complexity: O(m) due to the counting array.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Sorting and Linear SearchO(n log n)O(1) to O(n)Simple and direct solution when sorting is acceptable or already required elsewhere.
Counting and Offset CalculationO(n)O(1)Best choice when you want optimal performance without sorting the array.

Video Solution

LeetCode 2089 | Find Target Indices After Sorting Array | Day 31 | 100 Days LeetCode Challenge | DSA • edSlash • 5,122 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Find Target Indices After Sorting Array easy or hard?
LeetCode classifies this problem as Easy. The straightforward sorting solution is simple to implement, while the O(n) counting technique adds a small optimization that demonstrates stronger algorithmic reasoning.
Find Target Indices After Sorting Array Python/Java solution
In Python or Java, the basic solution sorts the array using `sort()` and scans for matches. The optimal implementation loops once through the array, counts values less than and equal to the target, and then constructs the resulting index list.
How to solve Find Target Indices After Sorting Array in O(n)?
Traverse the array once and maintain two counters: the number of elements less than the target and the number equal to it. After the scan, generate indices starting from `less` up to `less + equal - 1`. These represent the exact positions of the target after sorting.
What is the best approach for Find Target Indices After Sorting Array?
The optimal approach counts how many numbers are smaller than the target and how many equal it. If `less` elements are smaller and `equal` elements match the target, the target occupies indices from `less` to `less + equal - 1` in the sorted array. This method runs in O(n) time and uses O(1) extra space.
Is Find Target Indices After Sorting Array asked at Google/Amazon/Meta?
Problems involving counting frequencies and determining positions after sorting appear frequently in interviews at large tech companies. Variations of this pattern show up in Google and Amazon interview prep sets because they test understanding of sorting properties and linear scans.
What data structure is used in Find Target Indices After Sorting Array?
The problem mainly uses arrays and simple counters. The sorting approach relies on array sorting algorithms, while the optimal solution only uses integer counters to track frequencies and compute index offsets.
What is the time complexity of Find Target Indices After Sorting Array?
The straightforward method sorts the array and scans it, which costs O(n log n) time due to sorting. The optimal counting approach avoids sorting and finishes in O(n) time with constant extra space.

Ready to solve this problem?

Practice Find Target Indices After Sorting Array with our built-in code editor and test cases.

Practice on FleetCode
Previous

Find First and Last Position of Element in Sorted Array

Next

Find Words Containing Character