leetcode: 406. Queue Reconstruction by Height

problem

• https://leetcode.com/problems/queue-reconstruction-by-height/

sort

class Solution {
    fun reconstructQueue(people: Array<IntArray>): Array<IntArray> {
        // sort by h decreasing order. then, by k increasing order.
        // k takes part of index of insertion.
        people.sortWith(compareBy({-it[0]}, {it[1]}))
        val result = mutableListOf<IntArray>()
        for (person in people) {
            result.add(person[1], person)
        }
        return result.toTypedArray()
    }
}

binary tree

data class Node(val person: IntArray, var precedePersonIncludeMe: Int, var left: Node?, var right: Node?)

class Solution {
    fun reconstructQueue(people: Array<IntArray>): Array<IntArray> {
        // sort by h decreasing order. then, by k increasing order.    
        people.sortWith(compareBy({-it[0]}, {it[1]}))
        val root = Node(people[0], 1, null, null)
        val size = people.size
        for (i in 1 until size) {
            // If the number of precede person include target node, go to left with increasing precede person one.
            // Else go to right with decreasing the number of precede person which means does not consider already passed precede person.
            insertPerson(root, people[i], people[i][1])
        }
        val result = mutableListOf<IntArray>()
        traverse(root, result)
        return result.toTypedArray()
    }
    
    fun insertPerson(root: Node, person: IntArray, numOfPrecedePerson: Int) {
        if (numOfPrecedePerson < root.precedePersonIncludeMe) {
            if (root.left == null) {
                root.left = Node(person, 1, null, null)
            } else {
                insertPerson(root.left!!, person, numOfPrecedePerson)
            }
            root.precedePersonIncludeMe += 1
        } else { // numOfPrecedePerson >= root.precedePersonIncludeMe
            if (root.right == null) {
                root.right = Node(person, 1, null, null)
            } else {
                insertPerson(root.right!!, person, numOfPrecedePerson - root.precedePersonIncludeMe)
            }
        }
    }
    
    fun traverse(root: Node?, result: MutableList<IntArray>) {
        root ?: return
        traverse(root.left, result)
        result.add(root.person)
        traverse(root.right, result)
    }
}