Jobs

Interviews

Discussions

Find Target Indices After Sorting Array

Easy

Asked by:

13 views

Topics:

Arrays

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

Try coding it in LeetCode

Find Target Indices After Sorting Array

Easy

Asked by:

13 views

Topics:

Arrays

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.

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

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values that can be present in the input array?
Can the input array contain duplicate numbers, and if so, should the output list include all indices where the target value appears?
Is the target value guaranteed to be present in the array, and what should I return if the target is not found?
What is the expected data type of the input array elements and the target value (e.g., integers, floats)?
Are there any specific constraints on the size of the input array?

Brute Force Solution

Approach

The basic idea is to rearrange the numbers from smallest to biggest. Afterward, we need to identify the positions where a specific number appears. This can be done by looking at each position one by one.

Here's how the algorithm would work step-by-step:

First, rearrange the entire set of numbers so that they are in order from smallest to largest.
Then, look at each position in the rearranged set of numbers, one at a time, starting from the beginning.
At each position, check if the number at that position is the specific number we are searching for.
If it is the number we are searching for, then we remember this position.
Continue looking at each position until we have checked every position in the set of numbers.
Finally, we will have a list of all the positions where the specific number appears.

Code Implementation

def find_target_indices_brute_force(numbers, target):
    sorted_numbers = sorted(numbers)
    target_indices = []

    # Iterate through the sorted array to find target indices
    for index in range(len(sorted_numbers)):

        # Check if the number at the current index is the target
        if sorted_numbers[index] == target:

            # Append the index to the result if it matches
            target_indices.append(index)

    return target_indices

Big(O) Analysis

Time Complexity

O(n log n) – The primary cost driver of this algorithm is the sorting step, which typically employs an efficient algorithm like merge sort or quicksort. These algorithms have a time complexity of O(n log n), where n is the number of elements in the input array. The subsequent iteration to find target indices takes O(n) time, as it involves checking each element once. Since O(n log n) dominates O(n), the overall time complexity is O(n log n).

Space Complexity

O(1) – The provided solution involves sorting the array in-place and then iterating through it. It only stores the indices of the target values in a list. Since the sorting is done in-place, it does not require auxiliary space proportional to the input size (N). The list to store the indices, in the worst case, can have a size of N, but since in-place sorting is expected, we do not take that into account. Therefore, the dominant space usage is constant, regardless of the input array's size (N).

Optimal Solution

Approach

The best way to solve this is not to sort the whole collection. Instead, we only need to count how many numbers are smaller than our target and how many are equal to it. This gives us all the information needed to figure out where the target numbers would be located after sorting, without actually doing the sort.

Here's how the algorithm would work step-by-step:

Count how many numbers in the collection are smaller than the number we're looking for.
Count how many numbers are equal to the number we're looking for.
The numbers smaller than our target tell us the starting location where our target would be after sorting.
The count of numbers equal to our target tells us how many consecutive slots our target would occupy after sorting.
With the starting location and the count, we know the exact locations where our target numbers would be found in the sorted collection, which is our final answer.

Code Implementation

def find_target_indices(numbers, target):    smaller_count = 0
    equal_count = 0

    for number in numbers:
        if number < target:
            smaller_count += 1
        elif number == target:
            equal_count += 1

    # Starting index is the number of elements smaller than the target.
    start_index = smaller_count

    # Determine the end index based on the count of equal numbers.
    end_index = start_index + equal_count

    target_indices = []
    # Populate the result with the range of indices.
    for index in range(start_index, end_index):
        target_indices.append(index)

    return target_indices

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input array of size n twice. The first pass counts the number of elements smaller than the target. The second pass counts the number of elements equal to the target. Both loops are independent and iterate through the entire array once. Therefore, the total number of operations is proportional to 2n, which simplifies to O(n).

Space Complexity

O(1) – The algorithm uses a constant amount of extra space. It only stores two integer variables, one for counting numbers smaller than the target and another for counting numbers equal to the target. The space required does not scale with the input array size N, hence the space complexity is O(1).

Edge Cases

Case	How to Handle
Null or empty input array	Return an empty list immediately as there are no indices to find.
Input array with only one element	Compare the single element to the target and return [0] if it matches, or [] if it doesn't.
Target is smaller than all elements in the array	The sorted array will have all elements larger than the target, so the algorithm should return an empty list.
Target is larger than all elements in the array	The sorted array will not contain the target, and the algorithm should return an empty list.
Array contains duplicate target values	The algorithm should correctly identify and return all indices where the target value is located in the sorted array.
Array contains only identical values, and the target is that value	The algorithm should return all indices in the array.
Large input array with potential integer overflow during sorting index calculations (if using indices)	Use data types that can handle large indices, or use a counting sort approach to avoid index-based comparisons during sorting.
Integer overflow if target is close to max or min int	Ensure the comparison `nums[i] == target` doesn't result in an overflow, especially if the target is derived from computations involving array elements.

