Practice Session 1: Two Pointers
Problem 1: Container With Most Water
Link: LeetCode 11
Quick Summary: Given array of heights, find two lines that together with x-axis form container with max water.
Industry Context: Resource allocation, load distribution across servers (finding optimal pairing)
Solutions
Approach 1: Brute Force
public int maxArea(int[] height) {
int maxArea = 0;
for (int i = 0; i < height.length; i++) {
for (int j = i + 1; j < height.length; j++) {
int area = Math.min(height[i], height[j]) * (j - i);
maxArea = Math.max(maxArea, area);
}
}
return maxArea;
}- Time: O(n²) - check all pairs
- Space: O(1)
- Tradeoff: Simple but too slow for large inputs
Approach 2: Two Pointers (Optimal)
public int maxArea(int[] height) {
int left = 0, right = height.length - 1;
int maxArea = 0;
while (left < right) {
int width = right - left;
int h = Math.min(height[left], height[right]);
maxArea = Math.max(maxArea, h * width);
// Move pointer with smaller height
if (height[left] < height[right]) {
left++;
} else {
right--;
}
}
return maxArea;
}- Time: O(n) - single pass
- Space: O(1)
- Why it works: Moving shorter line always has potential for improvement
- Tradeoff: More complex logic but optimal
- Added intuition: For equal on both side, if the answer needs to change, then to compensate for lesser width, both sides need to have taller barriers, and hence which changes first does not matter.
Problem 2: 3Sum
Link: LeetCode 15
Quick Summary: Find all unique triplets in array that sum to zero.
Industry Context: Fraud detection (finding related transactions), network routing (path optimization)
Solutions
Approach 1: HashSet (Suboptimal)
public List<List<Integer>> threeSum(int[] nums) {
Set<List<Integer>> result = new HashSet<>();
Arrays.sort(nums);
for (int i = 0; i < nums.length - 2; i++) {
Set<Integer> seen = new HashSet<>();
for (int j = i + 1; j < nums.length; j++) {
int complement = -nums[i] - nums[j];
if (seen.contains(complement)) {
List<Integer> triplet = Arrays.asList(nums[i], complement, nums[j]);
Collections.sort(triplet);
result.add(triplet);
}
seen.add(nums[j]);
}
}
return new ArrayList<>(result);
}- Time: O(n²)
- Space: O(n) for HashSet
- Tradeoff: Uses extra space, slower due to set operations
Approach 2: Two Pointers (Optimal)
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(nums);
for (int i = 0; i < nums.length - 2; i++) {
// Skip duplicates for first number
if (i > 0 && nums[i] == nums[i-1]) continue;
int left = i + 1, right = nums.length - 1;
int target = -nums[i];
while (left < right) {
int sum = nums[left] + nums[right];
if (sum == target) {
result.add(Arrays.asList(nums[i], nums[left], nums[right]));
// Skip duplicates
while (left < right && nums[left] == nums[left+1]) left++;
while (left < right && nums[right] == nums[right-1]) right--;
left++;
right--;
} else if (sum < target) {
left++;
} else {
right--;
}
}
}
return result;
}- Time: O(n²) - O(n log n) sort + O(n²) for iteration
- Space: O(1) excluding output
- Tradeoff: More code but optimal space usage
Problem 3: Trapping Rain Water
Link: LeetCode 42
Quick Summary: Calculate how much water can be trapped after raining given elevation map.
Industry Context: Memory pool management, buffer capacity planning
Solutions
Approach 1: Brute Force
public int trap(int[] height) {
int total = 0;
for (int i = 0; i < height.length; i++) {
int leftMax = 0, rightMax = 0;
// Find max height on left
for (int j = 0; j <= i; j++) {
leftMax = Math.max(leftMax, height[j]);
}
// Find max height on right
for (int j = i; j < height.length; j++) {
rightMax = Math.max(rightMax, height[j]);
}
total += Math.min(leftMax, rightMax) - height[i];
}
return total;
}- Time: O(n²)
- Space: O(1)
- Tradeoff: Too slow
Approach 2: Precompute Arrays
public int trap(int[] height) {
if (height.length == 0) return 0;
int n = height.length;
int[] leftMax = new int[n];
int[] rightMax = new int[n];
leftMax[0] = height[0];
for (int i = 1; i < n; i++) {
leftMax[i] = Math.max(leftMax[i-1], height[i]);
}
rightMax[n-1] = height[n-1];
for (int i = n-2; i >= 0; i--) {
rightMax[i] = Math.max(rightMax[i+1], height[i]);
}
int total = 0;
for (int i = 0; i < n; i++) {
total += Math.min(leftMax[i], rightMax[i]) - height[i];
}
return total;
}- Time: O(n)
- Space: O(n) for arrays
- Tradeoff: Fast but uses extra space
Approach 3: Two Pointers (Optimal)
public int trap(int[] height) {
int left = 0, right = height.length - 1;
int leftMax = 0, rightMax = 0;
int total = 0;
while (left < right) {
if (height[left] < height[right]) {
if (height[left] >= leftMax) {
leftMax = height[left];
} else {
total += leftMax - height[left];
}
left++;
} else {
if (height[right] >= rightMax) {
rightMax = height[right];
} else {
total += rightMax - height[right];
}
right--;
}
}
return total;
}- Time: O(n)
- Space: O(1)
- Tradeoff: Most optimal, but trickiest to understand
Key Insight: We only need to track max on the side we’re processing, not both sides.
Key Takeaways
- Two pointers work best on sorted arrays or when you can sort
- Choose direction: opposite (meet in middle) vs same (slow-fast)
- Always consider if sorting changes problem semantics
- Space vs Time: Arrays for speed, pointers for space efficiency