Two Pointers

# Time complexity: O(n)
# Space complexity: O(1)
def isPalindrome(s: str) -> bool:
    start = 0
    end = len(s) - 1
    s = s.lower()
    while start < end:
        if not s[start].isalnum():
            start += 1
        elif not s[end].isalnum():
            end -= 1
        elif s[start] == s[end]:
            start += 1
            end -= 1
        else:
            return False
    return True

# Time complexity: O(n)
# Space complexity: O(1)
def isSubsequence(s: str, t: str) -> bool:
    si = ti = 0

    while si < len(s) and ti < len(t):
        if s[si] == t[ti]:
            si += 1
        ti += 1

    return si == len(s)

# Time complexity: O(n)
# Space complexity: O(1)
def twoSum(numbers: List[int], target: int) -> List[int]:
    start, end = 0, len(numbers) - 1
    while start < end:
        currSum = numbers[start] + numbers[end]
        if currSum == target:
            return [start + 1, end + 1]
        if currSum < target:
            start += 1
        else:
            end -= 1

# Time complexity: O(n)
# Space complexity: O(1)
def maxArea(height: List[int]) -> int:
    start, end = 0, len(height) - 1
    answer = 0

    while start < end:
        answer = max(answer, (end - start) * min(height[start], height[end]))
        # Keep the pointer with a greater value
        if height[start] < height[end]:
            start += 1
        # In the case of height[start] == height[end],
        #   the pointer to move does not matter because
        #   regardless of the next pointer's value,
        #   the calculated area will never be greater.
        else:
            end -= 1
    return answer

# Time complexity: O(n^2)
# Space complexity: O(n)
def threeSum(nums: List[int]) -> List[List[int]]:
    answer = set()
    nums.sort()
    i = 0

    # Essentially 2Sum with an extra loop and dynamic target
    while i < len(nums):
        target = -1 * nums[i]
        start, end = i + 1, len(nums) - 1

        while start < end:
            currSum = nums[start] + nums[end]
            if currSum > target:
                end -= 1
            elif currSum < target:
                start += 1
            else:
                triplet = tuple(sorted([nums[i], nums[start], nums[end]]))
                answer.add(triplet)
                # Skip duplicates from front and back
                while start < end and nums[start] == triplet[1]:
                    start += 1
                while start < end and nums[end] == triplet[2]:
                    end -= 1

        # Skip duplicates of current integer
        while i + 1 < len(nums) and nums[i + 1] == nums[i]:
            i += 1
        i += 1
    return answer