Input: arr = [1,2,2,6,6,6,6,7,10]
Output: 6

class Solution {
    fun findSpecialInteger(arr: IntArray): Int {
        val counts = mutableMapOf<Int, Int>()
        val target = arr.size / 4
        for (num in arr) {
            counts[num] = counts.getOrDefault(num, 0) + 1
            if (counts[num]!! > target) {
                return num
            }
        }
        return -1
    }
}

Input: s = "egg", t = "add"
Output: true

class Solution {
    fun isIsomorphic(s: String, t: String): Boolean {
        val mappingStoT = mutableMapOf<Char, Char>()
        val mappingTtoS = mutableMapOf<Char, Char>()

        for (i in s.indices) {
            val c1 = s[i]
            val c2 = t[i]

            if (!mappingStoT.containsKey(c1) && !mappingTtoS.containsKey(c2)) {
                mappingStoT[c1] = c2
                mappingTtoS[c2] = c1
            } else if (mappingStoT[c1] != c2 || mappingTtoS[c2] != c1) {
                return false
            }
        }

        return true
    }
}

Input: digits = ["1","3","5","7"], n = 100
Output: 20

class Solution {
    fun atMostNGivenDigitSet(digits: Array<String>, n: Int): Int {
        val s = n.toString()
        val K = s.length
        val dp = IntArray(K + 1)
        dp[K] = 1

        for (i in K - 1 downTo 0) {
            for (d in digits) {
                if (d[0] < s[i]) {
                    dp[i] += Math.pow(digits.size.toDouble(), (K - i - 1).toDouble()).toInt()
                } else if (d[0] == s[i]) {
                    dp[i] += dp[i + 1]
                }
            }
        }

        for (i in 1 until K) {
            dp[0] += Math.pow(digits.size.toDouble(), i.toDouble()).toInt()
        }

        return dp[0]
    }
}

Input: arr = [1,5,7,8,5,3,4,2,1], difference = -2
Output: 4
Explanation: The longest arithmetic subsequence is [7,5,3,1].

class Solution {
    fun longestSubsequence(arr: IntArray, difference: Int): Int {
        val dp = mutableMapOf<Int, Int>()
        var answer = 1
        
        for (a in arr) {
            val beforeA = dp.getOrDefault(a - difference, 0)
            dp[a] = beforeA + 1
            answer = maxOf(answer, dp[a]!!)
        }
        
        return answer
    }
}

Input: head = [1,2,3], k = 5
Output: [[1],[2],[3],[],[]]

class ListNode(var `val`: Int) {
    var next: ListNode? = null
}

fun splitListToParts(root: ListNode?, k: Int): Array<ListNode?> {
    var length = 0
    var node = root
    while (node != null) {
        length++
        node = node.next
    }

    val partLength = length / k
    val extraParts = length % k

    val parts = Array<ListNode?>(k) { null }
    node = root
    for (i in 0 until k) {
        val partHead = node
        val partSize = partLength + if (i < extraParts) 1 else 0
        for (j in 0 until partSize - 1) {
            if (node != null) node = node.next
        }
        if (node != null) {
            val nextPart = node.next
            node.next = null
            node = nextPart
        }
        parts[i] = partHead
    }

    return parts
}

Input: n = 3  
Output: ["((()))","(()())","(())()","()(())","()()()"]  

class Solution {
    fun generateParenthesis(n: Int): List<String> {
        val result = mutableListOf<String>()
        generate("", n, n, result)
        return result
    }

    private fun generate(current: String, left: Int, right: Int, result: MutableList<String>) {
        if (left == 0 && right == 0) {
            result.add(current)
            return
        }
        if (left > 0) generate(current + "(", left - 1, right, result)
        if (right > left) generate(current + ")", left, right - 1, result)
    }
}

Input: nums = [1], k = 0
Output: 0

