# Simple Java Sort Solution (beat 97.9%)

• ``````public int findLHS(int[] nums) {
if (nums.length == 0) {
return 0;
}
Arrays.sort(nums);
int start = 0;
int nextstart = 0;
for (int i = 1; i < nums.length; i++) {
if (nums[i] - nums[start] == 1) {
if (nums[nextstart] < nums[i]) {
nextstart = i;
}
res = Math.max(res, i - start + 1);
} else if (nums[i] - nums[start] > 1) {
start = start == nextstart ? i : nextstart;
i--;
}
}
return res;
}
``````

Thanks all for the comments. I revised the code to make it easier to read and adjusted the percentage.

• I dont think this is a O(n logn) solution, to get the for loop in O(n), everytime a need to move the start is detected, it needs to be from i.

• @johnyrufus16 Thanks for your comment. I optimized the code. Now it runs in 44 ms and beats 100%. Actually if we need to move start idx, we can't make it point to i directly. We need to use a variable to keep track of the next idx. Example would be 1, 1, 1, 2, 2, 3, 3, in this case, if i points to 3 where the idx is 5, we should change start idx to point to first 2's idx which is 3.

• @ihaveayaya
nice, you have optimized a lot, but we can still proceed in a fashion where stardIdx never needs to go back, here is my code (my code ooks a bit more stressful :) so not sure if its worth the effort):

``````public static int findLHS(int[] nums) {
if(nums.length < 2 ) return 0;
Arrays.sort(nums);
int count = 0;

int res = Integer.MIN_VALUE;

int curi = 0;
int curj = 0;

while(curj + 1 < nums.length && nums[curj + 1] == nums[0]) ++curj;

for(int  nexti = curj+1; nexti < nums.length; nexti++) {
int nextj = nexti;
while(nextj + 1 < nums.length && nums[nextj + 1] == nums[nexti]) ++nextj;
if(nums[curi] + 1 == nums[nexti]) {
res = Math.max(res, nextj - curi + 1);
}
curi = nexti;
curj = nextj;
nexti = curj;
}
return Math.max(res, count);
}
``````

• @johnyrufus16 Thanks for your post. I have already changed the way to traverse the array. Start idx now always increase.

• Why sorting O(nlogn) can beat normal HashMap O(n) solution ?

• @daniexia I think it's test case specific. Hashmap can introduce some overhead which would slow down the execution. We are not comparing runtime complexity here.

• ``````public class Solution {
public int findLHS(int[] nums) {
Arrays.sort(nums);

int result = 0;
int left = 0, right = 0;

while (right < nums.length) {
if (nums[right] - nums[left] < 1)
right++;
else if (nums[right] - nums[left] == 1) {
result = Math.max(result, right - left + 1);
right++;
} else
left++;
}

return result;
}
}
``````

• I think they changed the test cases further more only a month or so later. Now this algorithm is 55ms beats 92.23% according to my last submission(2017-07-02 00:38:02).

• This post is deleted!

• my code beats >94%

``````public class Solution {
public int findLHS(int[] nums) {
if(nums == null || nums.length <= 1){
return 0;
}
Arrays.sort(nums);
int len = nums.length;
int max = 0;
int curr = 0;
int small = 1;
int large = 0;
//分情况讨论：1.如果当前元素等于前一个元素（再继续判断它是属于小的还是大的）
//2.如果当前元素值比前一个元素值大1（判断该元素是下一次比较的较大者，还是本次比较的较大者）
//3.如果不符合上面两种情况，则重置large和small
//每一轮比较，如果large不为0的话，说明有存在值相差1的序列对，则更新max的值
for(int i = 1; i < len; i++){
if(nums[i] == nums[i-1] + 1){
if(small == 0){
small = 1;
}else if(large != 0){
max = Math.max(max, large+small);
small = large;
}
large = 1;
}else if(nums[i] == nums[i-1]){
if(large == 0){
small++;
}else{
large++;
}
}else{
small = 1;
large = 0;
}
if(large != 0){
max = Math.max(max, large+small);
}
}
return max;
}
}
``````

• My clean version:

``````public int findLHS(int[] nums) {
int result = 0;
Arrays.sort(nums);
int left = 0 , right = 1;
//right is the subsequence's right RHS index and left is the subsequence's LHS index
//namely: nums[right] is max, nums[left] is min
while(right<nums.length){
while(nums[right]-nums[left]>1) left++;  //in case of difference between max and min > 1
if(right-left+1>result&&nums[right]-nums[left]==1) result = right-left+1; //update result if new length: right-left+1> result and difference between max and min = 1
right++;
}
return result;
}``````

• @tongzhou2
great solution!

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