Null or empty input array

How to Handle:

Return an empty list immediately as there are no indices to find.

Input array with only one element

How to Handle:

Compare the single element to the target and return [0] if it matches, or [] if it doesn't.

Target is smaller than all elements in the array

How to Handle:

The sorted array will have all elements larger than the target, so the algorithm should return an empty list.

Target is larger than all elements in the array

How to Handle:

The sorted array will not contain the target, and the algorithm should return an empty list.

Array contains duplicate target values

How to Handle:

The algorithm should correctly identify and return all indices where the target value is located in the sorted array.

Array contains only identical values, and the target is that value

How to Handle:

The algorithm should return all indices in the array.

Large input array with potential integer overflow during sorting index calculations (if using indices)

How to Handle:

Use data types that can handle large indices, or use a counting sort approach to avoid index-based comparisons during sorting.

Integer overflow if target is close to max or min int

How to Handle:

Ensure the comparison `nums[i] == target` doesn't result in an overflow, especially if the target is derived from computations involving array elements.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values that can be present in the input array?
Can the input array contain duplicate numbers, and if so, should the output list include all indices where the target value appears?
Is the target value guaranteed to be present in the array, and what should I return if the target is not found?
What is the expected data type of the input array elements and the target value (e.g., integers, floats)?
Are there any specific constraints on the size of the input array?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, rearrange the entire set of numbers so that they are in order from smallest to largest.
Then, look at each position in the rearranged set of numbers, one at a time, starting from the beginning.
At each position, check if the number at that position is the specific number we are searching for.
If it is the number we are searching for, then we remember this position.
Continue looking at each position until we have checked every position in the set of numbers.
Finally, we will have a list of all the positions where the specific number appears.

Code Implementation

def find_target_indices_brute_force(numbers, target):
    sorted_numbers = sorted(numbers)
    target_indices = []

    # Iterate through the sorted array to find target indices
    for index in range(len(sorted_numbers)):

        # Check if the number at the current index is the target
        if sorted_numbers[index] == target:

            # Append the index to the result if it matches
            target_indices.append(index)

    return target_indices

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Count how many numbers in the collection are smaller than the number we're looking for.
Count how many numbers are equal to the number we're looking for.
The numbers smaller than our target tell us the starting location where our target would be after sorting.
The count of numbers equal to our target tells us how many consecutive slots our target would occupy after sorting.
With the starting location and the count, we know the exact locations where our target numbers would be found in the sorted collection, which is our final answer.

Code Implementation

def find_target_indices(numbers, target):    smaller_count = 0
    equal_count = 0

    for number in numbers:
        if number < target:
            smaller_count += 1
        elif number == target:
            equal_count += 1

    # Starting index is the number of elements smaller than the target.
    start_index = smaller_count

    # Determine the end index based on the count of equal numbers.
    end_index = start_index + equal_count

    target_indices = []
    # Populate the result with the range of indices.
    for index in range(start_index, end_index):
        target_indices.append(index)

    return target_indices

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input array	Return an empty list immediately as there are no indices to find.
Input array with only one element	Compare the single element to the target and return [0] if it matches, or [] if it doesn't.
Target is smaller than all elements in the array	The sorted array will have all elements larger than the target, so the algorithm should return an empty list.
Target is larger than all elements in the array	The sorted array will not contain the target, and the algorithm should return an empty list.
Array contains duplicate target values	The algorithm should correctly identify and return all indices where the target value is located in the sorted array.
Array contains only identical values, and the target is that value	The algorithm should return all indices in the array.
Large input array with potential integer overflow during sorting index calculations (if using indices)	Use data types that can handle large indices, or use a counting sort approach to avoid index-based comparisons during sorting.
Integer overflow if target is close to max or min int	Ensure the comparison `nums[i] == target` doesn't result in an overflow, especially if the target is derived from computations involving array elements.

Null or empty input array

How to Handle:

Return an empty list immediately as there are no indices to find.

Input array with only one element

How to Handle:

Compare the single element to the target and return [0] if it matches, or [] if it doesn't.

Target is smaller than all elements in the array

How to Handle:

The sorted array will have all elements larger than the target, so the algorithm should return an empty list.

Target is larger than all elements in the array

How to Handle:

The sorted array will not contain the target, and the algorithm should return an empty list.

Array contains duplicate target values

How to Handle:

The algorithm should correctly identify and return all indices where the target value is located in the sorted array.

Array contains only identical values, and the target is that value

How to Handle:

The algorithm should return all indices in the array.

Large input array with potential integer overflow during sorting index calculations (if using indices)

How to Handle:

Use data types that can handle large indices, or use a counting sort approach to avoid index-based comparisons during sorting.

Integer overflow if target is close to max or min int

How to Handle:

Ensure the comparison `nums[i] == target` doesn't result in an overflow, especially if the target is derived from computations involving array elements.