class Solution {
    fun smallestRangeII(nums: IntArray, k: Int): Int {
        val nums = nums.sorted()
        val n = nums.size
        var result = nums[n - 1] - nums[0]
        val minVal = nums[0]
        val maxVal = nums[n - 1]

        for (i in 0 until n - 1) {
            val high = maxOf(nums[i] + k, maxVal - k)
            val low = minOf(nums[i + 1] - k, minVal + k)
            result = minOf(result, high - low)
        }

        return result
    }
}

Input: mat = [[0,1,1,0],[0,1,1,0],[0,0,0,1]]
Output: 3

class Solution {
    fun longestLine(mat: Array<IntArray>): Int {
        if (mat.isEmpty() || mat[0].isEmpty()) return 0
        
        val m = mat.size
        val n = mat[0].size
        var maxLength = 0
        
        val horizontal = Array(m) { IntArray(n) }
        val vertical = Array(m) { IntArray(n) }
        val diagonal = Array(m) { IntArray(n) }
        val antiDiagonal = Array(m) { IntArray(n) }
        
        for (i in mat.indices) {
            for (j in mat[0].indices) {
                if (mat[i][j] == 1) {
                    horizontal[i][j] = (if (j > 0) horizontal[i][j - 1] else 0) + 1
                    vertical[i][j] = (if (i > 0) vertical[i - 1][j] else 0) + 1
                    diagonal[i][j] = (if (i > 0 && j > 0) diagonal[i - 1][j - 1] else 0) + 1
                    antiDiagonal[i][j] = (if (i > 0 && j < n - 1) antiDiagonal[i - 1][j + 1] else 0) + 1
                    
                    maxLength = maxOf(maxLength, horizontal[i][j], vertical[i][j], diagonal[i][j], antiDiagonal[i][j])
                }
            }
        }
        
        return maxLength
    }
}

Input: a = "aba", b = "cdc"
Output: 3
Explanation: One longest uncommon subsequence is "aba" because "aba" is a subsequence of "aba" but not "cdc".
Note that "cdc" is also a longest uncommon subsequence.

class Solution {
    fun findLUSlength(a: String, b: String): Int {
        return if (a == b) {
            -1
        } else {
            maxOf(a.length, b.length)
        }
    }
}

Input: heights = [2,1,5,6,2,3]
Output: 10
Explanation: The above is a histogram where width of each bar is 1.
The largest rectangle is shown in the red area, which has an area = 10 units.

class Solution {
    fun repeatedSubstringPattern(s: String): Boolean {
        val n = s.length
        for (i in 1..n / 2) {
            if (n % i == 0) {
                val pattern = s.substring(0, i).repeat(n / i)
                if (s == pattern) {
                    return true
                }
            }
        }
        return false
    }
}

Input
["TopVotedCandidate", "q", "q", "q", "q", "q", "q"]
[[[0, 1, 1, 0, 0, 1, 0], [0, 5, 10, 15, 20, 25, 30]], [3], [12], [25], [15], [24], [8]]
Output
[null, 0, 1, 1, 0, 0, 1]

class TopVotedCandidate(persons: IntArray, times: IntArray) {
    private val times = times
    private val leaders = mutableListOf<Int>()

    init {
        val counts = mutableMapOf<Int, Int>()
        var leader = -1

        for (person in persons) {
            counts[person] = counts.getOrDefault(person, 0) + 1
            if (counts[person]!! >= counts.getOrDefault(leader, 0)) {
                leader = person
            }
            leaders.add(leader)
        }
    }

    fun q(t: Int): Int {
        var left = 0
        var right = times.size - 1
        while (left < right) {
            val mid = (left + right + 1) / 2
            if (times[mid] <= t) {
                left = mid
            } else {
                right = mid - 1
            }
        }
        return leaders[left]
    }
}

Input: wordsDict = ["practice", "makes", "perfect", "coding", "makes"], word1 = "coding", word2 = "practice"
Output: 3

