Find Target Indices After Sorting Array solution and explanation
Google
9 more videos on this problem
LeetCode 2089 | Find Target Indices After Sorting Array | Day 31 | 100 Days LeetCode Challenge | DSAedSlash · 9:48 · 5K views
Find Target Indices After Sorting Array | LeetCode 2089 | CppCodeClips with Abhishek Ranjan · 5:34 · 3K views
Find target indices after sorting array leetcode (Hindi)Engineering Digest · 5:44 · 2K views
2089 Find Target Indices After Sorting Array (Leetcode Easy)Programming Live with Larry · 2:38 · 1K views
LeetCode 2089 | Find Target Indices After Sorting Array | Binary search | PythonTechtonic Knights · 5:13 · 600 views
2089 Find Target Indices After Sorting ArrayMath Geeks · 1:22 · 318 views
2089. Find Target Indices After Sorting Array with Python | Leetcode with Python #youtube #youtuberArsalan Ahmed · 3:49 · 306 views
Leetcode problem no - 2089 : Find Target Indices After Sorting Array (using C++)Shohanur Rifat · 8:17 · 178 views
LeetCode 2089 | Find Target Indices After Sorting Array | Array | JavaSleepy Cracker · 1:24 · 140 views
Find Target Indices After Sorting Array | Leetcode 2089 | Approach + Code with explanation.Pirai's Academy · 17:52 · 104 views
The problem
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 <= 1001 <= 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.
def target_indices(nums, target):
nums.sort()
return [i for i, num in enumerate(nums) if num == target]
nums = [1, 2, 5, 2, 3]
target = 2
print(target_indices(nums, target))import java.util.Arrays;
import java.util.ArrayList;
import java.util.List;
public class Solution {
public static List<Integer> targetIndices(int[] nums, int target) {
Arrays.sort(nums);
List<Integer> result = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
if (nums[i] == target) {
result.add(i);
}
}
return result;
}
public static void main(String[] args) {
int[] nums = {1, 2, 5, 2, 3};
int target = 2;
List<Integer> indices = targetIndices(nums, target);
System.out.println(indices);
}
}#include <iostream>
#include <vector>
#include <algorithm>
std::vector<int> targetIndices(std::vector<int>& nums, int target) {
std::sort(nums.begin(), nums.end());
std::vector<int> result;
for (int i = 0; i < nums.size(); ++i) {
if (nums[i] == target) {
result.push_back(i);
}
}
return result;
}
int main() {
std::vector<int> nums = {1, 2, 5, 2, 3};
int target = 2;
std::vector<int> indices = targetIndices(nums, target);
std::cout << "[";
for (size_t i = 0; i < indices.size(); ++i) {
std::cout << indices[i] << (i < indices.size() - 1 ? ", " : "");
}
std::cout << "]\n";
return 0;
}function targetIndices(nums, target) {
nums.sort((a, b) => a - b);
const result = [];
nums.forEach((num, index) => {
if (num === target) result.push(index);
});
return result;
}
const nums = [1, 2, 5, 2, 3];
const target = 2;
console.log(targetIndices(nums, target));#include <stdio.h>
#include <stdlib.h>
int compare(const void *a, const void *b) {
return (*(int*)a - *(int*)b);
}
void findTargetIndices(int* nums, int numsSize, int target, int* result, int* returnSize) {
qsort(nums, numsSize, sizeof(int), compare);
int index = 0;
for (int i = 0; i < numsSize; ++i) {
if (nums[i] == target) {
result[index++] = i;
}
}
*returnSize = index;
}
int main() {
int nums[] = {1, 2, 5, 2, 3};
int target = 2;
int result[5]; // Maximum size needed
int returnSize = 0;
findTargetIndices(nums, 5, target, result, &returnSize);
printf("[");
for (int i = 0; i < returnSize; ++i) {
printf("%d%s", result[i], i < returnSize - 1 ? ", " : "");
}
printf("]\n");
return 0;
}using System;
using System.Collections.Generic;
class Solution {
public static List<int> TargetIndices(int[] nums, int target) {
Array.Sort(nums);
var result = new List<int>();
for (int i = 0; i < nums.Length; i++) {
if (nums[i] == target) {
result.Add(i);
}
}
return result;
}
static void Main() {
int[] nums = {1, 2, 5, 2, 3};
int target = 2;
List<int> indices = TargetIndices(nums, target);
Console.WriteLine("[" + string.Join(", ", indices) + "]");
}
}The Python solution sorts the list using sort() and then uses a list comprehension with enumerate to gather all indices of the target element.
Time Complexity: O(n log n) for sorting.
Space Complexity: O(n) for the resulting list.
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.
def target_indices(nums, target):
count = [0] * 101
for num in nums:
count[num] += 1
start = sum(count[:target])
return list(range(start, start + count[target]))
nums = [1, 2, 5, 2, 3]
target = 2
print(target_indices(nums, target))import java.util.ArrayList;
import java.util.List;
public class Solution {
public static List<Integer> targetIndices(int[] nums, int target) {
int[] count = new int[101];
for (int num : nums) {
count[num]++;
}
int start = 0;
for (int i = 0; i < target; i++) {
start += count[i];
}
List<Integer> result = new ArrayList<>();
for (int i = start; i < start + count[target]; i++) {
result.add(i);
}
return result;
}
public static void main(String[] args) {
int[] nums = {1, 2, 5, 2, 3};
int target = 2;
List<Integer> indices = targetIndices(nums, target);
System.out.println(indices);
}
}#include <iostream>
#include <vector>
#include <cstring>
std::vector<int> targetIndices(std::vector<int>& nums, int target) {
int count[101] = {0};
for (int num : nums) {
count[num]++;
}
int start = 0;
for (int i = 0; i < target; ++i) {
start += count[i];
}
std::vector<int> result;
for (int i = 0; i < count[target]; ++i) {
result.push_back(start + i);
}
return result;
}
int main() {
std::vector<int> nums = {1, 2, 5, 2, 3};
int target = 2;
std::vector<int> indices = targetIndices(nums, target);
std::cout << "[";
for (size_t i = 0; i < indices.size(); ++i) {
std::cout << indices[i] << (i < indices.size() - 1 ? ", " : "");
}
std::cout << "]\n";
return 0;
}function targetIndices(nums, target) {
const count = new Array(101).fill(0);
nums.forEach(num => count[num]++);
const start = count.slice(0, target).reduce((a, b) => a + b, 0);
return Array.from({ length: count[target] }, (v, i) => start + i);
}
const nums = [1, 2, 5, 2, 3];
const target = 2;
console.log(targetIndices(nums, target));#include <stdio.h>
#include <string.h>
void findTargetIndices(int* nums, int numsSize, int target, int* result, int* returnSize) {
int count[101];
memset(count, 0, sizeof(count));
for (int i = 0; i < numsSize; ++i) {
count[nums[i]]++;
}
int start = 0;
for (int i = 0; i < target; ++i) {
start += count[i];
}
for (int i = start; i < start + count[target]; ++i) {
result[i - start] = i;
}
*returnSize = count[target];
}
int main() {
int nums[] = {1, 2, 5, 2, 3};
int target = 2;
int result[5]; // Maximum size needed
int returnSize = 0;
findTargetIndices(nums, 5, target, result, &returnSize);
printf("[");
for (int i = 0; i < returnSize; ++i) {
printf("%d%s", result[i], i < returnSize - 1 ? ", " : "");
}
printf("]\n");
return 0;
}using System;
using System.Collections.Generic;
class Solution {
public static List<int> TargetIndices(int[] nums, int target) {
int[] count = new int[101];
foreach (int num in nums) {
count[num]++;
}
int start = 0;
for (int i = 0; i < target; i++) {
start += count[i];
}
var result = new List<int>();
for (int i = 0; i < count[target]; i++) {
result.Add(start + i);
}
return result;
}
static void Main() {
int[] nums = {1, 2, 5, 2, 3};
int target = 2;
List<int> indices = TargetIndices(nums, target);
Console.WriteLine("[" + string.Join(", ", indices) + "]");
}
}In Python, this approach builds a list of 101 integers to serve as counts. It calculates start index for the target without sorting fully.
Time Complexity: O(n + m), n is the list size and m is max value (101).
Space Complexity: O(m).
Approach 3: Default Approach
function targetIndices(nums: number[], target: number): number[] {
nums.sort((a, b) => a - b);
let ans: number[] = [];
for (let i = 0; i < nums.length; ++i) {
if (nums[i] == target) {
ans.push(i);
}
}
return ans;
}func targetIndices(nums []int, target int) (ans []int) {
sort.Ints(nums)
for i, v := range nums {
if v == target {
ans = append(ans, i)
}
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Sorting and Linear Search | Time Complexity: O(n log n) for sorting. |
| Approach 2: Counting Sort and Offset Calculation | Time Complexity: O(n + m), n is the list size and m is max value (101). |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting and Linear Search | O(n log n) | O(1) to O(n) | Simple and direct solution when sorting is acceptable or already required elsewhere. |
| Counting and Offset Calculation | O(n) | O(1) | Best choice when you want optimal performance without sorting the array. |
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.