Problem Statement

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

1. First, sort the array in non-decreasing order.
2. Then, find all the indices where nums[index] == target in the sorted array.
3. Return these indices in increasing order as a list.

If the target does not exist in the array, return an empty list.

Examples

Example 1:

Input: nums = [1, 2, 5, 2, 3], target = 2
Output: [1, 2]

Explanation: After sorting, nums becomes [1, 2, 2, 3, 5]
The target 2 appears at indices 1 and 2.

Example 2:

Input: nums = [1, 2, 5, 2, 3], target = 3
Output: [3]

Explanation: After sorting, nums becomes [1, 2, 2, 3, 5]
The target 3 appears at index 3.

Example 3:

Input: nums = [1, 2, 5, 2, 3], target = 4
Output: []

Explanation: After sorting, nums becomes [1, 2, 2, 3, 5]
The target 4 does not exist in the array, so the output is an empty list.

Different Approaches

1️⃣ Binary Search

Intuition:

The problem requires finding all indices of a target value in an array after sorting it in non-decreasing order. Sorting the array groups all occurrences of the target together, making it easy to identify the indices of the target. By leveraging binary search (lower and upper bounds), we can efficiently find the range of indices where the target appears.

Approach:

1. Sort the Array:
   • Sort the array in non-decreasing order to group all occurrences of the target together.
2. Find Range of Target:
   • Use binary search:
     • Lower Bound: Find the smallest index where the target appears (nums[index] >= target).
     • Upper Bound: Find the first index after the target stops appearing (nums[index] > target).
3. Collect Indices:
   • Use the range [lower bound, upper bound - 1] to collect all indices where the target occurs.
4. Edge Case:
   • If the target does not appear, the lower bound and upper bound will overlap, resulting in an empty list.

Code:

#include <vector>
#include <algorithm> // For sort
using namespace std;

class Solution {
public:
    vector<int> targetIndices(vector<int>& nums, int target) {
        // Step 1: Sort the array
        sort(nums.begin(), nums.end());
        
        // Step 2: Find the lower and upper bounds for the target
        int low = lower_bound(nums.begin(), nums.end(), target) - nums.begin(); // First occurrence
        int high = upper_bound(nums.begin(), nums.end(), target) - nums.begin(); // First index after last occurrence
        
        // Step 3: Collect indices within the range [low, high)
        vector<int> result;
        for (int i = low; i < high; ++i) {
            result.push_back(i);
        }
        
        return result;
    }
};

OR:

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    vector<int> targetIndices(vector<int>& nums, int target) {
        // Step 1: Sort the array
        sort(nums.begin(), nums.end());
        
        // Step 2: Find the lower bound
        int low = 0, high = nums.size() - 1;
        int lowerBound = -1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (nums[mid] >= target) {
                // Potential lower bound, go left
                high = mid - 1;
            } else {
                // Go right
                low = mid + 1;
            }
        }
        lowerBound = low;  // Final `low` is the lower bound
        
        // Step 3: Find the upper bound
        low = 0, high = nums.size() - 1;
        int upperBound = -1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (nums[mid] > target) {
                // Potential upper bound, go left
                high = mid - 1;
            } else {
                // Go right
                low = mid + 1;
            }
        }
        upperBound = low;  // Final `low` is the upper bound
        
        // Step 4: Collect indices
        vector<int> result;
        for (int i = lowerBound; i < upperBound; i++) {
            result.push_back(i);
        }
        return result;
    }
};

Complexity Analysis:

• Time Complexity: O(n log n + n) = O(n log n)
  • Sorting the array takes O(n log n), where n is the size of the array.
  • Finding the lower and upper bounds takes O(log n) each, using binary search.
  • Collecting the indices (if k is the number of occurrences of the target) takes O(k)
  • Overall: O(n log n + k)
  • Worst-case for k = n: O(n log n + n) = O(n log n)
• Space Complexity: O(k)
  • The result vector requires O(k) space for storing the indices.