Start learning free

LESSON 227 OF 415 · SORTING

Longest Consecutive Sequence in Swift: O(n log n) with Sorting

Practice O(n log 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:

For this lesson, your algorithm should run in O(n log n) time and use O(1) extra space.
(There are faster solutions which we will discuss in future lessons)


Hints:

Let's sort the array in non-decreasing order. In this way each consecutive elements sequence is a subarray of the sorted array. Even more, these consecutive elements subarrays will come one after another.

Let's start by finding the first subarray. Its left endpoint is i = 0. We will use another index variable j to find the right endpoint. j is initially equal to i + 1 and should be incremented for as long as nums[i...j] is a consecutive subarray. But how can we check this?

j is initially equal to i + 1 and will be incremented as long as nums[j] <= nums[j - 1] + 1. When the condition is not satisfied anymore, we have found the first subarray: nums[i...j-1]. How can we find the second one?

The left endpoint of the second subarray is j. So we can set the index i to j. Then we can continuously increment j as long as our condition is satisfied just like we did for the first subarray. When the condition is not satisfied anymore, we have found the second subarray: nums[i...j-1]. Can we use the same strategy for finding the rest of the subarrays?

Yes, we can. We should design an algorithm that repeats this strategy until we are left with no more subarrays (e.g. i >= n, where n is nums.count).
  • 1. Initialize i with 0.
  • 2. While i < n:
    • 1. Initialize j with i + 1.
    • 2. While nums[j] <= nums[j - 1] + 1, increment j
    • 3. Set i to j and return to step 1.

STEP 1 OF 11
    Ctrl + Enter to check

    SWIFT · SORTING

    Longest Consecutive Sequence in Swift, explained

    Problem overview

    The method longestConsecutive receives an unsorted array of integers and returns the length of the longest run of values that follow each other by exactly 1: such as 1, 2, 3, 4. The values don't need to be next to each other in the array, and a repeated value counts once.

    For [100, 4, 200, 1, 3, 2] the longest run is 1, 2, 3, 4, so the answer is 4. For [0, 2, 0, 1, 2, 3, 1] the answer is also 4, from 0, 1, 2, 3. The repeated 0, 1 and 2 add nothing.

    Approach: sort, then scan the runs

    After sorting, every run of consecutive values is a block of neighbours in the array, and the blocks follow each other. Within a block, each element is either equal to the previous one (a duplicate) or exactly one larger. When an element is two or more above the last value, there is a gap, and a new block starts.

    So one pass is enough. Start a block at index i and extend it with a second index j. Keep currVal, the last value of the run so far. If nums[j] equals currVal, it is a duplicate: skip it. If it equals currVal + 1, the run grows: increase currVal. If it is larger still, the run has ended. The run's length is currVal - nums[i] + 1, and the next block starts at j.

    Sorted, the second example is [0, 0, 1, 1, 2, 2, 3]. The block starts at the first 0. The scan skips the second 0, then grows through 1, skips the second 1, grows to 2, skips the second 2 and grows to 3. The length is 3 - 0 + 1 = 4.

    Now the first example, sorted: [1, 2, 3, 4, 100, 200]. The first block starts at 1. The scan grows through 2, 3 and 4, then meets 100, which is above currVal + 1 = 5, so the block ends with length 4 and i jumps to the index of 100. That block is just 100, with length 1, and the last block is just 200. The maximum is 4.

    Step by step

    1. Start with result = 1. A non-empty array always has a run of at least one value.
    2. Make a mutable copy. A parameter is a constant, so var nums = nums shadows it with a variable.
    3. Sort the copy with sort().
    4. Open a while loop with the index i at 0. It marks the first element of the block being measured. The loop doesn't add 1 to i; its last line moves i to the start of the next block.
    5. Set currVal to nums[i]: the run so far contains just that value.
    6. Set j to i + 1, the next element to look at.
    7. Inner loop: run while j < nums.count and nums[j] <= currVal + 1. Checking j first means nums[j] is never read past the end.
    8. Grow the run with if nums[j] == currVal + 1 { currVal += 1 }. A duplicate fails the test and changes nothing.
    9. Move on with j += 1 on every pass.
    10. Record the length with max(result, currVal - nums[i] + 1).
    11. Jump to the next block with i = j, then return result after the outer loop.

    The solution in Swift

    class Solution {
    func longestConsecutive(_ nums: [Int]) -> Int {
        var result = 1
        var nums = nums
        nums.sort()

        var i = 0
        while i < nums.count {
            var currVal = nums[i]
            var j = i + 1
            while j < nums.count && nums[j] <= currVal + 1 {
                if nums[j] == currVal + 1 {
                    currVal += 1
                }
                j += 1
            }
            result = max(result, currVal - nums[i] + 1)
            i = j
        }
        return result
    }
}

    The Swift details worth knowing:

    • Short-circuit &&. If j < nums.count is false, Swift doesn't evaluate the right side. That is why the bounds check has to come first.
    • No C-style for. Because i jumps by variable amounts, a while loop is the natural fit. A for i in 0..<nums.count loop can't have its counter changed inside it.
    • Shadowing. var nums = nums is legal in a function body and gives you a mutable local copy. The caller's array is unchanged.
    • Global max. max(a, b) returns the larger of two values.
    • Empty array. The function returns 1 for an empty array, since result starts at 1 and the loop never runs. The lesson doesn't use that case, but it is the one place where 1 is not a true run length.

    Complexity

    Time: O(n log n). Sorting dominates. The two while loops together advance j through the array once, since i always jumps to where j stopped, so the scan is O(n).

    Space: O(n). The sorted copy of the array holds n values. Apart from it, the code uses a few integers.

    Edge cases and common mistakes

    • Duplicates. [1, 2, 2, 3] has the run 1, 2, 3, so the answer is 3, not 4. The inner test nums[j] == currVal + 1 keeps duplicates from counting.
    • Negative values. [-2, -1, 5] gives 2. The subtraction currVal - nums[i] + 1 works the same for negative numbers.
    • A gap in the middle. [1, 2, 4, 5, 6] gives 3, from 4, 5, 6.
    • Using the block's size. Measuring a block as j - i counts duplicates. The length must come from the values, currVal - nums[i] + 1.
    • Stopping on a duplicate. If the loop condition were nums[j] == currVal + 1, a duplicate would end the run too early.
    • Forgetting i = j. The outer loop would never move forward and would repeat forever.

    Testing

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