class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """

        # Intuition: When using `for i in range(num_ints)` to check for zeros,
        # `i` will end up reaching to the appended zeros,
        # so we need to mark the "end" of checking (which moves forward when a zero is removed).
        # The checking will terminate when we reach the

        i_curr = 0  # marks the int we are checking
        i_end = len(nums) - 1  # marks the (real-time) end of the list
        while i_curr <= i_end:
            if nums[i_curr] == 0:
                nums.pop(i_curr)
                nums.append(0)
                i_end -= 1  # The end moves forward by 1.
            else:
                i_curr += 1

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        
        # Intuition: We go through `t`, and whenever we see a char also appearing in `s`,
        # we cross that char out in `s` (metaphorically)
        # and go on and compare the rest of chars in `t` with the next char in `s`.

        if not s:
            return True  # "" is treated as a subsequence of any strings.

        i_s = 0
        for i_t in range(len(t)):
            if t[i_t] == s[i_s]:
                i_s += 1  # we move on to check the rest of chars in `t` with the next char in `s`
            if i_s >= len(s):
                return True  # we've seen all chars in `s`

        return False

class Solution:
    def maxArea(self, height: List[int]) -> int:

        # Intuition: We set a left border and a right border.
        # By adjusting the left and right wall, we could control the volumn formed.
        # The volumn is also determined by the shorter one of the left & right walls.

        # We start from the left-most wall and right-most wall to get the largest width,
        # and we constantly adjust the shorter wall,
        # expecting that though the width is getting smaller,
        # we would meet a taller wall that gives us a larger volumn.

        i_left = 0
        i_right = len(height) - 1
        max_area = 0

        while i_left < i_right:
            curr_area = min(height[i_left], height[i_right]) * (i_right - i_left)
            max_area = max(max_area, curr_area)  # update

            # Shrink width:
            if height[i_left] < height[i_right]:
                i_left += 1
            else:
                i_right -= 1

        return max_area

class Solution:
    def maxOperations(self, nums: List[int], k: int) -> int:

        # Intuition: This looks similar to the Two Sum problem.
        # We could use Counter() to build a frequency map.

        # freq = {}
        # for num in nums:
        #     freq[num] = freq.get(num, 0) + 1
        freq = Counter(nums)

        operations = 0
        for num in nums:
            complement = k - num
            if freq[num] > 0 and freq[complement] > 0:
                # Skip if there's only one occurrence of itself:
                if num == complement and freq[num] <= 1:
                    continue
                # Do a removal operation:
                operations += 1
                freq[num] -= 1
                freq[complement] -= 1

        return operations

class Solution:
    def findMaxAverage(self, nums: List[int], k: int) -> float:
        # max_avg = sum(nums[0:k])/k
        # for i in range(len(nums)- k + 1):
        #     avg = sum(nums[i:i+k])/k
        #     max_avg = max(avg, max_avg)
        # return max_avg

        # Reflection: computing `sum(nums[i:i+k])/k` consumes too much CPU for each new i.

        curr_sum = max_sum = sum(nums[0:k])
        for i in range(k, len(nums)):
            curr_sum = curr_sum + nums[i] - nums[i-k]
            max_sum = max(curr_sum, max_sum)
        return (max_sum / k)  # computes the avg only at the end

class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        # Intuition: Use a sliding window of length k.
        # Use set for faster lookups.

        vowels = {'a', 'e', 'i', 'o', 'u'}  # Set of vowels for fast lookup
        curr_num_vowels = 0

        # Initial count:
        for i in range(k):
            if s[i] in vowels:
                curr_num_vowels += 1
        max_num_vowels = curr_num_vowels
        
        # Move the sliding window:
        for i in range(1, len(s) - k + 1):
            if s[i-1] in vowels:
                curr_num_vowels -= 1  # removed from the window
            if s[i+k-1] in vowels:
                curr_num_vowels += 1  # added into the window
            max_num_vowels = max(max_num_vowels, curr_num_vowels)
        
        return max_num_vowels

class Solution:
    def longestOnes(self, nums: List[int], k: int) -> int:
        # Intuition:
        # We create a sliding window where there are k 0's.

        left = 0
        max_length = 0
        zero_count = 0
        
        # Move the right bound of sliding window:
        for right in range(len(nums)):
            if nums[right] == 0:
                zero_count += 1
            
            # If there are more than k zeros, shrink the window from the left
            while zero_count > k:
                if nums[left] == 0:
                    zero_count -= 1
                left += 1  # Move left pointer to the right
            
            # Update:
            max_length = max(max_length, right - left + 1)
        
        return max_length

class Solution:
    def longestSubarray(self, nums: List[int]) -> int:

        # Intuition:
        # We specify the longest subarray using a `left` and a `right` pointer.
        # NOTE: To make the algorithm cleaner, we use a for loop to automate the incrementations of `right` and adjust `left` separately.

        left = 0
        max_len = 0
        zero_count = 0
        for right in range(len(nums)):
            if nums[right] == 0:
                zero_count += 1

            # Once zero_count reaches 2,
            # we shrink the window to remove the previous zero:
            while zero_count > 1:
                if nums[left] == 0:
                    zero_count -= 1
                left += 1

            max_len = max(max_len, right - left)

        return max_len

class Solution:
    def largestAltitude(self, gain: List[int]) -> int:
        altitude = 0
        highest = 0
        for rise in gain:
            altitude += rise
            highest = max(highest, altitude)
        return highest

class Solution:
    def pivotIndex(self, nums: List[int]) -> int:
        left_sum = 0
        total_sum = sum(nums)
        for i in range(len(nums)):
            if left_sum == total_sum - nums[i] - left_sum:
                return i
            left_sum += nums[i]
        return -1

class Solution:
    def mergeAlternately(self, word1: str, word2: str) -> str:
        result = []  # more performant than `result = ""`
        i = 0
        while i < len(word1) or i < len(word2):
            if i < len(word1):
                result.append(word1[i])  # more performant than `result += word1[i]`
            if i < len(word2):
                result.append(word2[i])
            i += 1
        return ''.join(result)

        # NOTE: In Python, strings are immutable, meaning every time you perform an operation like result += char, a new string is created in memory. This results in repeated memory allocation and copying of the existing string contents, which becomes costly as the string grows.

class Solution:
    def gcdOfStrings(self, str1: str, str2: str) -> str:

        # Intuition: Simply use gcd() on the string lengths as long as the strings have a GCD.
        # Check: when str1 and str2 have a GCD (str1 = mGCD, str2 = nGCD),
        # then str1 + str2 = (m + n)GCD = str2 + str1.
        
        if str1 + str2 != str2 + str1:
            return ""
        return str1[:math.gcd(len(str1), len(str2))]  # or `str2[:math.gcd(len(str1), len(str2))]`

class Solution:
    def kidsWithCandies(self, candies: List[int], extraCandies: int) -> List[bool]:
        # Intuition: For each kid, find the number of candies needed to make him/her
        # the kid with the most candies.

        max_num_candies = max(candies)  # the max num of candies
    
        return [(num_candies + extraCandies >= max_num_candies) for num_candies in candies]
        # Syntax ("list comprehesion"): [<expression> for <item> in <iterable> if <condition>]
        # which can also be done using a for loop.

class Solution:
    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
        # Intuition: Given `flowerbed` alone, the max num of additional flowers
        # can already be determined.

        num_allowed = 0
        for i in range(len(flowerbed)):
            if flowerbed[i] == 0:
                # if left is unoccupied and right is unoccupied -> plant flower:
                if (i == 0 or flowerbed[i-1] == 0) and (i == len(flowerbed) - 1 or flowerbed[i+1] == 0):
                    # print(i)
                    flowerbed[i] = 1
                    num_allowed += 1
        return n <= num_allowed

class Solution:
    def reverseVowels(self, s: str) -> str:

        # Intuition:
        # "Reversing" is basically swapping against the central element.
        # We can use the two-pointer method to avoid using `indices` in Solution 1.

        vowels = set("aeiouAEIOU")
        s = list(s)  # Convert string to list for mutability
        left, right = 0, len(s) - 1

        while left < right:
            # Move `left` and `right` separately until they both point at vowels.
            while left < right and s[left] not in vowels:
                left += 1
            while left < right and s[right] not in vowels:
                right -= 1
            
            # Swap:
            s[left], s[right] = s[right], s[left]
            left += 1
            right -= 1

        return "".join(s)  # Convert list back to string

class Solution:
    def reverseWords(self, s: str) -> str:
        words = s.split()
        words.reverse()  # reversed as a list
        return ' '.join(words)  # joined with ' '

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:

        # Intuition:
        # We notice to compute the product for each integer in `nums`,
        # we would have to multiply all integers before and after it.
        # e.g. For both `nums[5]` and `nums[6]`, we will need to compute the product of `nums[0]` to `nums[4]`, which are redundant calculations.

        # We use two passes, which is still O(n).
        # For each integer in `nums`,
        # the forward pass computes the product of all integers before it and
        # the backward pass computes the product of all integers after it.

        result = [1] * len(nums)
        
        # Forward pass:
        product = 1
        for i in range(len(nums)):
            result[i] = product
            product *= nums[i]  # build up the "prefix product"
        
        # Backward pass:
        product = 1
        for i in range(len(nums)-1, -1, -1):
            result[i] *= product
            product *= nums[i]  # build up the "suffix product"
        
        return result

class Solution:
    def increasingTriplet(self, nums: List[int]) -> bool:

        # Intuition: 
        # Since the question only asks for a True/False answer instead of all triple of indices, the algorithm can be simplified significantly.
        # To check for the existence of such triples, the key idea is to find the 1st and 2nd minimum values seen so far. For example, for [2, 4, 1, 3, _], to make a triple exist, we only have to make sure _ is larger than 1 and 3 without having to comparing it with 2 or 4.

        min_1 = float('inf')  # the smallest
        min_2 = float('inf')  # the 2nd smallest

        # (i < j < k) naturally holds in a for loop
        for num in nums:
            if num <= min_1:
                min_1 = num
            elif num <= min_2:  # min_1 < num <= min_2
                min_2 = num
            else:  # num > min_2
                return True

        return False

class Solution:
    def compress(self, chars: List[str]) -> int:

        # Intuition: We go through the list and modify it in-place.
        # Again, `for i in range(len(chars))` won't work since `chars` will be modified inside the for loop.

        # Helper function (for avoiding boilerplate code):
        # For pass-by-reference, Python lists are mutable,
        # but Python integers are immutable (needs to be returned explicitly).
        #   i: the index right after the last duplicate of `prev_char`
        #   count: the number of occurrences of `prev_char`
        def compress_for_prev_char(chars, i, count):
            # 1. Remove all duplicates (except the first occurrence):
            chars[(i-count+1):i] = []
            i -= (count - 1)  # adjusts `i` after the deletion

            # 2. Append the count as digits to `chars` (conditionally):
            if count > 1:
                for idx, digit in enumerate(str(count)):
                    chars.insert(i + idx, digit)
                i += len(str(count))  # adjusts `i` after the insertion
            return i

        i = 0
        prev_char = ""
        count = 0
        while i <= len(chars) - 1:
            temp = chars[i]

            if not prev_char or chars[i] == prev_char:  # Simply count:
                count += 1
            else:  # Compress the list for the last char:
                i = compress_for_prev_char(chars, i, count)
                count = 1  # reset count for this new (different) char:

            # Update:
            i += 1
            prev_char = temp

            # Handle the exit:
            if i >= len(chars):
                i = compress_for_prev_char(chars, i, count)
                break

        return len(chars)