leetcode: 128. Longest Consecutive Sequence

problem

• https://leetcode.com/problems/longest-consecutive-sequence

set

class Solution {
    fun longestConsecutive(nums: IntArray): Int {
        val set = nums.toSet()
        var answer = 0
        for (num in set) {
            if (!set.contains(num - 1)) { // is start position?
                var target = num + 1
                while (set.contains(target)) {
                    target++ // forward
                }
                answer = maxOf(answer, target - num) // get max length
            }
        }
        return answer
    }
}

hash map

class Solution {
    fun longestConsecutive(nums: IntArray): Int {
        val hashMap = mutableMapOf<Int, Int>()
        var answer = 0
        for (num in nums) {
            if (hashMap[num] != null) continue // pass duplicated number
            
            val lLen = hashMap[num - 1] ?: 0 // get left adjcent consecutive sequence length
            val rLen = hashMap[num + 1] ?: 0 // get left adjcent consecutive sequence length
            val len = lLen + rLen + 1 // get length include itself
            
            // store consecutive sequence length
            hashMap[num] = len
            hashMap[num - lLen] = len
            hashMap[num + rLen] = len
            
            answer = maxOf(answer, len)            
        }
        return answer
    }
}

union find

class Solution {
    fun longestConsecutive(nums: IntArray): Int {
        val size = nums.size
        val parents = IntArray(size) { 0 }
        val lengths = IntArray(size) { 1 } // include itself
        for (i in 0 until size) {
            parents[i] = i
        }
        
        val valToIndex = mutableMapOf<Int, Int>()
        for (i in 0 until size) {
            if (valToIndex[nums[i]] != null) continue // pass duplicated value
            
            if (valToIndex[nums[i] - 1] != null) { // consecutive sequence
                union(parents, lengths, i, valToIndex[nums[i] - 1]!!)
            }
            if (valToIndex[nums[i] + 1] != null) { // consecutive sequence
                union(parents, lengths, i, valToIndex[nums[i] + 1]!!)
            }
            valToIndex[nums[i]] = i
        }
        
        var answer = 0
        for (i in 0 until size) {
            answer = maxOf(answer, lengths[i])
        }
        return answer
    }
    
    fun union(parents: IntArray, lengths: IntArray, x: Int, y: Int) {
        val parentX = getParent(parents, x)
        val parentY = getParent(parents, y)
        if (parentX != parentY) {
            parents[parentX] = parentY
            lengths[parentY] += lengths[parentX] // merge length
        }
    }
    
    fun getParent(parents: IntArray, x: Int): Int {
        if (parents[x] == x) return x
        parents[x] = getParent(parents, parents[x])
        return parents[x]
    }
}