# Java O(nlgn) solution 42ms beats 99.71% @ 2017-07-02 00:28:19

• Sort first, then do a one pass to find the longest length desired. Does not employ hashtables. Only keep two pointers to speed up the algorithm.

``````public class Solution {
public int findLHS(int[] nums) {
Arrays.sort(nums);
int maxLen = 0;
int firstPrev = 0, secondPrev = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] > nums[firstPrev]) {
if (nums[i] - nums[firstPrev] == 1) {
if (nums[i] > nums[secondPrev]) secondPrev = i;
} else if (nums[i - 1] - nums[firstPrev] == 1) {
maxLen = Math.max(maxLen, i - firstPrev);
if (nums[i] - nums[i - 1] == 1) {
firstPrev = secondPrev;
secondPrev = i;
} else {
firstPrev = secondPrev = i;
}
} else firstPrev = secondPrev = i;
}
}
return Math.max(maxLen, secondPrev > firstPrev ? (nums.length - firstPrev) : 0);
}
}
``````

We track the closest run of `k and k + 1` with `firstPrev` and `secondPrev`

• `firstPrev`: index of the leftmost `k`
• `secondPrev`: index of the leftmost `k + 1`.

The logic can be a little intricate. The cases below should help understand the algorithm. Especially, the last branch of the conditional logic deals specifically a situation that arises in `input6`.

``````        int[] input1 = {1,3,2,2,5,2,3,7};//5
int[] input2 = {1,3,5,7,9,11,13,15,17};//0
int[] input3 = {4289383,46930886,81692777,14636915,57747793,24238335,19885386,49760492,96516649,89641421};//0
int[] input4 = {1,3,2,2,5,2,3,6,2,1,2,3,2,3,2,3,2,3,7};//5
int[] input5 = {1,2,2,1};//4
int[] input6 = {1,2,3,3,1,-14,13,4};//3
``````

My original idea was to use hashing, which also saves the trouble of sorting at all. But `input3` broke that approach.

I submitted the code twice, with time 43ms(99.61%) and 42ms(99.71%).

Despite the benchmarking purpose, I do think the more important version of solution is the O(n) hashtable solution. Overheads cause leetcode OJ to sorta penalize using hashtables, but in real interviews, I think hashtable is the better choice to go with.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.