algoadvance

Leetcode 2089. Find Target Indices After Sorting Array

Problem Statement

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

You need to return the indices of the target in nums after sorting nums in non-decreasing order. If there are no target indices, return an empty array. The returned array must be sorted in increasing order.

Example

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 2 is present in nums 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 3 is present in nums 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 5 is present in nums is 4.

Clarifying Questions

  1. Q: What are the constraints on the array size and the values within the array?
    • A: 1 <= nums.length <= 100
    • A: 1 <= nums[i], target <= 100
  2. Q: Can the array contain duplicate values?
    • A: Yes, the array can contain duplicates.
  3. Q: Is there any specific requirement on the complexity of the solution?
    • A: Given the constraints, a simple solution leveraging sorting and iteration would be efficient.

Strategy

  1. Sort the array nums.
  2. Find the indices of the target value in the sorted array.
    • Iterate through the sorted array and collect indices where the elements match the target value.
  3. Return the collection of indices.

Code

#include <vector>
#include <algorithm>

std::vector<int> targetIndices(std::vector<int>& nums, int target) {
    std::vector<int> result;
    // Step 1: Sort the array in non-decreasing order
    std::sort(nums.begin(), nums.end());
    
    // Step 2: Iterate through the sorted array and collect indices where value equals target
    for (int i = 0; i < nums.size(); ++i) {
        if (nums[i] == target) {
            result.push_back(i);
        }
    }
    
    return result;
}

Time Complexity

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

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