algoadvance

You are given a 0-indexed integer array nums and an integer target.

You need to determine the indices of the array where the value equals the target after sorting the array in non-decreasing order. Return these indices in the form of a list. If there are no such indices, return an empty list.

Clarifying Questions

  1. Input constraints: What are the constraints on the size of the array and the values of its elements?
    • nums can have length [1, 100].
    • Each element in nums is an integer within the range [1, 100].
  2. Output format: Should the returned list be sorted?
    • Yes, since the array is sorted before determining the indices, the indices in the result will naturally be in ascending order.
  3. Edge cases: What if the target is not present in the array at all?
    • The function should return an empty list.

Strategy

  1. Sort the Array: First, sort the array in non-decreasing order.
  2. Find Indices: Iterate through the sorted array and collect the indices of the elements that match the target value.

Code

Let’s write the Python function to achieve this:

def targetIndices(nums, target):
    # Step 1: Sort the array
    nums.sort()

    # Step 2: Find the indices of the target value
    result = []
    for i, num in enumerate(nums):
        if num == target:
            result.append(i)
    
    return result

Time Complexity

  1. Sorting the array: Sorting takes O(n log n) time, where n is the number of elements in nums.
  2. Finding indices: Traversing the sorted array takes O(n) time.

Thus, the total time complexity of the solution is O(n log n).

Example

Let’s test the function with an example:

nums = [1, 2, 5, 2, 3]
target = 2
print(targetIndices(nums, target))  # Output should be [1, 2]

This example assumes the sorted array is [1, 2, 2, 3, 5], and the target value 2 appears at indices 1 and 2.

Try our interview co-pilot at AlgoAdvance.com