Complexity
The sort is about \$O(n log(n))\$ depending on the JS engine so this makes your function above \$O(n)\$
Redundancies
Your code is full of redundancies.
compare
and ascending
can just be ascending
and if you needed descending
you would just swap the arguments.
- The object named
maxObj
has redundant naming. The max
prefix is not needed in the properties. If you use it for minObj
would you thus need to rename the two properties?
- Does the max object need the name
Obj
?
- You ignor the second argument of reduce and then index the array to find it. The indexing is redundant as you already have the value stored in
_
.
- The function
getMax
is not used.
- The
()
around src[idx] + 1
is not needed, the operator +
has precedence over ===
- You can use
Math.max
if only complexity is important rather than the ternary that only gives a slight performance benefit over Math.max
- The line
maxObj.maxResult = ++maxObj.maxCurrent > maxObj.maxResult ? maxObj.maxCurrent : maxObj.maxResult;
is redundant. Each time you call it maxCurrent
is always greater than maxResult
. Not only is the line redundant but it makes the need for maxObj
redundant as well.
Same function without the redundant code
You can thus remove most of the code, wrap it in a function, use closure to access samples
to get 4 line and many fewer objects, arguments, and overhead to do the same thing. More readable and faster, (not less complex)
From about 16 lines to 4 for the same result.
const countConsecutive = arr => {
const count = (count, val, i) => count += val + 1 === arr[i + 1] ? 1 : 0;
return sample.sort((a, b) => a - b).reduce(count, 1);
}
However
With all that said I am not sure that the result is correct?
For [1, 100, 2, 90, 3, 88, 4, 9, 5]
"...the longest consecutive element sequence..."
is 5 items.
That makes sense 1,2,3,4,5
But you return 7 for [1, 100, 2, 90, 3, 88, 89, 4, 9, 5]
?
To me 1, 2, 3, 4, 5, 88, 89, 90
is not a "consecutive... sequence" ???
An example solution
For a \$O(n)\$ solution you need to join sequences as you find them.
Use a Set
to do the lookups (if the next number exists). Iterate the set deleting numbers as you go lets you only check values you have not encountered.
Counting forwards sequences as you find them and storing the result in a map. When the next in a sequence is in the map add to the sequence length.
That brings the solution to \$O(2n + m)\$ The \$2n\$ as one pass is needed to create the Set
and where \$m\$ is the number of broken sequences that at max is \$n\$. So \$O(3n)\$ is the same as \$O(n)\$
There is room for performance improvement as you can do some of the counting as you create the Set
const longestSequence = (arr) => {
const numbers = new Set(arr), counts = {};
var max = 1;
for (const num of numbers.values()) {
let counting = true, next = num + 1;
numbers.delete(num);
while (counting) {
counting = false;
while (numbers.has(next)) { numbers.delete(next++) }
if (counts[next]) { counting = numbers.has(next += counts[next]) }
}
max = Math.max(counts[num] = next - num, max);
}
return max;
}
sort
makes thisO(nlog(n))
\$\endgroup\$