Skip to main content

Binary Search

Find Target Indices After Sorting Array Solution In C++/Java/Python/JS

Problem Description:

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.
Illustration fo Find Target Indices After Sorting Array Problem Description

Examples:

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.

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.

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

Brute Force Approach

Intuition:

The problem is straightforward. You are given an array nums and an integer target. The task is to find the indices where the target appears after sorting the array in ascending order.

The result should be a list of these indices in increasing order. This problem is useful for understanding how sorting and searching work together in programming.

To do this, we can break the problem into two steps:

First, we will focus on sorting the array. First, we need to sort the given array nums in ascending order.

Most programming languages provide a built-in function to handle sorting, so we can use that to simplify the task.

Other than this, we can sort the array by ourselves using any algorithms like bubble sort, selection sort, insertion sort, merge sort, quick sort etc.

💡
Bubble Sort Algorithm !
💡
Insertion Sort Algorithm !
💡
Selection Sort Algorithm !
💡
Merge Sort Algorithm !
💡
Quick Sort Algorithm !

Second, we will find the target indices. After sorting, we need to search for the target value in the sorted array. We can do this by iterating through the array from index 0 to n-1 and storing only those indexes with values equal to the target.

Example:

Input:
nums = [4, 2, 2, 3, 4], target = 4

Step 1: After sorting → [2, 2, 3, 4, 4]
Step 2: Indices of 4 → 3, 4

Output: [3, 4]

Illustration of Find Target Indices After Sorting Array Brute Force Approach 1
Illustration of Find Target Indices After Sorting Array Brute Force Approach 2

Dry run

Input: [4, 3, 5, 3, 6, 3] target = 3
Output: [0, 1, 2]
Explanation: After sorting target will be at positions 0, 1, 3.

Initialization

  • The size of the array is calculated using nums.size() → n = 6.
  • An empty vector ans is declared to store the indices where the target value appears.

Sort the Array

  • The sort(nums.begin(), nums.end()) function sorts the array in ascending order.
  • Before sorting → [4, 3, 5, 3, 6, 3]
  • After sorting → [3, 3, 3, 4, 5, 6]

Start Loop

  • The loop starts at i = 0:
    • At i = 0, nums[0] = 3, which matches the target → Add index 0 to ans.
    • At i = 1, nums[1] = 3, which matches the target → Add index 1 to ans.
    • At i = 2, nums[2] = 3, which matches the target → Add index 2 to ans.
    • At i = 3, nums[3] = 4, which does not match the target → Skip.
    • At i = 4, nums[4] = 5, which does not match the target → Skip.
    • At i = 5, nums[5] = 6, which does not match the target → Skip.

Return Result

  • The result array ans = [0, 1, 2] is returned.

Steps to write code

Step 1: Initialization

  • Create a variable n to store the size of the array using nums.size().
  • Create an empty vector ans to store the target indices.

Step 2: Sort the Array

  • Use the built-in sort() function or manually sort the array using any of the sorting algorithms to sort the array in ascending order.

Step 3: Find Target Indices

  • Use a for loop to iterate through the array from i = 0 to i = n - 1.
  • Inside the loop:
    • If nums[i] == target, push the index i into the result array ans.

Step 4: Return Result

  • Return the result array ans containing the indices where the target value appears in sorted order.
Find Target Indices After Sorting Array Solution
Find Target Indices After Sorting Array Solution in C++ 
class Solution {
public:
    vector<int> targetIndices(vector<int>& nums, int target) {
        // Get the size of the array
        int n = nums.size();

        // Sort the array
        sort(nums.begin(), nums.end());

        // Store indices where nums[i] == target
        vector<int> ans;
        for(int i = 0; i < n; ++i) {
            if(nums[i] == target) ans.push_back(i);
        }
        return ans;
    }
};

Find Target Indices After Sorting Array Solution in Java 
class Solution {
    public List<Integer> targetIndices(int[] nums, int target) {
        // Sort the array
        Arrays.sort(nums);

        // Store indices where nums[i] == target
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target) ans.add(i);
        }
        return ans;
    }
}

Find Target Indices After Sorting Array Solution in Python 
class Solution:
    def targetIndices(self, nums, target):
        # Sort the array
        nums.sort()

        # Store indices where nums[i] == target
        ans = []
        for i in range(len(nums)):
            if nums[i] == target:
                ans.append(i)
        return ans

Find Target Indices After Sorting Array Solution in Javascript 
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var targetIndices = function(nums, target) {
    // Sort the array
    nums.sort((a, b) => a - b);

    // Store indices where nums[i] == target
    let ans = [];
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] === target) ans.push(i);
    }
    return ans;
};

Find Target Indices After Sorting Array Complexity Analysis

Time Complexity: O(nlogn)

Sorting Step:

  • The sort function sorts the array in ascending order.
  • Sorting complexity using built-in sort() (which typically uses quicksort, heapsort, or mergesort) is O(nlog⁡n).

Loop Step:

  • The loop runs through each element of the sorted array once.
  • Inside the loop, checking the condition nums[i] == target and adding to the result array both take constant time O(1).
  • Therefore, the total complexity for the loop is: O(n)

Total Time Complexity:

The total time complexity is the sum of sorting and looping O(nlog⁡n)+O(n)=O(nlog⁡n)

Since O(nlogn) dominates O(n), the overall time complexity is: O(nlog⁡n)

Space Complexity: O(n)

Auxiliary Space Complexity:

It refers to the extra space used by the algorithm, excluding the input data.

  • Sorting Step:
    • The sort() function may require extra space depending on the sorting algorithm used internally (e.g., quicksort is in-place, mergesort requires extra space).
    • In the worst case (for mergesort), it can require O(n)
  • Result Array:
    • The result array ans stores the indices where the target is found.
    • In the worst case, all elements in the array could match the target, leading to O(n)

Total auxiliary space is the sum of sorting space and result array space is O(n)

  1. Total Space Complexity:

It includes both the input data size and any additional space used during execution.

  • Since the input array nums is passed by reference and no extra space other than the result array and sorting buffer is used, the total space complexity is O(n)

Final overall space complexity is O(n)

Is the brute force approach efficient?

The time complexity of brute force approach is O(nlogn). Sorting the array gives the major contribution to this time complexity.

O(nlogn) very well fits in the constraints,in fact so the brute force approach infact is efficient.

But we can improve it further by making an observation. Let's look at that in the optimal approach.

Optimal Approach

Intuition:

To optimise the O(nlogn). We made a point that sorting gives a major contribution to the time complexity.

What if I tell you we can sort the numbers efficiently without using the custom inbuilt sort and the other O(n2) and O(nlogn) algorithms?

To sort the numbers in more efficient manner we will make use of the frequency array, which will store the count of the unique numbers in the nums array.

Now, imagine that we have a frequency array where we have stored the count of each unique number in the nums array.

The size of this array would be such that the maximum value of a number in the nums array should also find it's place in the frequency array.

That means the size of the frequency array must be 1 plus the maximum value in the nums array.

Now that we have the frequency array, we will take the prefix sum of it. This means now frequency array at any index will store the count of all the numbers that are less than or equal to i.

Example:

nums = [3, 2, 1, 6, 3]
freq = [0, 1, 1, 2, 0, 0, 1]
prefix of freq array = [0, 1, 2, 4, 4, 4, 5]

Now that we have the prefix sum of frequency, think of how we can use it to sort the array.

How can we use the prefix sum of the frequency array to sort the array?

To do this, we will iterate the nums from the end because traversing the input array from the end preserves the order of equal elements, which eventually makes this sorting algorithm stable.

For every value from the end of the nums array, we will look at the value in the prefix sum of the frequency array. That value will tell us the position it will hold in the sorted array.

From the previous example, we take sorted_nums = [0, 0, 0, 0, 0]

Find Target Indices After Sorting Array Algorithm

We will iterate from the end, so the first index will be index 4 (nums[4] = 3). We will look at the prefix sum of the freq array, which is prefix_freq[3] = 4.

This means the last occurrence of 3 will be placed at sorted_nums[4]. After doing this, we make prefix_freq[3] = 3 (reduce by 1). Because we place 1 occurrence of 3.

We will keep on doing this until we reach the index 0. Doing this we will get our sorted_nums filled up.

This method of sorting is called the counting sort algorithm. It is not commonly used because of a single drawback.

The algorithm is efficient when the maximum value of the array is small; in this case, it's just 100, so this will perform well then any other sorting algorithms for large n.

Hence, we can say that using counting sort is the best approach to solve this problem.

Counting sort in more detail :

💡
Counting Sort !

Then we will use the same approach as we used in the brute force approach to store only those indexes with sorted_nums[i] = target in some array answer.

Finally, we will return the answer array.

  • Find Target in Rotated Sorted Array: If the array is rotated at some pivot, we need a different approach (like binary search on rotated arrays) to find the target efficiently.
  • All Indices in an Array (LeetCode): Some problems require returning all occurrences of a value in an unsorted or sorted array.
  • Find Target Sum Elements in Array: If we need to find pairs or subsets that sum up to a target, we can use techniques like the two-pointer approach or dynamic programming.
0:00
/6:58

Animation of Find Target Indices After Sorting Array Optimal Approach

Dry run

Input: [4, 3, 5, 3, 6, 3] target = 3
Output: [0, 1, 2]
Explanation: After sorting target will be at positions 0, 1, 2.

Initialization

  • n = nums.size() = 6
  • ans = [] (empty vector to store target indices)
  • mx = 6 (maximum value in nums)

Frequency Array Calculation

  • freq array stores the count of occurrences of each number from 0 to mx. freq = [0, 0, 0, 3, 1, 1, 1]
    • 3 appears 3 times
    • 4 appears 1 time
    • 5 appears 1 time
    • 6 appears 1 time

Prefix Frequency Calculation

  • The array stores the cumulative sum of freq:
    prefix_freq = [0, 0, 0, 3, 4, 5, 6]
    • prefix_freq[i] tells how many elements are ≤ i in the original array.

Step 4: Sorting the Array Using Counting Sort

  • Step-by-step placement into sorted_nums using prefix_freq:
    Final sorted array: sorted_nums = [3, 3, 3, 4, 5, 6]
    1. Processing nums[5] = 3
      • Position: prefix_freq[3] - 1 = 2
      • Place 3 at sorted_nums[2]
      • Decrement prefix_freq[3]: [0, 0, 0, 2, 4, 5, 6]
    3. Processing nums[4] = 6
      • Position: prefix_freq[6] - 1 = 5
      • Place 6 at sorted_nums[5]
      • Decrement prefix_freq[6]: [0, 0, 0, 2, 4, 5, 5]
    5. Processing nums[3] = 3
      • Position: prefix_freq[3] - 1 = 1
      • Place 3 at sorted_nums[1]
      • Decrement prefix_freq[3]: [0, 0, 0, 1, 4, 5, 5]
    7. Processing nums[2] = 5
      • Position: prefix_freq[5] - 1 = 4
      • Place 5 at sorted_nums[4]
      • Decrement prefix_freq[5]: [0, 0, 0, 1, 4, 4, 5]
    9. Processing nums[1] = 3
      • Position: prefix_freq[3] - 1 = 0
      • Place 3 at sorted_nums[0]
      • Decrement prefix_freq[3]: [0, 0, 0, 0, 4, 4, 5]
    11. Processing nums[0] = 4
      • Position: prefix_freq[4] - 1 = 3
      • Place 4 at sorted_nums[3]
      • Decrement prefix_freq[4]: [0, 0, 0, 0, 3, 4, 5]

Step 5: Finding Target Indices

  • Iterate through sorted_nums and collect indices where sorted_nums[i] == target
  • target = 3 is found at indices 0, 1, 2
  • ans = [0, 1, 2]

Final Output: Output: [0, 1, 2]
Explanation: After sorting, target = 3 appears at indices 0, 1, 2 in sorted_nums.

Steps to write code

Step 1: Initialize Variables

  • Find the size of the array nums and store it in n.
  • Create an empty vector ans to store the target indices.
  • Determine the maximum element in nums (mx) to set the range for frequency counting.

Step 2: Build the Frequency Array

  • Create an array freq of size mx + 1 initialized with zeros.
  • Iterate through nums and update the count of each number in freq.

Step 3: Compute the Prefix Frequency Array

  • Create an array prefix_freq to store the cumulative sum of freq.
  • Iterate through freq, updating prefix_freq[i] to maintain the total count of numbers ≤ i.

Step 4: Sort the Array Using Counting Sort

  • Create an empty array sorted_nums of size n.
  • Iterate backward through nums, placing each element in its correct sorted position based on prefix_freq.
  • Decrement the corresponding prefix_freq value after placing an element.

Step 5: Find Target Indices

  • Iterate through sorted_nums.
  • If an element matches target, store its index in ans.

Step 6: Return the Result

  • Return the ans vector containing the indices of the target in the sorted array.
Find Target Indices After Sorting Array Leetcode Solution
Find Target Indices After Sorting Array Solution in C++ 
class Solution {
public:
    vector<int> targetIndices(vector<int>& nums, int target) {
        // Get the size of the array
        int n = nums.size();
        vector<int> ans;

        // Step 1: Find the maximum element in the array
        int mx = 0;
        for (int x : nums) mx = max(mx, x);

        // Step 2: Create a frequency array to store occurrences of each number
        vector<int> freq(mx + 1, 0);
        for (int i = 0; i < n; ++i) freq[nums[i]]++;

        // Step 3: Compute prefix sum of the frequency array
        vector<int> prefix_freq(mx + 1, 0);
        prefix_freq[0] = freq[0];
        for (int i = 1; i <= mx; ++i) {
            prefix_freq[i] = prefix_freq[i - 1] + freq[i];
        }

        // Step 4: Sort the array using counting sort logic
        vector<int> sorted_nums(n);
        for (int i = n - 1; i >= 0; --i) {
            sorted_nums[prefix_freq[nums[i]] - 1] = nums[i];
            prefix_freq[nums[i]]--;
        }

        // Step 5: Find the indices where the target appears
        for (int i = 0; i < n; ++i) {
            if (sorted_nums[i] == target) ans.push_back(i);
        }

        return ans;
    }
};

Find Target Indices After Sorting Array Solution in Java 
class Solution {
    public List<Integer> targetIndices(int[] nums, int target) {
        // Get the size of the array
        int n = nums.length;
        List<Integer> ans = new ArrayList<>();

        // Step 1: Find the maximum element in the array
        int mx = 0;
        for (int num : nums) mx = Math.max(mx, num);

        // Step 2: Create a frequency array to count occurrences of each number
        int[] freq = new int[mx + 1];
        for (int num : nums) freq[num]++;

        // Step 3: Compute the prefix sum of the frequency array
        int[] prefix_freq = new int[mx + 1];
        prefix_freq[0] = freq[0];
        for (int i = 1; i <= mx; i++) {
            prefix_freq[i] = prefix_freq[i - 1] + freq[i];
        }

        // Step 4: Sort the array using counting sort logic
        int[] sorted_nums = new int[n];
        for (int i = n - 1; i >= 0; i--) {
            sorted_nums[prefix_freq[nums[i]] - 1] = nums[i];
            prefix_freq[nums[i]]--;
        }

        // Step 5: Find the indices where the target appears
        for (int i = 0; i < n; i++) {
            if (sorted_nums[i] == target) ans.add(i);
        }

        return ans;
    }
}

Find Target Indices After Sorting Array Solution in Python 
class Solution:
    def targetIndices(self, nums: List[int], target: int) -> List[int]:
        # Get the size of the array
        n = len(nums)
        
        # Step 1: Find the maximum element in the array
        mx = max(nums)

        # Step 2: Create a frequency array to count occurrences of each number
        freq = [0] * (mx + 1)
        for num in nums:
            freq[num] += 1

        # Step 3: Compute prefix sum of the frequency array
        prefix_freq = [0] * (mx + 1)
        prefix_freq[0] = freq[0]
        for i in range(1, mx + 1):
            prefix_freq[i] = prefix_freq[i - 1] + freq[i]

        # Step 4: Sort the array using counting sort logic
        sorted_nums = [0] * n
        for i in range(n - 1, -1, -1):
            sorted_nums[prefix_freq[nums[i]] - 1] = nums[i]
            prefix_freq[nums[i]] -= 1

        # Step 5: Find the indices where the target appears
        ans = []
        for i in range(n):
            if sorted_nums[i] == target:
                ans.append(i)
        return ans

Find Target Indices After Sorting Array Solution in Javascript 
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var targetIndices = function(nums, target) {
    // Get the size of the array
    let n = nums.length;

    // Step 1: Find the maximum element in the array
    let mx = Math.max(...nums);

    // Step 2: Create a frequency array to count occurrences of each number
    let freq = new Array(mx + 1).fill(0);
    nums.forEach(num => freq[num]++);

    // Step 3: Compute prefix sum of the frequency array
    let prefix_freq = new Array(mx + 1).fill(0);
    prefix_freq[0] = freq[0];
    for (let i = 1; i <= mx; i++) {
        prefix_freq[i] = prefix_freq[i - 1] + freq[i];
    }

    // Step 4: Sort the array using counting sort logic
    let sorted_nums = new Array(n);
    for (let i = n - 1; i >= 0; i--) {
        sorted_nums[prefix_freq[nums[i]] - 1] = nums[i];
        prefix_freq[nums[i]]--;
    }

    // Step 5: Find the indices where the target appears
    let ans = [];
    for (let i = 0; i < n; i++) {
        if (sorted_nums[i] === target) ans.push(i);
    }

    return ans;
};

Find Target Indices After Sorting Array Complexity Analysis

Time Complexity: O(n + mx)

Finding Maximum Element (mx)

  • We iterate through nums once to determine the maximum element.
  • Time Complexity: O(n)

Building the Frequency Array

  • We iterate through nums again to count occurrences of each number.
  • Time Complexity: O(n)

Computing the Prefix Frequency Array

  • We iterate through the freq array, which has a size of mx + 1.
  • Time Complexity: O(mx)

Sorting the Array Using Counting Sort

  • We iterate backward through nums to place elements in sorted_nums.
  • Time Complexity: O(n)

Finding Target Indices

  • We iterate through the sorted array to collect target indices.
  • Time Complexity: O(n)

Overall Time Complexity

  • The dominant terms are O(n) (traversing the array multiple times) and O(mx) (prefix sum computation).
  • If mx is significantly smaller than n, the overall complexity is O(n).
  • In the worst case where mx is large, the complexity is O(n+mx)

Space Complexity: O(n+mx)

Before analyzing space complexity, let's define:

  • Auxiliary Space Complexity: Extra space used by the algorithm excluding the input.
  • Total Space Complexity: The sum of auxiliary space and input space.

Auxiliary Space Complexity

The additional space used in the code includes:

  • Frequency Array (freq) → O(mx) space to store the count of each number.
  • Prefix Frequency Array (prefix_freq) → O(mx) space to store cumulative counts.
  • Sorted Array (sorted_nums) → O(n) space for sorting the input.
  • Result Array (ans) → Stores the indices of target, at most O(n) in the worst case.

Thus, the auxiliary space complexity is O(n+mx).

Total Space Complexity

  • The input array nums takes O(n) space.
  • Adding the auxiliary space, the total space complexity is O(n+mx).

In cases where mx is much smaller than n, space complexity is effectively O(n).

Similar Problems

Now we have successfully tackled this problem, let's try these similar problems:-

1. Find First and Last Position of Element in Sorted Array

Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.

If target is not found in the array, return [-1, -1].

You must write an algorithm with O(log n) runtime complexity.

2. Rank Transform of an Array

Given an array of integers arr, replace each element with its rank.

The rank represents how large the element is. The rank has the following rules:

  • Rank is an integer starting from 1.
  • The larger the element, the larger the rank. If two elements are equal, their rank must be the same.
  • Rank should be as small as possible.

3. Find Words Containing Character

You are given a 0-indexed array of strings words and a character x.

Return an array of indices representing the words that contain the character x.

Note that the returned array may be in any order.