2089. Find Target Indices After Sorting Array

EasyArrayBinary SearchSorting
Leetcode Link

Problem Description

In this problem, we are given an array of integers called nums and another integer called target. Our task is to find all the indices in the array where the element is equal to the target, after sorting the array in non-decreasing order (from smallest to largest values). The "target indices" are the positions in the sorted array where the target is found. We're required to return these indices as a list, which should also be sorted in increasing order. If the target is not present in the array, we should return an empty list.

Intuition

To solve this problem, the intuitive approach is straightforward:

  1. Sort the array in non-decreasing order so that any duplicates of target will be positioned next to each other.

  2. Iterate through the sorted array and for each element that is equal to target, record its index.

By doing these steps, we ensure that we're considering the elements in the sorted order and collecting the indices of the target. Since we are sorting the array first, the indices that we collect will already be sorted. Thus, the resulting list of indices satisfies the problem's requirements without needing further sorting.

The Python solution provided leverages list comprehension, which is a concise way to iterate over the sorted array and construct the list of target indices in one go.

Learn more about Binary Search and Sorting patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which of the following uses divide and conquer strategy?

Solution Approach

The implementation of the solution follows a simple algorithm that involves sorting and then iterating through the array. The two main components of the implementation are the sorting algorithm and the enumeration pattern, which are both native to Python.

Here's the breakdown of the solution approach:

  1. nums.sort(): The sort() method is called on the nums array. In Python, this method uses a TimSort algorithm, which is a hybrid sorting algorithm derived from merge sort and insertion sort. It has a time complexity of O(n log n) on average, where n is the number of elements in the array. This step rearranges the elements of nums in-place in a non-decreasing order.

  2. [i for i, v in enumerate(nums) if v == target]: This is a list comprehension that creates a new list. The enumerate(nums) function is used to get both the index (i) and the value (v) of each element in the sorted nums array. The if v == target part is a condition that filters out all the elements that are not equal to the target. Only the indices of the elements that match the target are included in the final list.

The algorithm's space complexity is O(1) for the sorting (since it sorts in-place), and the space complexity for the list comprehension is O(k), where k is the number of times the target appears in nums since it creates a new list that contains all the target indices.

Overall, the solution is efficient and leverages Python's built-in functions to achieve the desired result with concise and readable code.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27
1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30
1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

Example Walkthrough

Let's go through an example to illustrate the solution approach.

Suppose we have an array of integers nums = [4, 1, 2, 1, 3, 2] and the target integer target = 2. We want to find all indices of target in the sorted array.

Here is how we apply the solution approach step-by-step:

  1. Sort the Array:

    We first sort the array in non-decreasing order. Applying nums.sort() will modify our nums array to [1, 1, 2, 2, 3, 4].

  2. Find Target Indices:

    We then use list comprehension to find all indices where the value is equal to target. For our sorted array, it would look like this:

    [i for i, v in enumerate([1, 1, 2, 2, 3, 4]) if v == 2]

    Here, enumerate() function gives us pairs of indices and their corresponding values. We only want the indices where the value v is equal to our target, which is 2.

  3. Filtering:

    As we iterate, we check each value v:

    • At index 0, v is 1, which is not equal to 2.
    • At index 1, v is 1, which is also not equal to 2.
    • At index 2, v is 2, which is equal to 2. We add 2 to our list.
    • At index 3, v is 2, which is again equal to 2. We add 3 to our list.
    • The last two values at indices 4 and 5 are 3 and 4, neither of which matches our target.

  4. Final Result:

    The resulting list of target indices after applying the filter is [2, 3], which are the sorted indices in the original sorted nums array where the target value 2 is located.

Thus, if we call our function with the above nums and target, we will get [2, 3] as the output because these are the positions in the sorted array where 2 is found.

Solution Implementation

1class Solution:
2    def target_indices(self, numbers: List[int], target: int) -> List[int]:
3        # Sort the list of numbers in place
4        numbers.sort()
5      
6        # Use list comprehension to find all indices where the value equals the target
7        # This loop iterates over each index and value in the sorted list of numbers
8        target_indices_list = [index for index, value in enumerate(numbers) if value == target]
9      
10        return target_indices_list
11
1class Solution {
2    public List<Integer> targetIndices(int[] nums, int target) {
3        // Sort the array in non-decreasing order
4        Arrays.sort(nums);
5      
6        // Initialize an empty list to hold the indices of the target
7        List<Integer> targetIndicesList = new ArrayList<>();
8      
9        // Loop through the sorted array
10        for (int index = 0; index < nums.length; index++) {
11            // If the current element is equal to the target...
12            if (nums[index] == target) {
13                // ...then add its index to the list
14                targetIndicesList.add(index);
15            }
16        }
17      
18        // Return the list of indices where the target is found
19        return targetIndicesList;
20    }
21}
22
1#include <vector>
2#include <algorithm>
3
4class Solution {
5public:
6    // Function to find all indices of 'target' in a sorted vector 'nums'.
7    std::vector<int> targetIndices(std::vector<int>& nums, int target) {
8        // First, sort the given vector.
9        std::sort(nums.begin(), nums.end());
10
11        // Declare a vector to store the indices where 'target' is found.
12        std::vector<int> result_indices;
13
14        // Iterate through the sorted vector to find all occurrences of 'target'.
15        for (int index = 0; index < nums.size(); ++index) {
16            // If the current element equals 'target', add its index to the result.
17            if (nums[index] == target) {
18                result_indices.push_back(index);
19            }
20        }
21
22        // Return the vector containing all indices of 'target'.
23        return result_indices;
24    }
25};
26
1// Function to find all indices at which a given target number appears
2// after sorting the array in ascending order.
3function targetIndices(nums: number[], target: number): number[] {
4    // Sort the array in ascending order.
5    nums.sort((a, b) => a - b);
6
7    // Initialize an array to store the indices where target is found.
8    let resultIndices: number[] = [];
9
10    // Iterate over the sorted array to find all occurrences of target.
11    for (let index = 0; index < nums.length; index++) {
12        // Check if the current element is equal to the target.
13        if (nums[index] === target) {
14            // If it is, add the current index to the resultIndices array.
15            resultIndices.push(index);
16        }
17    }
18
19    // Return the array of indices where target is found.
20    return resultIndices;
21}
22
Not Sure What to Study? Take the 2-min Quiz：

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?

Time and Space Complexity

Time Complexity

The time complexity of the provided code primarily comes from the sort method which has a time complexity of O(n log n) where n is the length of the nums list. After sorting, the code iterates through the list to find indices of elements equal to the target with a time complexity of O(n). Therefore, the total time complexity is O(n log n) + O(n), which simplifies to O(n log n) since n log n dominates for larger values of n.

Space Complexity

The space complexity of the code is O(1) if we use the sorting algorithm that sorts the input list in place, such as Timsort (which Python's sort method uses). No additional space is required proportional to the input size other than the space for the output list. The list comprehension for the indices generates the output list, so its space is necessary for the result and doesn't count towards auxiliary space complexity.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

How many times is a tree node visited in a depth first search?

Recommended Readings

Binary Search Speedrun

Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at

Sorting Summary

Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