Golang LIS Binary Search O(nlog(n)) time complexity
\nfunc kIncreasing(arr []int, k int) int {\n    buckets := partition(arr, k)\n    \n    // T -> O(n)\n    // S -> O(n)\n    var numberOfOperations int\n    for 
```\nfunc kIncreasing(arr []int, k int) int {\n    buckets := partition(arr, k)\n    \n    // T -> O(n)\n    // S -> O(n)\n    var numberOfOperations int\n    for _, bucket := range buckets {\n        numberOfOperations += longestIncreasingSequence(bucket)\n    }\n    \n    return numberOfOperations\n}\n\n// T -> O(n)\n// S -> O(n)\nfunc partition(arr []int, k int) [][]int {\n    var buckets = make([][]int, 0, k)\n    for i := 0; i < k; i++ {\n        buckets = append(buckets, []int{})\n    }\n    \n    for i := 0; i < len(arr); i++ {\n        bucket := i % k\n        buckets[bucket] = append(buckets[bucket], arr[i])\n    }\n    \n    return buckets\n}\n\nfunc longestIncreasingSequence(array []int) int {\n    if len(array) == 0 {\n        return 0\n    }\n    \n    // T -> O(nlog(n)) where `n` is the length of the array.\n    // S -> O(n) worst case the sequence could be the same size as the original array.\n    var sequence = []int{array[0]}\n    for i := 1; i < len(array); i++ {\n        \n        currentValue := array[i]\n        \n        if currentValue >= sequence[len(sequence)-1] {\n            sequence = append(sequence, currentValue)\n            continue\n        }\n        \n        firstIncreasingElement := bisectLeft(sequence, currentValue)\n        if sequence[firstIncreasingElement] == currentValue {\n            firstIncreasingElement++\n        }\n        \n        sequence[firstIncreasingElement] = currentValue\n    }\n    \n    \n    return len(array) - len(sequence)\n}\n\n// T -> O(log(n))\n// S -> O(1)\nfunc bisectLeft(array []int, target int) int {\n    l, r := 0, len(array)\n    \n    for l < r {\n        m := (l + r) / 2\n        \n        switch {\n        case target == array[m]:\n            return m\n        case target <= array[m]:\n            r = m\n        default:\n            l = m+ 1\n        }\n    }\n    \n    return l\n}\n```\n\nHere we do the following:\n1. Partition the array into buckets based on `k` \n2. Perform the LIS (longest increasing subsequence) algorithm on each bucket, with a slight modification\n3. Since the operations cannot be swaps, rather than replace an element in the array with a positive number - we recognise that to make the entire array increasing, we need to make\n    len(array) - len(longest increasing subsequence) operations in order to make the full array increasing.
[]