#2089

Easy

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Find Target Indices After Sorting Array

Find the target indices of a sorted array and return them in increasing order using binary search and sorting techniques.

array binary search sorting

Problem Statement

You are given a 0-indexed integer array nums and a target element target. Your task is to find all the indices in nums where the value is equal to the target after sorting the array in non-decreasing order.

Return the list of target indices sorted in increasing order. If no target indices are found, return an empty list. The array must be sorted first before applying binary search or other methods for finding target positions.

Examples

Example 1

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

Output: [1,2]

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]

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]

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

Solution Approach

Sort the Array

Begin by sorting the given array nums in non-decreasing order. This ensures that the target indices will appear consecutively, allowing us to effectively locate the target element.

Binary Search for the Target

Once the array is sorted, use binary search to find the leftmost and rightmost occurrences of the target. This will help efficiently identify all target indices in the sorted array.

Return Sorted Indices

After determining the target indices, return them in increasing order as required by the problem statement. If no indices are found, return an empty list.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Sorting the array takes O(n log n) time, where n is the length of the array. Binary search takes O(log n) time to locate the first and last occurrences of the target. Overall, the time complexity is dominated by the sorting step, i.e., O(n log n). The space complexity depends on the sorting algorithm used, but it's generally O(n) for most sorting algorithms.

What Interviewers Usually Probe

Check if the candidate understands binary search and how it can be applied to find the target indices efficiently after sorting.
Evaluate if the candidate considers edge cases like no target in the array or all elements being the target.
Observe whether the candidate can justify their choice of sorting and binary search as a solution pattern.

Common Pitfalls or Variants

Common pitfalls

Overlooking the requirement to sort the array first before applying binary search can lead to incorrect results.
Failing to handle edge cases, such as when the target element is not present in the array, or when all elements are the target.
Not returning the indices in the correct order or leaving out some of the indices if there are multiple occurrences of the target.

Follow-up variants

Modify the problem to handle a larger array or larger range of target values to test efficiency and edge case handling.
Extend the problem to allow for reverse sorting of the array, and adjust the approach for finding the target indices accordingly.
Introduce a variant where you need to find the indices of multiple target values instead of a single target.

FAQ

What is the best approach to solve the 'Find Target Indices After Sorting Array' problem?

The best approach involves sorting the array and then using binary search to efficiently find the target indices.

How does binary search help in finding target indices?

Binary search allows you to quickly locate the first and last occurrences of the target in a sorted array, improving search efficiency.

Why do we need to sort the array before finding the target indices?

Sorting ensures that the target indices are consecutive, making it easier to locate and return them in increasing order.

What is the time complexity of this solution?

The time complexity is O(n log n) due to the sorting step, with binary search contributing O(log n) for target index identification.

Can GhostInterview help with solving the 'Find Target Indices After Sorting Array' problem?

Yes, GhostInterview provides step-by-step guidance, helping you understand how to apply binary search and sorting to efficiently find the target indices.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

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

Continue Practicing

#2071 maximum number of tasks you can assign #2070 most beautiful item for each query #2054 two best non overlapping events