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.

Description Hints 2 Solution Video 9:48

2089. Find Target Indices After Sorting Array

Easy82.1% acceptance3 companies

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

Asked at 3 companies

Google Amazon Meta

Topics

Hints open one at a time

Hint 1

Try "sorting" the array first.

Hint 2

Now find all indices in the array whose values are equal to target.

9:48

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution