Find Target Indices After Sorting Array

Find Target Indices After Sorting Array

What is this problem about?

The Find Target Indices After Sorting Array interview question is a basic sorting and indexing task. You are given an array of integers and a target value. You need to determine what the indices of the target value would be if the array were sorted in non-decreasing order. You should return a list of all such indices.

Why is this asked in interviews?

Companies like Meta and Amazon use the Find Target Indices After Sorting Array coding problem as an introductory question. It tests your basic understanding of array manipulation, sorting, and linear vs. logarithmic time complexity. While sorting is the obvious path, interviewers often look for a more optimized $O(N)$ approach that doesn't actually require a full sort.

Algorithmic pattern used

There are two main patterns:

1. Sorting + Linear Scan: Sort the array ($O(N \log N)$) and then iterate to find the target.
2. Counting (Optimized): Iterate through the array once ($O(N)$). Count how many numbers are strictly smaller than the target (this tells you where the first target will be) and count how many times the target itself appears. The result is a sequence starting from smallerCount up to smallerCount + targetCount - 1.

Example explanation

Array: [1, 2, 5, 2, 3], Target: 2.

• Sorting path: Sorted array is [1, 2, 2, 3, 5]. Indices of '2' are 1 and 2.
• Counting path:
• Numbers < 2: [1] (Count = 1).
• Numbers = 2: [2, 2] (Count = 2).
• Starting index: 1. Target indices: [1, 2].

Common mistakes candidates make

• Ignoring Duplicates: Only returning the first index of the target.
• Inefficiency: Automatically choosing sorting without considering the $O(N)$ counting approach.
• Wrong return type: Returning values instead of the sorted indices.

Interview preparation tip

Always look for ways to avoid sorting if you only need properties related to a single value or rank. Counting is a powerful Array interview pattern that often beats sorting in both time and space complexity.