iOS Interview - Leetcode 128. Longest Consecutive Sequence

November 18, 2024 • 4 min read • #swift, #interview, #leetcode

Leetcode: 128. Longest Consecutive Sequence

Naive Solution

Primary idea: Sort the array, remove duplicated elements then iterate through the array to find the longest sequence
Time Complexity: O(Nlog(N)), Time to sort the array is O(Nlog(N)).
Space Complexity: O(N). Extra space is needed for storing distinct elements.

func naive_longestConsecutive(_ nums: [Int]) -> Int {
    guard !nums.isEmpty else { return 0 }
    
    // Sort the array
    let nums = nums.sorted(by: <)
    
    // Insert repeated elements only
    // once in the vector
    var dist = [Int]()
    for (index, num) in nums.enumerated() {
        if index == 0 || nums[index - 1] != num {
            dist.append(num)
        }
    }
            
    // Find the maximum length
    // by traversing the array
    var count = 0
    var answer = 0
    for (index, num) in dist.enumerated() {
        // Check if the current element is
        // equal to previous element +1
        if index > 0 && dist[index] == dist[index - 1] + 1 {
            count += 1
        } else {
            count = 1
        }
        answer = max(answer, count)
    }
    
    return answer
}

print(naive_longestConsecutive([100,4,200,1,3,2])) // 4
print(naive_longestConsecutive([1, 9, 3, 10, 4, 20, 2, 5, 2])) // 5
print(naive_longestConsecutive([0,3,7,2,5,8,4,6,0,1])) // 9
print(naive_longestConsecutive([])) // 0
print(naive_longestConsecutive([0])) // 1
print(naive_longestConsecutive([0, 1, 3, 0, 2])) // 4

Using Hashing

Primary idea: We first insert all elements in a Set. Then, traverse over all the elements and check if the current element can be a starting element of a consecutive subsequence. To check if the current element, say X can be a starting element, check if (X – 1) is present in the set. If (X – 1) is present in the set, then X cannot be starting of a consecutive subsequence. Else if (X – 1) is not present, then start from X and keep on removing elements X + 1, X + 2 …. to find a consecutive subsequence.
Time Complexity: O(N), Only one traversal is needed and the time complexity is O(N) under the assumption that hash insert and search takes O(1) time.
Space Complexity: O(N), To store every element in the hashmap O(N) space is needed

func hashing_longestConsecutive(_ nums: [Int]) -> Int {
    guard !nums.isEmpty else { return 0 }

    // Hash all the array elements
    let numsSet = Set(nums)
            
    var answer = 0
    // check each possible sequence from the start
    // then update optimal length
    for num in nums {
        // if current element is the starting
        // element of a sequence
        if !numsSet.contains(num - 1) {
            var j = num
            // Then check for next elements in the
            // sequence
            while numsSet.contains(j) {
                j += 1
            }
            
            // update the answer if this length
            // is bigger
            answer = max(answer, j - num)
        }
    }
    
    return answer
}

print(hashing_longestConsecutive([100,4,200,1,3,2])) // 4
print(hashing_longestConsecutive([1, 9, 3, 10, 4, 20, 2, 5, 2])) // 5
print(hashing_longestConsecutive([0,3,7,2,5,8,4,6,0,1])) // 9
print(hashing_longestConsecutive([])) // 0
print(hashing_longestConsecutive([0])) // 1
print(hashing_longestConsecutive([0, 1, 3, 0, 2])) // 4