Skip to content

2089. Find Target Indices After Sorting Array

SourceWeekly Contest 269 Q1DifficultyEasyRating1152

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.

 

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 nums[i] == 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 nums[i] == 3 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 nums[i] == 5 is 4.

 

Constraints:

  • 1 <= nums.length <= 100
  • 1 <= nums[i], target <= 100

Solutions

Solution 1

Thinking

With \(n \le 100\), sort and collect indices equal to \(\textit{target}\); they already appear in increasing order.

A linear count of smaller/equal values could build the same range; the code simply sorts.

1
2
3
4
class Solution:
    def targetIndices(self, nums: list[int], target: int) -> list[int]:
        nums.sort()
        return [i for i, v in enumerate(nums) if v == target]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
    public List<Integer> targetIndices(int[] nums, int target) {
        Arrays.sort(nums);
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < nums.length; ++i) {
            if (nums[i] == target) {
                ans.add(i);
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
public:
    vector<int> targetIndices(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        vector<int> ans;
        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i] == target) {
                ans.push_back(i);
            }
        }
        return ans;
    }
};

1
2
3
4
5
6
7
8
9
func targetIndices(nums []int, target int) (ans []int) {
    sort.Ints(nums)
    for i, v := range nums {
        if v == target {
            ans = append(ans, i)
        }
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
function targetIndices(nums: number[], target: number): number[] {
    nums.sort((a, b) => a - b);
    let ans: number[] = [];
    for (let i = 0; i < nums.length; ++i) {
        if (nums[i] == target) {
            ans.push(i);
        }
    }
    return ans;
}

Solution 2: Counting

Thinking

Solution 1 sorts the whole array to recover indices, so the time stays \(O(n \log n)\). Those indices depend only on where \(\textit{target}\) would sit after sorting, not on the order among the other values.

The number of values strictly less than \(\textit{target}\) is the start of that contiguous range, and the number of values equal to \(\textit{target}\) is its length. Both counts come from one pass over the original array, which removes the comparison sort.

After sorting into non-decreasing order, every value equal to \(\textit{target}\) occupies one contiguous index range. The start of the range equals the number of elements strictly less than \(\textit{target}\), and the length equals the number of elements equal to \(\textit{target}\).

Scan \(\textit{nums}\) once and store the two counts in \(\textit{less}\) and \(\textit{equal}\). The answer is every integer in \([\textit{less}, \textit{less} + \textit{equal})\). The range is empty when \(\textit{equal} = 0\).

The time complexity is \(O(n)\), and the space complexity is \(O(1)\), where \(n\) is the length of \(\textit{nums}\).

1
2
3
4
5
6
7
8
9
class Solution:
    def targetIndices(self, nums: list[int], target: int) -> list[int]:
        less = equal = 0
        for x in nums:
            if x < target:
                less += 1
            elif x == target:
                equal += 1
        return list(range(less, less + equal))

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
    public List<Integer> targetIndices(int[] nums, int target) {
        int less = 0, equal = 0;
        for (int x : nums) {
            if (x < target) {
                ++less;
            } else if (x == target) {
                ++equal;
            }
        }
        List<Integer> ans = new ArrayList<>();
        for (int i = less; i < less + equal; ++i) {
            ans.add(i);
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<int> targetIndices(vector<int>& nums, int target) {
        int less = 0, equal = 0;
        for (int x : nums) {
            if (x < target) {
                ++less;
            } else if (x == target) {
                ++equal;
            }
        }
        vector<int> ans;
        for (int i = less; i < less + equal; ++i) {
            ans.push_back(i);
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
func targetIndices(nums []int, target int) (ans []int) {
    less, equal := 0, 0
    for _, x := range nums {
        if x < target {
            less++
        } else if x == target {
            equal++
        }
    }
    for i := less; i < less+equal; i++ {
        ans = append(ans, i)
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
function targetIndices(nums: number[], target: number): number[] {
    let less = 0;
    let equal = 0;
    for (const x of nums) {
        if (x < target) {
            ++less;
        } else if (x == target) {
            ++equal;
        }
    }
    const ans: number[] = [];
    for (let i = less; i < less + equal; ++i) {
        ans.push(i);
    }
    return ans;
}

Comments