Find Target Indices After Sorting Array

Difficulty: Easy | Acceptance: 78.00% | Paid: No Topics: Array, Binary Search, Sorting

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 after sorting the array in non-decreasing order.

Return a list of the target indices of nums after sorting nums in non-decreasing order. You can return the answer in any order.

• Examples
• Constraints
• Sorting and Linear Scan
• Counting Approach
• Binary Search on Sorted Array

Examples

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.

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.

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] <= 100
1 <= target <= 100

Sorting and Linear Scan

Intuition Sort the array first, then iterate through it to collect all indices where the value equals target.

Steps

• Sort the array in non-decreasing order
• Iterate through the sorted array
• For each element equal to target, add its index to the result list

class Solution:
    def targetIndices(self, nums: List[int], target: int) -> List[int]:
        nums.sort()
        result = []
        for i, num in enumerate(nums):
            if num == target:
                result.append(i)
        return result

Complexity

• Time: O(n log n)
• Space: O(1) or O(n) depending on sorting algorithm
• Notes: Simple and intuitive, but not the most efficient

Counting Approach

Intuition Count elements less than target and elements equal to target. The indices will be from count_less to count_less + count_equal - 1.

Steps

• Count how many elements are less than target
• Count how many elements equal to target
• Generate indices from count_less to count_less + count_equal - 1

class Solution:
    def targetIndices(self, nums: List[int], target: int) -> List[int]:
        less = 0
        equal = 0
        for num in nums:
            if num < target:
                less += 1
            elif num == target:
                equal += 1
        return list(range(less, less + equal))

Complexity

• Time: O(n)
• Space: O(1) excluding output
• Notes: Optimal solution - avoids sorting entirely

Binary Search on Sorted Array

Intuition Sort the array and use binary search to find the first and last occurrence of target, then generate all indices between them.

Steps

• Sort the array
• Use binary search to find the first occurrence of target
• Use binary search to find the last occurrence of target
• Generate all indices from first to last

class Solution:
    def targetIndices(self, nums: List[int], target: int) -> List[int]:
        nums.sort()
        
        def findFirst():
            left, right = 0, len(nums)
            while left < right:
                mid = (left + right) // 2
                if nums[mid] < target:
                    left = mid + 1
                else:
                    right = mid
            return left if left < len(nums) and nums[left] == target else -1
        
        def findLast():
            left, right = 0, len(nums)
            while left < right:
                mid = (left + right) // 2
                if nums[mid] <= target:
                    left = mid + 1
                else:
                    right = mid
            return left - 1 if left > 0 and nums[left - 1] == target else -1
        
        first = findFirst()
        if first == -1:
            return []
        last = findLast()
        return list(range(first, last + 1))

Complexity

• Time: O(n log n) for sorting + O(log n) for binary search = O(n log n)
• Space: O(1) or O(n) depending on sorting algorithm
• Notes: More efficient than linear scan after sorting, but still requires sorting