# Single pass using HashMap, no sorting

• I use a map to store 3 values about each element n: `[top, bottom, flat]`.
`top` is the count of `n+1`.
`bottom` is the count of `n-1`.
`flat` is the count of `n`.
If `n` isn't encountered before, default to `[0,0,1]`, else increment `flat`. After that check if we've encountered `n+1` and/or `n-1`.
If encountered `n+1` before, then increment `top` for `n` by (flat count of n + 1) - (top count of n). Also increment `bottom` for `n+1`.
If encountered `n-1` before, then increment `bottom` for `n` by (flat count of n - 1) - (bottom count of n). Also increment `top` for `n-1`.
Finally, if either `top > 0` or `bottom > 0` for `n`, then `max` is the maximum between `max`, `top+flat` and `bottom+flat`.
Apologies if my explanation is confusing. Code provided below.

Javascript version:

``````var findLHS = function(nums) {
if (nums.length < 2) {
return 0;
}
var map = {};
var max = 0;
map[nums[0]] = [0, 0, 1]; // [top, bottom, flat]
var curr;
for (var i = 1; i < nums.length; i++) {
var n = nums[i];
if (!map.hasOwnProperty(n)) {
map[n] = [0, 0, 1];
} else {
map[n][2]++;
}
curr = map[n];
if (map.hasOwnProperty(n + 1)) {
curr[0] += map[n+1][2] - curr[0];
map[n + 1][1]++;
}
if (map.hasOwnProperty(n - 1)) {
curr[1] += map[n-1][2] - curr[1];
map[n - 1][0]++;
}
if (curr[0] > 0 || curr[1] > 0) {
max = Math.max(max, curr[0] + curr[2], curr[1] + curr[2]);
}
}
return max;
};
``````

Java version:

``````public int findLHS(int[] nums) {
if (nums.length < 2) {
return 0;
}
Map<Integer, int[]> map = new HashMap<>();
int max = 0;
map.put(nums[0], new int[]{0, 0, 1}); // [top, bottom, flat]
for (int i = 1; i < nums.length; i++) {
int n = nums[i];
if (map.containsKey(n)) {
map.get(n)[2]++;
} else {
map.put(n, new int[]{0, 0, 1});
}
int[] curr = map.get(n);
int[] top = map.get(n+1);
int[] bottom = map.get(n-1);
if (top != null) {
curr[0] += top[2] - curr[0];
top[1]++;
}
if (bottom != null) {
curr[1] += bottom[2] - curr[1];
bottom[0]++;
}
if (curr[0] > 0 || curr[1] > 0) {
max = Math.max(max, Math.max(curr[0] + curr[2], curr[1] + curr[2]));
}
}
return max;
}
}
``````

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