Two Pointers¶
Table of Contents¶
- 125. Valid Palindrome (Easy)
- 167. Two Sum II - Input Array Is Sorted (Medium)
- 15. 3Sum (Medium)
- 11. Container With Most Water (Medium)
- 42. Trapping Rain Water (Hard)
125. Valid Palindrome¶
# List Comprehension
def isPalindrome(s: str) -> bool:
s = [char.lower() for char in s if char.isalnum()]
return s == s[::-1]
# Left Right Pointers
def isPalindromeLR(s: str) -> bool:
left, right = 0, len(s) - 1
while left < right:
while left < right and not s[left].isalnum():
left += 1
while left < right and not s[right].isalnum():
right -= 1
if s[left].lower() != s[right].lower():
return False
left += 1
right -= 1
return True
s = "A man, a plan, a canal: Panama"
print(isPalindrome(s)) # True
print(isPalindromeLR(s)) # True
167. Two Sum II - Input Array Is Sorted¶
from typing import List
# Left Right Pointers
def twoSum(numbers: List[int], target: int) -> List[int]:
left, right = 0, len(numbers) - 1
while left < right:
total = numbers[left] + numbers[right]
if total > target:
right -= 1
elif total < target:
left += 1
else:
return [left + 1, right + 1]
# |------------|------- |---------|
# | Approach | Time | Space |
# |------------|--------|---------|
# | Left Right | O(n) | O(1) |
# |------------|--------|---------|
numbers = [2, 7, 11, 15]
target = 9
print(twoSum(numbers, target)) # [1, 2]
15. 3Sum¶
from typing import List
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
"""Two Pointers: O(n^2) time, O(1) space.
Sort, fix one element, then two-pointer scan for complement.
"""
n = len(nums)
if n <= 2:
return []
res = []
nums.sort()
for k in range(n - 2):
if k > 0 and nums[k] == nums[k - 1]:
continue
i, j = k + 1, n - 1
while i < j:
total = nums[k] + nums[i] + nums[j]
if total > 0:
j -= 1
elif total < 0:
i += 1
else:
res.append([nums[k], nums[i], nums[j]])
while i < j and nums[i] == nums[i + 1]:
i += 1
while i < j and nums[j] == nums[j - 1]:
j -= 1
i += 1
j -= 1
return res
def test_three_sum():
s = Solution()
for fn in (s.threeSum,):
assert fn([-1, 0, 1, 2, -1, -4]) == [[-1, -1, 2], [-1, 0, 1]]
assert fn([0, 1, 1]) == []
assert fn([0, 0, 0]) == [[0, 0, 0]]
assert fn([]) == []
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<vector<int>> res;
int n = nums.size();
for (int i = 0; i < n - 2; i++) {
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
int left = i + 1, right = n - 1;
while (left < right) {
int total = nums[i] + nums[left] + nums[right];
if (total > 0)
right--;
else if (total < 0)
left++;
else {
res.push_back({nums[i], nums[left], nums[right]});
while (left < right && nums[left] == nums[left + 1]) left++;
while (left < right && nums[right] == nums[right - 1]) right--;
left++;
right--;
}
}
}
return res;
}
int main() {
vector<int> nums = {-1, 0, 1, 2, -1, -4};
vector<vector<int>> res = threeSum(nums);
for (auto& v : res) {
for (int i : v) {
cout << i << " ";
}
cout << endl;
}
return 0;
}
11. Container With Most Water¶
from typing import List
class Solution:
def maxArea(self, height: List[int]) -> int:
"""Two Pointers: O(n) time, O(1) space.
Move the shorter side inward to potentially find a taller line.
"""
left, right = 0, len(height) - 1
res = 0
while left < right:
w = right - left
h = min(height[left], height[right])
res = max(res, w * h)
if height[left] < height[right]:
left += 1
else:
right -= 1
return res
def maxAreaBF(self, height: List[int]) -> int:
"""Brute Force: O(n^2) time, O(1) space.
Check every pair of lines.
"""
res = 0
for i in range(len(height)):
for j in range(i + 1, len(height)):
res = max(res, min(height[i], height[j]) * (j - i))
return res
def test_max_area():
s = Solution()
for fn in (s.maxArea, s.maxAreaBF):
assert fn([1, 8, 6, 2, 5, 4, 8, 3, 7]) == 49
assert fn([1, 1]) == 1
assert fn([4, 3, 2, 1, 4]) == 16
assert fn([1, 2, 1]) == 2
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
int maxArea(vector<int>& height) {
int left = 0, right = height.size() - 1;
int res = 0;
while (left < right) {
int h = min(height[left], height[right]);
int w = right - left;
res = max(res, h * w);
if (height[left] < height[right])
left++;
else
right--;
}
return res;
}
int main() {
vector<int> height = {1, 8, 6, 2, 5, 4, 8, 3, 7};
cout << maxArea(height) << endl; // 49
return 0;
}
42. Trapping Rain Water¶
from typing import List
class Solution:
def trap(self, height: List[int]) -> int:
"""Two Pointers: O(n) time, O(1) space.
Track max from each side; shorter side determines water level.
"""
left, right = 0, len(height) - 1
max_l = max_r = res = 0
while left < right:
if height[left] < height[right]:
max_l = max(max_l, height[left])
res += max_l - height[left]
left += 1
else:
max_r = max(max_r, height[right])
res += max_r - height[right]
right -= 1
return res
def trapDP(self, height: List[int]) -> int:
"""DP Prefix Max: O(n) time, O(n) space.
Precompute max heights from left and right.
"""
n = len(height)
max_left = [0] * n
max_right = [0] * n
for i in range(1, n):
max_left[i] = max(max_left[i - 1], height[i - 1])
for i in range(n - 2, -1, -1):
max_right[i] = max(max_right[i + 1], height[i + 1])
return sum(max(0, min(max_left[i], max_right[i]) - height[i]) for i in range(n))
def trapStack(self, height: List[int]) -> int:
"""Monotonic Stack: O(n) time, O(n) space.
Pop shorter bars and accumulate trapped water by layer.
"""
stack = []
res = 0
for i in range(len(height)):
while stack and height[i] > height[stack[-1]]:
top = stack.pop()
if not stack:
break
w = i - stack[-1] - 1
h = min(height[i], height[stack[-1]]) - height[top]
res += w * h
stack.append(i)
return res
def test_trap():
s = Solution()
for fn in (s.trap, s.trapDP, s.trapStack):
assert fn([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]) == 6
assert fn([4, 2, 0, 3, 2, 5]) == 9
assert fn([1, 0, 1]) == 1
assert fn([]) == 0
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
class Solution
{
public:
int trap(vector<int> &height)
{
if (height.empty())
return 0;
int res = 0;
int left = 0, right = height.size() - 1;
int maxL = height[left], maxR = height[right];
while (left < right)
{
if (maxL < maxR)
{
left++;
maxL = max(maxL, height[left]);
res += maxL - height[left];
}
else
{
right--;
maxR = max(maxR, height[right]);
res += maxR - height[right];
}
}
return res;
}
};
int main()
{
vector<int> height = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
Solution solution;
cout << solution.trap(height) << endl;
return 0;
}