Longest Consecutive Sequence in an Array.

A32.swift

// Article Link: https://takeuforward.org/data-structure/longest-consecutive-sequence-in-an-array/
// Problem Link: https://leetcode.com/problems/longest-consecutive-sequence/

// Brute Force Approch

// TC -> O(n * n * n)
// SC -> O(1)

// Thought Process
// 1. We will try to find one greater element for every element using binary search.
// 2. If found increase by 1 that founded element and counter, try to find this new element.
// 3. Repeat.

func longestConsecutive(_ arr: [Int]) -> Int {
    let n = arr.count
    var maxLength = 0

    for i in arr.indices {
        var ele = arr[i] + 1
        var count = 1

        while(binarySearch(arr, ele)) {
            ele += 1
            count += 1
        }

        maxLength = max(maxLength, count)
    }

    return maxLength
}

func binarySearch(_ arr: [Int], _ number: Int) -> Bool {
    for ele in arr {
        if ele == number {
            return true
        }
    }

    return false
}

// Better Approch

// TC -> O(nlogn * n)
// SC -> O(n)

// Thought Process:
// 1. First we sort the array.
// 2. Keeping a track of last smallest element.
// 3. If arr[i] - 1 == lastSmallest element then arr[i] will be the part of sequence.
//    if it is part of sequence increase the counter and change lastSmallest element to current.
// 4. If arr[i] == lastSmallest we will nothing.
// 5. if arr[i] != lastSmallest, we will reset the variables.

func longestConsecutive(_ nums: [Int]) -> Int {
    var arr = nums
    arr.sort()

    let n = arr.count
    var maxLength = 0, currentCount = 1, lastSmallest = Int.min

    for ele in arr {
        if ele - 1 == lastSmallest {
            currentCount += 1
            lastSmallest = ele
        }
        else if ele != lastSmallest {
            currentCount = 1
            lastSmallest = ele
        }

        maxLength = max(maxLength, currentCount)
    }

    return maxLength
}

// Optimal Approch 
// TC -> O(n + n)
// SC -> O(n)

// Thought Process:
// We will using the powers of Set to optimize the brute force approch
// 1. First we will add all elements in the set. (It will remove any duplicates, it will beneficial to optimize because
// it will also remove duplicates of first element of our consecutive sequence.)
// 2. We will check if ele - 1 is exists in set, we don't go further (simply skip that element)
// 3. If not check every concesutive elements like brute force solution.

func longestConsecutive(_ nums: [Int]) -> Int {

    let n = nums.count

    var set = Set<Int>()

    for ele in nums {
        set.insert(ele)
    }

    var maxLength = 0

    for ele in set {
        if set.contains(ele - 1) == false {
            var currentCount = 1
            var x = ele + 1

            while(set.contains(x)) {
                currentCount += 1
                x += 1
            }

            maxLength = max(maxLength, currentCount)
        }
    }

    return maxLength
}