[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]