algoadvance

Leetcode 2089. Find Target Indices After Sorting Array

Problem Statement

You are given a list of integers nums and an integer target. You need to return a list of indices of nums after sorting the nums array in non-decreasing order. These are the indices where the target number would appear in the sorted array.

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 the target is 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 the target is 3 is 3.

Clarifying Questions

  1. Can nums contain negative numbers?
    • Yes, nums can contain negative numbers.
  2. Can the array be empty?
    • Yes, the array can be empty, in which case the result should be an empty list.
  3. Can there be multiple occurrences of target in nums?
    • Yes, part of the problem is to handle multiple occurrences.

Strategy

  1. Sort the nums array: Sorting will help to directly find the indices of the target values in a straightforward manner.
  2. Iterate through the sorted array: Identify and collect the indices where the target matches the value in the array.
  3. Store the indices in the list and return that list as the result.

Code

Here’s a Java implementation:

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

public class TargetIndices {
    public static List<Integer> targetIndices(int[] nums, int target) {
        List<Integer> result = new ArrayList<>();
        
        // Sort the array
        Arrays.sort(nums);
        
        // Iterate through the sorted array and collect the target indices
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target) {
                result.add(i);
            }
        }
        
        return result;
    }

    public static void main(String[] args) {
        int[] nums1 = {1, 2, 5, 2, 3};
        int target1 = 2;
        System.out.println(targetIndices(nums1, target1)); // Output: [1, 2]

        int[] nums2 = {1, 2, 5, 2, 3};
        int target2 = 3;
        System.out.println(targetIndices(nums2, target2)); // Output: [3]
    }
}

Time Complexity

  1. Sorting: The time complexity of sorting the array is O(n log n), where n is the number of elements in nums.
  2. Iterating through the array: This operation takes O(n).

Combining these, the overall time complexity is O(n log n), dominated by the sorting step.

Summary

The provided solution sorts the input array and then checks the sorted array to find and collect indices of the target element. This approach ensures clarity and adherence to the requirement of locating the indices in a sorted array while maintaining an efficient time complexity.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI