Longest Harmonious Subsequence LeetCode solution in Java

1
class Solution {
2
  public static int firstOccurence(int[] arr, int target) {
3
    int res = -1;
4
    int start = 0;
5
    int end = arr.length - 1;
6
    while (start <= end) {
7
      int mid = start + (end - start) / 2;
8
      if (arr[mid] == target) {
9
        res = mid;
10
        end = mid - 1;
11
      } else if (arr[mid] < target) {
12
        start = mid + 1;
13
      } else {
14
        end = mid - 1;
15
      }
16
    }
17
    return res;
18
  }
19

20
  public static int lastOccurence(int[] arr, int target) {
21
    int res = -1;
22
    int start = 0;
23
    int end = arr.length - 1;
24
    while (start <= end) {
25
      int mid = start + (end - start) / 2;
26
      if (arr[mid] == target) {
27
        res = mid;
28
        start = mid + 1;
29
      } else if (arr[mid] < target) {
30
        start = mid + 1;
31
      } else {
32
        end = mid - 1;
33
      }
34
    }
35
    return res;
36
  }
37

38
  public int findLHS(int[] nums) {
39
    Arrays.sort(nums);
40
    int maxLen = 0;
41
    for (int i = 0; i < nums.length - 1; i++) {
42
      if (nums[i + 1] == nums[i] + 1) {
43
        int a = firstOccurence(nums, nums[i]);
44
        int b = lastOccurence(nums, nums[i] + 1);
45
        if (b - a + 1 > maxLen) maxLen = b - a + 1;
46
      }
47
    }
48
    return maxLen;
49
  }
50
}