Two Pointers

Valid Palindrome

Time Complexity: O(n)

Space Complexity: O(1)

def isPalindrome(s: str) -> bool:
  l, r = 0, len(s) - 1
  while l < r:
    while l < r and not s[l].isalnum():
      l += 1
    while l < r and not s[r].isalnum():
      r -= 1
    
    if s[l].lower() != s[r].lower():
      return False
    l += 1
    r -= 1
  return True

167 Two Sum II - Input Array Is Sorted

Time Complexity: O(n). At worst case we iterate through every number and find the solution to be the last pair.

Space Complexity: O(1). The only extra space used was two pointers which is constant.

def twoSum(numbers: List[int], target: int) -> List[int]:
  l, r = 0, len(numbers) - 1

  while l < r:
    res = numbers[l] + numbers[r]
  
    if res == target:
      return [l + 1, r + 1]
    elif res > target:
      r -= 1
    else:
      l += 1

15 3Sum

Let n be the number of elements in the nums list.

Time Complexity

• Sorting the input array takes O(n log n).
• We iterate through the array once, fixing one element at a time (O(n)).
• For each fixed element, we use a two-pointer scan over the remaining portion of the array (O(n)).

Combining these:

• O(n log n + n²) = O(n²)

Space Complexity

• The array is sorted in place and only a few pointers are used, so the algorithm requires O(1) extra space.
• The output list is not counted toward auxiliary space; in the worst case it may contain up to O(n) triplets, where k is the number of valid solutions.

Overall auxiliary space: O(1) (excluding output)

def threeSum(nums: List[int]) -> List[List[int]]:
    nums.sort()
    res = []

    for idx, i in enumerate(nums):
        if i > 0:
          break
        if idx > 0 and i == nums[idx - 1]:
          continue
        
        l, r = idx + 1, len(nums) - 1
        while l < r:
            total = i + nums[l] + nums[r]

            if total == 0:
                res.append([i, nums[l], nums[r]])
                l += 1
                r -= 1

                while l < r and nums[l] == nums[l - 1]:
                    l += 1
            elif total > 0:
                r -= 1
            else:
                l += 1
    return res

11 Container With Most Water

Time Complexity: O(n). We iterate over the input heights once.

Space Complexity: O(1). The only extra space used was for the two pointers and result, which both are constants.

def maxArea(height: List[int]) -> int:
  l, r = 0, len(height) - 1
  res = 0

  while l < r:
    res = max(res, min(height[l], height[r]) * (r - l))

    if height[l] >= height[r]:
      r -= 1
    else:
      l += 1
      
  return res

42 Trapping Rain Water

def trap(height: List[int]) -> int:
  res = 0
  prefix_max = []

  for h in height:
    if prefix_max:
      prefix_max.append(max(h, prefix_max[-1]))
    else:
      prefix_max.append(h)
  
  post_high = 0
  for i in range(len(height) - 1, 0, -1):
    post_high = max(post_high, height[i])
    res += min(prefix_max[i], post_high) - height[i]

  return res