Longest Consecutive Sequence

LongestConsecutiveSequence.swift

//
//  LongestConsecutiveSequence.swift
//  Test
//
//  Created by KONSTANTIN KUSAINOV on 19/01/2019.
//  Copyright © 2019 KONSTANTIN KUSAINOV. All rights reserved.
//

//Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
//
//Your algorithm should run in O(n) complexity.
//
//Example:
//
//Input: [100, 4, 200, 1, 3, 2]
//Output: 4
//Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.
// https://leetcode.com/problems/longest-consecutive-sequence/

import Foundation

struct LongestConsecutiveSequence {
    static func test() {
        var arr1 = [100, 4, 200, 1, 3, 2, 5, 5]
        print("LongestConsecutiveSequence = \(arr1)")
        var result = transform_ver2(numbers: &arr1)
        assert(result == 5)
        print("LongestConsecutiveSequence length is: \(result)")

        var arr2 = [100, 4, 200, 1, 3, 2]
        print("LongestConsecutiveSequence = \(arr2)")
        result = transform_ver2(numbers: &arr2)
        assert(result == 4)
        print("LongestConsecutiveSequence length is: \(result)")

        var arr3 = [100, 5, 5, 2, 3, 200, 4]
        print("LongestConsecutiveSequence = \(arr3)")
        let result3 = transform_ver1(numbers: &arr3)
        assert(result3 == 4)
        print("LongestConsecutiveSequence length is: \(result3)")
    }
    
    private class NumberStore {
        var numbers: Array<Int> = []
    }
    
    private static func transform_ver2(numbers: inout [Int]) -> Int {
        var numbersMap: Set<Int> = []
        var numbersStoreMap: [Int : NumberStore] = [:]
        var counter = 0

        for number in numbers {

            if numbersMap.contains(number) {
                continue
            }
            
            let number_plus = number + 1
            let number_minus = number - 1

            // receive available store or create it
            var store: NumberStore?

            if numbersMap.contains(number_plus) {
                if let s = numbersStoreMap[number_plus] {
                    store = s
                } else {
                    let s = NumberStore()
                    s.numbers.append(number_plus)
                    numbersStoreMap[number_plus] = s
                    store = s
                }
                numbersStoreMap[number] = store
            }

            if numbersMap.contains(number_minus) {
                if let s = numbersStoreMap[number_minus] {
                    if let prevPlusStore = store {
                        prevPlusStore.numbers.append(contentsOf: s.numbers)
                    } else {
                        store = s
                    }
                } else {
                    let s = store ?? NumberStore()
                    s.numbers.append(number_minus)
                    numbersStoreMap[number_minus] = s
                    store = s
                }
                numbersStoreMap[number] = store
            }
            
            if let s = store {
                s.numbers.append(number)
                if s.numbers.count > counter {
                    counter = s.numbers.count
                }
            }

            // Flag that's passed
            numbersMap.insert(number)
        }

        return counter
    }
    
    private static func transform_ver1(numbers: inout [Int]) -> Int {
        var numbersMap: Set<Int> = []
        for number in numbers {
            numbersMap.insert(number)
        }
        
        var counter = 0
        
        for number in numbers {
            let number_minus = number - 1
            if numbersMap.contains(number_minus) {
                continue
            }
            
            var counterLocal = 1
            var number_plus = number + 1
            while numbersMap.contains(number_plus) {
                counterLocal += 1
                number_plus += 1
            }
            
            if counterLocal > counter {
                counter = counterLocal
            }
        }
        
        return counter
    }
}