Two Pointers¶
Table of Contents¶
- 283. Move Zeroes (Easy)
- 11. Container With Most Water (Medium)
- 15. 3Sum (Medium)
- 42. Trapping Rain Water (Hard)
283. Move Zeroes¶
from typing import List
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
"""Two Pointers: O(n) time, O(1) space.
Swap non-zero elements to the front, zeroes drift to end.
"""
slow = 0
n = len(nums)
for fast in range(n):
if nums[fast] != 0:
nums[slow], nums[fast] = nums[fast], nums[slow]
slow += 1
def test_move_zeroes():
s = Solution()
for fn in (s.moveZeroes,):
nums = [0, 1, 0, 3, 12]
fn(nums)
assert nums == [1, 3, 12, 0, 0]
nums = [0]
fn(nums)
assert nums == [0]
nums = [1, 2, 3]
fn(nums)
assert nums == [1, 2, 3]
nums = [0, 0, 0, 0, 1]
fn(nums)
assert nums == [1, 0, 0, 0, 0]
#include <iostream>
#include <vector>
using namespace std;
void moveZeroes(vector<int>& nums) {
size_t n = nums.size();
size_t fast = 0, slow = 0;
while (fast < n) {
if (nums[fast] != 0) {
swap(nums[slow], nums[fast]);
slow++;
}
fast++;
}
}
int main() {
vector<int> nums = {0, 1, 0, 3, 12};
moveZeroes(nums);
// [1, 3, 12, 0, 0]
for (size_t i = 0; i < nums.size(); i++) {
cout << nums[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;
}
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;
}
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;
}