problems

• https://leetcode.com/problems/min-max-game/
• https://leetcode.com/problems/partition-array-such-that-maximum-difference-is-k/
• https://leetcode.com/problems/replace-elements-in-an-array/
• https://leetcode.com/problems/design-a-text-editor/

2293. Min Max Game

O(N) space solution (recursion)

class Solution {
    fun minMaxGame(nums: IntArray): Int {
        val size = nums.size;
        if (size == 1) return nums[0];
        
        val newNums = IntArray(size / 2) { 0 };
        var index = 0;
        for (i in  0 until size step 2) {
            if (index % 2 == 0) {
                newNums[index++] = minOf(nums[i], nums[i + 1]);
            } else {
                newNums[index++] = maxOf(nums[i], nums[i + 1]);
            }
        }
        return minMaxGame(newNums);
    }
}

O(1) space solution (iteration)

class Solution {
    fun minMaxGame(nums: IntArray): Int {
        var size = nums.size
        while (size > 1) {
            for (i in 0 until size / 2) {
                if (i % 2 == 0) nums[i] = minOf(nums[2 * i], nums[2 * i + 1])
                else nums[i] = maxOf(nums[2 * i], nums[2 * i + 1])
            }
            size /= 2
        }
        return nums[0]
    }
}

2294. Partition Array Such That Maximum Difference Is K

O(N) space

class Solution {
    fun partitionArray(nums: IntArray, k: Int): Int {
        val size = nums.size;
        val sorted = nums.sorted();
        var minIndex = 0;
        var maxIndex = 0;
        var partition = 0;
        while (maxIndex < size) {
            if (sorted[maxIndex] - sorted[minIndex] <= k) {
                maxIndex++;
            } else {
                partition++;
                minIndex = maxIndex;
            }
        }
        partition++;
        return partition;
    }
}

O(1) space

class Solution {
    fun partitionArray(nums: IntArray, k: Int): Int {
        nums.sort()
        var answer = 1
        var end = nums[0]
        val size = nums.size
        
        for (i in 1 until size) {
            if (nums[i] - end > k) {
                answer++
                end = nums[i]
            }
        }
        return answer
    }
}

2295. Replace Elements in an Array

O(N) time, O(M) space

class Solution {
    fun arrayChange(nums: IntArray, operations: Array<IntArray>): IntArray {
        val table = mutableMapOf<Int, Int>();
        nums.forEachIndexed { index, num -> 
            table[num] = index;
        }
        val opSize = operations.size;
        for (i in 0 until opSize) {
            val old = operations[i][0];
            val new = operations[i][1];
            val index = table[old]!!;
            table[new] = index;
            nums[index] = new;
        }    
        return nums;
    }
}

2296. Design a Text Editor

two stacks

class TextEditor() {
    private val stack1 = mutableListOf<Char>();
    private val stack2 = mutableListOf<Char>();
    
    fun addText(text: String) {
        text.forEach { c ->
            stack1.add(c);
        }
    }

    fun deleteText(k: Int): Int {
        var deleted = 0;
        for (i in 0 until k) {
            if (stack1.isEmpty()) return deleted;
            stack1.removeAt(stack1.size - 1);
            deleted++;
        }
        return deleted;
    }

    fun cursorLeft(k: Int): String {
        val sb = StringBuilder();
        for (i in 0 until k) {
            if (stack1.isEmpty()) break;
            val c = stack1.last();
            stack1.removeAt(stack1.size - 1);
            stack2.add(c);
        }
        var start = 0;
        if (stack1.size >= 10) {
            start = stack1.size - 10;      
        }
        for (i in start until stack1.size) {
            sb.append(stack1[i]);
        }
        return sb.toString();
    }

    fun cursorRight(k: Int): String {
        val sb = StringBuilder();
        for (i in 0 until k) {
            if (stack2.isEmpty()) break;
            val c = stack2.last();
            stack2.removeAt(stack2.size - 1);
            stack1.add(c);
        }
        var start = 0;
        if (stack1.size >= 10) {
            start = stack1.size - 10;      
        }
        for (i in start until stack1.size) {
            sb.append(stack1[i]);
        }
        return sb.toString();
    }

}

/**
 * Your TextEditor object will be instantiated and called as such:
 * var obj = TextEditor()
 * obj.addText(text)
 * var param_2 = obj.deleteText(k)
 * var param_3 = obj.cursorLeft(k)
 * var param_4 = obj.cursorRight(k)
 */

one string builder

class TextEditor() {
    val sb = StringBuilder()
    var pos = 0
    
    fun addText(text: String) {
        sb.insert(pos, text)
        pos += text.length
    }

    fun deleteText(k: Int): Int {    
        val deleted = if (k > pos) pos else k
        sb.delete(pos - deleted, pos)
        pos -= deleted
        return deleted        
    }

    fun cursorLeft(k: Int): String {
        pos = if (k > pos) 0 else pos - k
        val start = if (pos - 10 > 0) pos - 10 else 0
        return sb.substring(start, pos)
    }

    fun cursorRight(k: Int): String {
        val size = sb.length
        pos = if (pos + k > size) size else pos + k
        val start = if (pos - 10 > 0) pos - 10 else 0
        return sb.substring(start, pos)
    }

}

/**
 * Your TextEditor object will be instantiated and called as such:
 * var obj = TextEditor()
 * obj.addText(text)
 * var param_2 = obj.deleteText(k)
 * var param_3 = obj.cursorLeft(k)
 * var param_4 = obj.cursorRight(k)
 */