LeetCode/kt/construct-the-lexicographically-largest-valid-sequence.kt

class Solution {
    private data class LargestSequence(val n: Int) {
        val result: IntArray = IntArray(n * 2 - 1) { 0 }
        private val isUsed: BooleanArray = BooleanArray(n + 1) { false }

        fun find(i: Int): Boolean =
            when {
                // All positions were filled
                i == result.size -> true

                // Already filled, can skip
                result[i] != 0 -> find(i + 1)
                else -> {
                    (n downTo 1).asSequence().filter {
                        !isUsed[it]
                    }.forEach { toPlace ->
                        isUsed[toPlace] = true
                        result[i] = toPlace

                        if (toPlace == 1) {
                            if (find(i + 1)) {
                                return true
                            }
                        } else if (i + toPlace < result.size && result[i + toPlace] == 0) {
                            result[i + toPlace] = toPlace

                            if (find(i + 1)) {
                                return true
                            }

                            result[i + toPlace] = 0
                        }

                        result[i] = 0
                        isUsed[toPlace] = false
                    }

                    false
                }
            }
    }

    fun constructDistancedSequence(n: Int): IntArray =
        LargestSequence(n).let {
            it.find(0)
            it.result
        }
}