0
\$\begingroup\$

The task:

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

For example, given [100, 4, 200, 1, 3, 2], the longest consecutive element sequence is [1, 2, 3, 4]. Return its length: 4.

Your algorithm should run in O(n) complexity.

My solution:

const sample = [1, 100, 2, 90, 3, 88, 4, 9, 5];
const compare = prefix => (a,b) => prefix * (a - b);
const ascending = compare(1);

const maxObj = {
  maxResult: 0,
  maxCurrent: 1,
};

const getMax = (max, current) => current > max ? current : max;
const countConsecutive = (maxObj, _, idx, src) => {
  if ((src[idx] + 1) === src[idx + 1]) {
    maxObj.maxResult = ++maxObj.maxCurrent > maxObj.maxResult ?
        maxObj.maxCurrent : maxObj.maxResult;
  }
  return maxObj;
}
const result = sample
  .sort(ascending)
  .reduce(countConsecutive, maxObj);
console.log(result.maxResult);

Can you write the code so it is faster (and still be readable/maintainable)?

\$\endgroup\$
1
  • 1
    \$\begingroup\$ sort makes this O(nlog(n)) \$\endgroup\$
    – molamk
    Commented Feb 3, 2019 at 12:47

2 Answers 2

1
\$\begingroup\$

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;
}
\$\endgroup\$
6
  • \$\begingroup\$ I don't know why you get 7, but I get 5. \$\endgroup\$ Commented Feb 3, 2019 at 12:17
  • \$\begingroup\$ @thadeuszlay I double checked and the code as given in the question returns 7 for [1, 100, 2, 90, 3, 88, 4, 89, 5] the reason is you count up every time (src[idx] + 1) === src[idx + 1] is true so 88 +1 === 89 and so... is counted \$\endgroup\$
    – Blindman67
    Commented Feb 3, 2019 at 12:55
  • \$\begingroup\$ I just executed this and it returns 5:jsbin.com/qamaxitupe/edit?js,console \$\endgroup\$ Commented Feb 3, 2019 at 13:05
  • \$\begingroup\$ BTW: Isn't your code just as fast as mine, i.e. O(nlog(n))? \$\endgroup\$ Commented Feb 3, 2019 at 13:07
  • \$\begingroup\$ I just ran your jsbin with [1, 100, 2, 90, 3, 88, 4, 89, 5] and it returned 7. (NOTE I changed the 9 to 89) And yes it is the same complexity. I did not change the logic just the number of lines \$\endgroup\$
    – Blindman67
    Commented Feb 3, 2019 at 13:36
1
\$\begingroup\$

I think you can get average-case O(n) complexity using hashing.

Perform a single pass over the data, recording consecutive ranges in a hash table ( the current start and end of each range needs to be recorded ).

When the next input element ( integer ) is encountered, check ( using hashing ) whether there is a range which can be extended.

If there is, extend that range, re-hashing as necessary. Keep track of the longest range found ( which will be the final result ).

[ Be sure to allow for the case where the new element allows two ranges to be merged ]

\$\endgroup\$
1
  • \$\begingroup\$ if we define "average" and "linear" loosely enough that hashing qualifies, then radix sort qualifies too and we're back to the original, simpler algorithm. \$\endgroup\$ Commented Feb 4, 2019 at 1:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.