Find Target Indices After Sorting Array

EASY

Description

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

Approaches

Checkout 2 different approaches to solve Find Target Indices After Sorting Array. Click on different approaches to view the approach and algorithm in detail.

Brute Force: Sort and Scan

This approach directly follows the problem statement. First, we sort the input array nums in non-decreasing order. Then, we iterate through the sorted array to find all indices where the element is equal to the target and add these indices to a result list.

Algorithm

Create an empty list, result, to store the target indices.
Sort the input array nums in non-decreasing order.
Iterate through the sorted nums array with an index i from 0 to nums.length - 1.
Inside the loop, if nums[i] is equal to target, add the index i to the result list.
After the loop finishes, return the result list.

The algorithm consists of two main steps:

Sorting: We use a standard library function, like Arrays.sort() in Java, to sort the input array nums. This operation has a time complexity of O(N log N), where N is the number of elements in the array.
Scanning: After sorting, we perform a linear scan through the array from index 0 to N-1. During the scan, we check if the element at the current index i is equal to the target. If nums[i] == target, we add the index i to our result list. Since we are iterating in increasing order of indices, the resulting list of indices will also be sorted.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public List<Integer> targetIndices(int[] nums, int target) {
        // Step 1: Sort the array
        Arrays.sort(nums);
        
        List<Integer> result = new ArrayList<>();
        
        // Step 2: Scan the sorted array to find target indices
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target) {
                result.add(i);
            }
        }
        
        return result;
    }
}

Complexity Analysis

Time Complexity: O(N log N), where N is the number of elements in `nums`. The dominant operation is sorting the array. The subsequent linear scan takes O(N) time, which is overshadowed by the sorting time.Space Complexity: O(K) or O(N) in the worst case. The space required for the output list is O(K), where K is the number of occurrences of the target. In the worst case, all elements could be the target, making it O(N). Additionally, the sorting algorithm might use O(log N) to O(N) space, depending on the implementation.

Pros and Cons

Pros:

Simple and straightforward to understand and implement.
Directly translates the problem description into code.

Cons:

Not the most efficient solution due to the O(N log N) time complexity of sorting.

Code Solutions

Checking out 3 solutions in different languages for Find Target Indices After Sorting Array. Click on different languages to view the code.

Video Solution

Watch the video walkthrough for Find Target Indices After Sorting Array

Algorithms:

Binary SearchSorting

Data Structures:

Array

Companies:

TikTok |