LeetCode in Kotlin

2097. Valid Arrangement of Pairs

Hard

You are given a 0-indexed 2D integer array pairs where pairs[i] = [starti, endi]. An arrangement of pairs is valid if for every index i where 1 <= i < pairs.length, we have endi-1 == starti.

Return any valid arrangement of pairs.

Note: The inputs will be generated such that there exists a valid arrangement of pairs.

Example 1:

Input: pairs = [[5,1],[4,5],[11,9],[9,4]]

Output: [[11,9],[9,4],[4,5],[5,1]]

Explanation:

This is a valid arrangement since end_i-1 always equals start_i.

end₀ = 9 == 9 = start₁

end₁ = 4 == 4 = start₂

end₂ = 5 == 5 = start₃

Example 2:

Input: pairs = [[1,3],[3,2],[2,1]]

Output: [[1,3],[3,2],[2,1]]

Explanation:

This is a valid arrangement since end_i-1 always equals start_i.

end₀ = 3 == 3 = start₁

end₁ = 2 == 2 = start₂

The arrangements [[2,1],[1,3],[3,2]] and [[3,2],[2,1],[1,3]] are also valid.

Example 3:

Input: pairs = [[1,2],[1,3],[2,1]]

Output: [[1,2],[2,1],[1,3]]

Explanation:

This is a valid arrangement since end_i-1 always equals start_i.

end₀ = 2 == 2 = start₁

end₁ = 1 == 1 = start₂

Constraints:

• 1 <= pairs.length <= 105
• pairs[i].length == 2
• 0 <= starti, endi <= 109
• starti != endi
• No two pairs are exactly the same.
• There exists a valid arrangement of pairs.

Solution

import java.util.LinkedList
import java.util.Queue

@Suppress("NAME_SHADOWING")
class Solution {
    fun validArrangement(pairs: Array<IntArray>): Array<IntArray> {
        val inOutedge = HashMap<Int, IntArray>()
        val adList = getAdList(pairs, inOutedge)
        val start = getStart(inOutedge)
        val res = Array(pairs.size) { IntArray(2) }
        getRes(start, adList, res, pairs.size - 1)
        return res
    }

    private fun getAdList(
        pairs: Array<IntArray>,
        inOutEdge: HashMap<Int, IntArray>,
    ): HashMap<Int, Queue<Int>> {
        val adList = HashMap<Int, Queue<Int>>()
        for (pair in pairs) {
            val s = pair[0]
            val d = pair[1]
            val set = adList.computeIfAbsent(s) { _: Int? -> LinkedList() }
            set.add(d)
            val sEdgeCnt = inOutEdge.computeIfAbsent(s) { _: Int? -> IntArray(2) }
            val dEdgeCnt = inOutEdge.computeIfAbsent(d) { _: Int? -> IntArray(2) }
            sEdgeCnt[1]++
            dEdgeCnt[0]++
        }
        return adList
    }

    private fun getRes(k: Int, adList: HashMap<Int, Queue<Int>>, res: Array<IntArray>, idx: Int): Int {
        var idx = idx
        val edges = adList[k] ?: return idx
        while (edges.isNotEmpty()) {
            val edge = edges.poll()
            idx = getRes(edge, adList, res, idx)
            res[idx--] = intArrayOf(k, edge)
        }
        return idx
    }

    private fun getStart(map: HashMap<Int, IntArray>): Int {
        var start = -1
        for ((k, value) in map) {
            val inEdge = value[0]
            val outEdge = value[1]
            start = k
            if (outEdge - inEdge == 1) {
                return k
            }
        }
        return start
    }
}

This site is open source. Improve this page.