Pointer-based solutions show up repeatedly in LeetCode-style interview practice, but the useful part is not memorizing a template. Each of these three problems asks for a slightly different form of movement: expanding from a center, shrinking a range from both ends, or sorting first so two pointers can search for a target sum.
Longest Palindromic Substring
Given a string s, return the longest palindromic substring in s.
Example:
Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.
A palindrome is symmetric, so one natural approach is to treat every character and every adjacent pair as a possible center. Expand outward while the characters on both sides match, and keep track of the widest range found so far. Odd-length palindromes use a single character as the center; even-length palindromes use the gap between two characters.
Steps: 1. Walk through the string and consider each character or character pair as a center. 2. Expand left and right until the two characters differ or a boundary is reached. 3. Record the longest range seen so far. 4. Run the same expansion logic separately for odd and even lengths.
class Solution:
def longestPalindrome(self, s: str) -> str:
n = len(s)
if n == 0:
return ""
ans_left = ans_right = 0
# Expand around odd-length centers
for i in range(n):
l = r = i
while l >= 0 and r < n and s[l] == s[r]:
l -= 1
r += 1
l += 1
r -= 1
if r - l > ans_right - ans_left:
ans_left, ans_right = l, r
# Expand around even-length centers
for i in range(n - 1):
l, r = i, i + 1
while l >= 0 and r < n and s[l] == s[r]:
l -= 1
r += 1
l += 1
r -= 1
if r - l > ans_right - ans_left:
ans_left, ans_right = l, r
return s[ans_left:ans_right + 1]
Complexity: each center can expand up to O(n), so the total time is O(n²). Only a constant number of variables are used, so the extra space is O(1).
Container With Most Water
You are given an integer array height of length n. Each element represents the height of a vertical line. Choose two lines that, together with the x-axis, form a container that holds the most water.
Example:
Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
The area is width times height, and the height is limited by the shorter line. Start with the widest possible container by placing one pointer at each end. After calculating the current area, move the pointer on the shorter side inward. Moving the taller side cannot improve the area while the width decreases, because the shorter line still caps the height. Moving the shorter side leaves open the possibility of finding a taller boundary.
Steps:
1. Set left = 0 and right = n - 1.
2. Compute the current area and update the maximum.
3. Move the shorter side:
- If height[left] < height[right], increment left.
- Otherwise, decrement right.
4. Stop when left >= right.
from typing import List
class Solution:
def maxArea(self, height: List[int]) -> int:
left, right = 0, len(height) - 1
max_area = 0
while left < right:
area = (right - left) * min(height[left], height[right])
max_area = max(max_area, area)
if height[left] < height[right]:
left += 1
else:
right -= 1
return max_area
Complexity: each element is visited at most once, so time is O(n), and extra space is O(1).
3Sum
Given an integer array nums, return all unique triplets [nums[i], nums[j], nums[k]] such that nums[i] + nums[j] + nums[k] == 0.
Example:
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Sorting makes the problem easier to control. Fix one value as the first element of the triplet, then use two pointers inside the remaining portion to find pairs that sum to the negation of that value. Sorting also makes duplicate skipping straightforward.
Steps:
1. Sort nums.
2. Iterate over nums[i] as the first value.
- If nums[i] > 0, break, since the remaining values cannot bring the sum back down to zero.
- If nums[i] is the same as the previous value, skip it.
3. Use two pointers j and k in the range [i + 1, n - 1]:
- If the sum is greater than zero, decrement k.
- If the sum is less than zero, increment j.
- If the sum is zero, add the triplet and skip duplicate values for both pointers.
from typing import List
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
nums.sort()
n = len(nums)
ans = []
for i in range(n - 2):
if nums[i] > 0:
break
if i > 0 and nums[i] == nums[i - 1]:
continue
j, k = i + 1, n - 1
while j < k:
s = nums[i] + nums[j] + nums[k]
if s > 0:
k -= 1
elif s < 0:
j += 1
else:
ans.append([nums[i], nums[j], nums[k]])
# Skip duplicates
while j < k and nums[j] == nums[j + 1]:
j += 1
while j < k and nums[k] == nums[k - 1]:
k -= 1
j += 1
k -= 1
return ans
Complexity: sorting takes O(n log n), and the two-pointer scan is O(n²), so the overall time is O(n²). The sort can be done in place, and the extra space is O(1).
For a quick comparison: longest palindrome uses center expansion in O(n²) time and O(1) space; container with most water uses two pointers in O(n) time and O(1) space; 3Sum combines sorting with two pointers in O(n²) time and O(1) extra space.