Start learning free

LESSON 269 OF 414 · HASH TABLE

Longest Consecutive Sequence in Scala: O(n) with a HashSet

Practice O(n) Read the full explanation

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

Example 1:

Input: [100, 4, 200, 1, 3, 2]
Output: 4
Explanation: Longest consecutive sequence is [1, 2, 3, 4].
             Therefore its length is 4.

Example 2:

Input: [0, 2, 0, 1, 2, 3, 1]
Output: 4
Explanation: Longest consecutive sequence is [0, 1, 2, 3].
             Therefore its length is 4.
	     Note that we count each value once, even though values 0, 1 and 2 appear 2 times each in nums

Note:

Your algorithm should run in O(n) time and use O(n) extra space.


STEP 1 OF 8
    Ctrl + Enter to check

    SCALA · HASH TABLE

    Longest Consecutive Sequence in Scala, explained

    Problem overview

    The method longestConsecutive receives an unsorted Array[Int] called nums and returns the length of the longest run of consecutive integers that can be formed from its values. The run doesn't have to appear in order in the array: it only has to be made of values that are all present.

    For Array(100, 4, 200, 1, 3, 2) the values 1, 2, 3 and 4 are all present, so the answer is 4. The values 100 and 200 are isolated.

    A second example is Array(0, 2, 0, 1, 2, 3, 1). The values 0, 1, 2 and 3 form a run of length 4, and the answer is 4, not 7. Each value counts once, even though 0, 1 and 2 appear twice.

    The lesson asks for O(n) time and O(n) extra space.

    Approach: start counting only at the beginning of a run

    Sorting the array and scanning would work, but costs O(n log n). To stay linear, put all values in a hash set. Then a question like "is 5 in the array?" takes constant time on average.

    The naive use of the set is to start from every value and walk upward while the next value exists. That is correct but can be slow: in 1, 2, 3, ..., n, starting from every number walks over the rest of the run each time, which is O(n²). The fix is to walk a run only from its first number. A value is the first of a run exactly when value - 1 is not in the set. For every other value, skip it: its run will be walked from the real start.

    Every run is then walked once, from its start, and each number is visited a constant number of times overall. The walk from a start counts upward: for a length sequenceLength that begins at 1, the next number needed is value + sequenceLength. The walk ends at the first number that isn't in the set.

    On Array(100, 4, 200, 1, 3, 2) the only values whose predecessor is missing are 100, 200 and 1. Starting from 100 gives length 1, from 200 gives 1, and from 1 the walk finds 2, 3 and 4 and then stops at 5, so the length is 4.

    Step by step

    1. Declare result with var, starting at 0. This is also the right answer for an empty array.
    2. Fill the set. Create values, an empty scala.collection.mutable.HashSet[Int](), and add each element of nums in a for loop. Adding a number that is already there does nothing, so values holds every distinct number once.
    3. Loop over the set, not the array: for (value <- values). This skips duplicates automatically.
    4. Find run starts. Test !values.contains(value - 1). Only then is value the first number of a run.
    5. Start the length at 1 with var sequenceLength = 1, because the run already contains value.
    6. Extend the run. while (values.contains(value + sequenceLength)), add 1 to sequenceLength. The loop stops at the first number that is missing.
    7. Keep the best. After the while, still inside the if, set result = math.max(result, sequenceLength).
    8. Return result below the for loop.

    The solution in Scala

    class Solution {
    def longestConsecutive(nums: Array[Int]): Int = {
        var result = 0
        val values = scala.collection.mutable.HashSet[Int]()
        for (value <- nums) {
            values.add(value)
        }
        for (value <- values) {
            if (!values.contains(value - 1)) {
                var sequenceLength = 1
                while (values.contains(value + sequenceLength)) {
                    sequenceLength += 1
                }
                result = math.max(result, sequenceLength)
            }
        }
        return result
    }
}

    The Scala details worth a closer look:

    • Two loops over different things. The first for iterates the array to fill the set, and the second iterates the set itself. Iterating over a mutable set is fine as long as the loop doesn't change it, and this loop only reads values.
    • Same name, separate scopes. Both loops call their variable value. Each name exists only inside its own loop, so there is no clash.
    • var inside the if. sequenceLength is created fresh for every run start, so each walk begins at 1.
    • Int arithmetic. value - 1 and value + sequenceLength are Int operations, and Int wraps silently. With Int.MinValue in the array, value - 1 wraps around to Int.MaxValue, so a set holding both extremes could be seen as a run. The lesson's inputs don't go there.
    • Return style. The explicit return result sits directly in the method body, not inside a for closure, so it behaves normally. The bare expression result would do the same.

    Complexity

    Time: O(n). Filling the set takes n constant-time insertions on average. In the second loop, every value costs one membership test, and the while loop runs only for run starts. Each distinct number is stepped over by exactly one walk, the one from the start of its run, so the walks together take at most n steps.

    Space: O(n). The set holds each distinct value once.

    Edge cases and common mistakes

    • Empty array. Both loops do nothing and the result is 0.
    • Duplicates. Array(5, 5, 5) gives 1. The set keeps one 5.
    • Negative numbers. Array(-2, -1, 0, 5) gives 3, since -2, -1, 0 is a run.
    • Skipping the start test. Without the !values.contains(value - 1) check the answer is still correct, but a long run is re-walked from each of its numbers, which makes the time O(n²).
    • Counting array length. Using the array's length instead of the distinct numbers counts duplicates. In the second example that would give 7 rather than 4.
    • Starting the length at 0. A run contains its start, so the length begins at 1. Starting at 0 and checking value + sequenceLength would be off by one.
    • Wrong next number. The next number to look for is value + sequenceLength. Using value + 1 every time never moves forward.

    Testing

    • Array(100, 4, 200, 1, 3, 2) gives 4.
    • Array(0, 2, 0, 1, 2, 3, 1) gives 4.
    • Array(-2, -1, 0, 5) gives 3.
    • Array(5, 5, 5) gives 1.
    • Array() gives 0.
    Keep going with ScalaAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free