How Many Numbers Are Smaller Than the Current Number LeetCode solution in Java

1
class Solution {
2
  public int[] smallerNumbersThanCurrent(int[] nums) {
3
    int[] sorted = nums.clone();
4
    int[] res = new int[nums.length]; // result array
5
    Arrays.sort(sorted);
6
    for (int i = 0; i < nums.length; ++i) {
7
      // binary search it, if there is no duplicates the idx will be how many smaller are there
8
      int idx = binarySearch(sorted, nums[i]);
9
      // if there are duplicates, then we need to find the first one presented in the array
10
      if (idx - 1 >= 0 && sorted[idx - 1] == nums[i]) {
11
        while (idx >= 0 && sorted[idx] == nums[i]) {
12
          --idx;
13
        }
14
        ++idx;
15
      }
16
      // As I said before, array of indices(indexes) will be the answer
17
      res[i] = idx;
18
    }
19
    return res;
20
  }
21

22
  // Just simple iterative binary search
23
  public static int binarySearch(int[] arr, int target) {
24
    int s = 0;
25
    int e = arr.length - 1;
26
    int m = (s + e) / 2;
27

28
    while (s <= e) {
29
      if (arr[m] == target) {
30
        return m;
31
      } else if (arr[m] > target) {
32
        e = m - 1;
33
      } else {
34
        s = m + 1;
35
      }
36
      m = (s + e) / 2;
37
    }
38
    return -1;
39
  }
40
}