A. Min Max Game (opens new window)

Merge list accordingly, until there is only 1 element left.

DETAILS

def minMaxGame(self, A: List[int]) -> int:
        while len(A) > 1:
            nxt = [0] * (len(A) // 2)
            for i in range(len(nxt)):
                if i %2==0:
                    nxt[i] = min(A[i*2], A[i*2+1])
                else:
                    nxt[i] = max(A[i*2], A[i*2+1])
            A=nxt.copy()
        return A[0]

B. Partition Array Such That Maximum Difference Is K (opens new window)

Sort array and start iteration from a_0. If aj is larger than ai by more than k, we have one extra subarray of ai, ai+1, ... aj-1.

DETAILS

def partitionArray(self, nums: List[int], k: int) -> int:
        nums.sort()
        n, minn = 1, nums[0]
        for num in nums[1:]:
            if num - minn > k:
                n+=1
                minn = num
        return n

C. Replace Elements in an Array (opens new window)

Use hashmap to store the value-key pair, change value in each queries. Finally, restore the original order using the keys.

DETAILS

def arrayChange(self, A: List[int], O: List[List[int]]) -> List[int]:
        d, res = {a : i for i,a in enumerate(A)}, [0] * len(A)
        for i,j in O:
            d[j]=d[i]
            del d[i]
        for key in d.keys():
            res[d[key]]=key
        return res

D. Design a Text Editor (opens new window)

String operation, maintain a pointer as the cursor.

DETAILS

class TextEditor:
    def __init__(self):
        self.i, self.s = 0, ""
    
    def addText(self, text: str) -> None:
        if not self.s:
            self.s = text
        else: 
            self.s = self.s[:self.i] + text + self.s[self.i:]
        self.i + =len(text)

    def deleteText(self, k: int) -> int:
        prev, res = max(0, self.i - k),min(k, self.i)
        self.s = self.s[:prev] + self.s[self.i:]
        self.i -= res
        return res
    
    def cursorLeft(self, k: int) -> str:
        self.i -= k
        self.i = max(self.i, 0)
        if self.i >=  10:
            return self.s[self.i-10 : self.i]
        else:
            return self.s[:self.i]

    def cursorRight(self, k: int) -> str:
        self.i += k
        self.i = min(self.i, len(self.s))
        if self.i >= 10:
            return self.s[self.i-10 : self.i]
        else:
            return self.s[:self.i]