class Solution {
    fun shortestDistance(words: Array<String>, word1: String, word2: String): Int {
        var minDistance = words.size
        for (i in words.indices) {
            if (words[i] == word1) {
                for (j in words.indices) {
                    if (words[j] == word2) {
                        minDistance = kotlin.math.min(minDistance, kotlin.math.abs(i - j))
                    }
                }
            }
        }
        return minDistance
    }
}

Input: list1 = [10,1,13,6,9,5], a = 3, b = 4, list2 = [1000000,1000001,1000002]
Output: [10,1,13,1000000,1000001,1000002,5]
Explanation: We remove the nodes 3 and 4 and put the entire list2 in their place. The blue edges and nodes in the above figure indicate the result.

class Solution {
    fun mergeInBetween(list1: ListNode?, a: Int, b: Int, list2: ListNode?): ListNode? {
        val mergeArray = mutableListOf<Int>()
        var index = 0
        var current1 = list1
        
        while (index < a) {
            mergeArray.add(current1!!.`val`)
            current1 = current1.next
            index++
        }
        
        var current2 = list2
        while (current2 != null) {
            mergeArray.add(current2.`val`)
            current2 = current2.next
        }
        
        while (index < b + 1) {
            current1 = current1!!.next
            index++
        }
        
        while (current1 != null) {
            mergeArray.add(current1.`val`)
            current1 = current1.next
        }
        
        var resultList: ListNode? = null
        for (val in mergeArray.asReversed()) {
            val newNode = ListNode(val, resultList)
            resultList = newNode
        }
        
        return resultList
    }
}

Input: nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2
Output: 6

class Solution {
    fun longestOnes(nums: IntArray, k: Int): Int {
        var left = 0
        var maxOnes = 0
        var zeroCount = 0

        for (right in nums.indices) {
            if (nums[right] == 0) {
                zeroCount++
            }

            while (zeroCount > k) {
                if (nums[left] == 0) {
                    zeroCount--
                }
                left++
            }

            maxOnes = maxOf(maxOnes, right - left + 1)
        }

        return maxOnes
    }
}

Input: nums = [4,2,3], k = 1
Output: 5

class Solution {
    fun clumsy(n: Int): Int {
        if (n == 0) return 0
        if (n == 1) return 1
        if (n == 2) return 2 * 1
        if (n == 3) return 3 * 2 / 1
        
        var res = n * (n - 1) / (n - 2)
        var n = n - 3
        if (n > 0) res += n
        n -= 1
        
        while (n > 0) {
            res -= n * (n - 1) / (n - 2)
            n -= 3
            if (n > 0) res += n
            n -= 1
        }
        
        return res
    }
}

Input: s = "DID"
Output: 5

class Solution {
    fun numPermsDISequence(s: String): Int {
        val MOD = 1_000_000_007
        val n = s.length
        val dp = Array(n + 1) { IntArray(n + 1) }
        dp[0][0] = 1

        for (i in 1..n) {
            for (j in 0..i) {
                if (s[i - 1] == 'D') {
                    for (k in j until i) {
                        dp[i][j] = (dp[i][j] + dp[i - 1][k]) % MOD
                    }
                } else {
                    for (k in 0 until j) {
                        dp[i][j] = (dp[i][j] + dp[i - 1][k]) % MOD
                    }
                }
            }
        }

        var result = 0
        for (j in 0..n) {
            result = (result + dp[n][j]) % MOD
        }

        return result
    }
}

Input: arrays = [[1,2,3],[4,5],[1,2,3]]
Output: 4

fun maxDistance(arrays: List<List<Int>>): Int {
    var minVal = arrays[0][0]
    var maxVal = arrays[0].last()
    var maxDistance = 0
    
    for (i in 1 until arrays.size) {
        maxDistance = maxOf(maxDistance, kotlin.math.abs(arrays[i].last() - minVal), kotlin.math.abs(arrays[i][0] - maxVal))
        minVal = minOf(minVal, arrays[i][0])
        maxVal = maxOf(maxVal, arrays[i].last())
    }
    
    return maxDistance
}