Alex Sikorski
Jun 05, 2022
Find Target Indices After Sorting Array (LeetCode #2089)
#java
#leetcode
#leetcode easy
The problem starts by giving 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 <= 1001 <= nums[i], target <= 100
Initial Thoughts
We are told to sort nums in ascending order, but that is not necessary. The reason for this is that we can count the frequency of target numbers (let's call this number count) and also count the frequency of numbers lesser than the target number (let's call this number pos).
As we know the indexes that we want to obtain would be from an ascending list, we can simply figure out the position of the initial target number in that list by counting the frequency of numbers that are lesser than the target number. As they are lesser, they will appear before the target number. This is how we know the position, pos, of the target number without having to order the list. If there are more instances of the target number in the list, all we have to do is increment pos for each instance as they will appear after the initial position since it is an ascending list.
Solution
class Solution {
public List<Integer> targetIndices(int[] nums, int target) {
List<Integer> list = new ArrayList();
int count = 0;
int pos = 0;
// declare variables for target number count
// and 'sorted' position of target number
for(int i: nums){
if(i == target)
count++;
// if number in nums is target number, add to count
if(i < target)
pos++;
// if the number is smaller than target, if sorted, would
// be placed before target number so by counting these
// we will know where the target number(s) would start appearing
}
for(int i = 0; i < count; i++){
list.add(pos + i);
// for loop to calculate the indexes, the pos is incremented for
// each instance of the target number to create the answer
}
return list;
}
}Result
Alex Sikorski
Currently working as a full stack Software Engineer and curiously seeking new knowledge in free time.