Find Longest consecutive sequence

[Question]: Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence. You must write an algorithm that runs in O(n) time.
Example: I/P = [200,4,2,1,3,100].. Output-> 4 because 1,2,3,4 is largest consecutive.

// Question: Find longest consecutive in an array
// TC: O(N)
// SC: O(N)
func  longestConsecutive(_ nums: [Int]) -> Int {
    
    var setObject = Set(nums)
    var longestStreak = 0
    
    for i in 0..<nums.count {
        
        if !setObject.contains(nums[i] - 1) {// Find smallest element in the set
            var currentNum = nums[i]
            var currentStreak = 1
            
            while setObject.contains(currentNum + 1) {// Based on smallest element we got find next higher number
                currentNum += 1
                currentStreak += 1
            }
            
            longestStreak = max(longestStreak, currentStreak)// compare max length array
        }
    }
    
    return longestStreak
}
var consecutiveArr = [200,4,2,1,3,100]
var ansConsecutiveArr = longestConsecutive(consecutiveArr)
print("The longest consecutive sequence is ", ansConsecutiveArr)// 4
Now a similar problem which gives consecutive array
// Question: Find longest consecutive in an array
func  longestConsecutiveArray(_ nums: [Int]) -> [Int] {
    
    var setObject = Set(nums)
    var longestArr:[Int] = []
    for i in 0..<nums.count {
        
        if !setObject.contains(nums[i] - 1) {// Find smallest element in the set
            var currentNum = nums[i]
            
            while setObject.contains(currentNum + 1) {// Based on smallest element we got find next higher number
                longestArr.append(currentNum)
                currentNum += 1
                if !setObject.contains(currentNum + 1) {
                    longestArr.append(currentNum)
                }
            }
            
        }
    }
    return longestArr
}
var consecutiveArr1 = [6,8,7,100,200]
var ansConsecutiveArr1 = longestConsecutiveArray(consecutiveArr1)
print("The longest consecutive sequence is ", ansConsecutiveArr1)//[6, 7, 8]

Leave a Comment

Your email address will not be published. Required fields are marked *