Find Target Indices After Sorting Array LeetCode solution in Java

1
class Solution {
2
  /**
3
   * Algorithm: - Parse the array once and count how many are lesser than target and how many are
4
   * equal - DO NOT sort the array as we don't need it sorted. Just to know how many are lesser and
5
   * how many are equal. O(N) better than O(NlogN - sorting) - The response list will have a size =
6
   * with the number of equal elements (as their positions) - Loop from smaller to smaller+equal and
7
   * add the values into the list. Return the list
8
   */
9
  public List<Integer> targetIndices(int[] nums, int target) {
10
    int smaller = 0;
11
    int equal = 0;
12
    for (int num : nums) {
13
      if (num < target) {
14
        smaller++;
15
      } else if (num == target) {
16
        equal++;
17
      }
18
    }
19
    List<Integer> indices = new ArrayList<>(equal);
20
    for (int i = smaller; i < smaller + equal; i++) {
21
      indices.add(i);
22
    }
23
    return indices;
24
  }
25
}