Find Target Indices After Sorting Array - Practice Coding Problems

Find Target Indices After Sorting Array - 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.

Input & Output

Example 1 — Basic Case

$ Input: nums = [1,2,5,2,3], target = 2

› Output: [1,2]

💡 Note: After sorting: [1,2,2,3,5]. Target 2 appears at indices 1 and 2.

Example 2 — No Target Found

$ Input: nums = [1,2,5,2,3], target = 4

› Output: []

💡 Note: After sorting: [1,2,2,3,5]. Target 4 is not found, so return empty list.

Example 3 — Single Element

$ Input: nums = [1], target = 1

› Output: [0]

💡 Note: Array has one element which matches target, so return [0].

Constraints

1 ≤ nums.length ≤ 100
-100 ≤ nums[i] ≤ 100
-100 ≤ target ≤ 100

Visualization

Tap to expand

Understanding the Visualization

Input

Unsorted array and target value

Process

Sort array and find target positions

Output

List of indices where target appears

Key Takeaway

🎯 Key Insight: We can calculate target positions without sorting by counting smaller and equal elements

Asked in

a Amazon 15 M Microsoft 12 G Google 8

The key insight is that we don't need to actually sort the array - we just need to count how many elements are smaller than the target and how many equal the target. The target indices in a sorted array would be consecutive positions starting from the count of smaller elements. Best approach is the count-based method. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Count-Based Approach	O(n)	O(1)	Count elements smaller than and equal to target to calculate positions
Sort and Search	O(n log n)	O(1)	Sort the array then find all positions where target appears

Count-Based Approach — Algorithm Steps

Count elements smaller than target
Count elements equal to target
Generate consecutive indices starting from smaller_count

Visualization

Tap to expand

Step-by-Step Walkthrough

Count Elements

Count smaller and equal elements

Calculate Positions

Target positions start from smaller_count

Result

Generate consecutive indices

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int* solution(int* nums, int numsSize, int target, int* returnSize) {
    int smallerCount = 0;
    int targetCount = 0;
    
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] < target) {
            smallerCount++;
        } else if (nums[i] == target) {
            targetCount++;
        }
    }
    
    int* result = (int*)malloc(targetCount * sizeof(int));
    *returnSize = targetCount;
    
    for (int i = 0; i < targetCount; i++) {
        result[i] = smallerCount + i;
    }
    
    return result;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int nums[1000];
    int numsSize = 0;
    char *token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int target;
    scanf("%d", &target);
    
    int returnSize;
    int* result = solution(nums, numsSize, target, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass to count elements, then generate result array

✓ Linear Growth

Space Complexity

O(1)

Only using constant extra space (not counting output array)

✓ Linear Space

28.5K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Count-Based Approach — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler