Two Pointers
Instead of a loop inside a loop, put one finger at each end (or one slow and one fast finger) and move them toward each other based on a simple rule. Each move throws away candidates you can prove are useless, so you finish in one pass.
After this topic: You can decide which pointer to move and justify why the discarded options can never be the answer.
Do these first: Arrays & Hashing
Step 1 · Read the lesson
Walk two indexes through sorted or symmetric data instead of nesting loops.
Step 2 · Solve the problems in order
Try each one for about 20 minutes first. Problems with a Run code tab are checked right here. If you are stuck, open Nudge, think again, then Idea. Go skeleton only gives the function shape, and Reference solution is for comparing after you have tried. Tick the box when you could solve it again without help.
A palindrome reads the same from both ends. What if you compare from the outside in?
Left and right pointers; skip anything that is not a letter or digit, compare lowercase characters, move inward.
Target: O(n) time, O(1) space
Types such as ListNode, TreeNode and Node are already defined in the LeetCode editor.
func isPalindrome(s string) boolTested with go test. Try it yourself first, then compare. It is explained step by step on the Two Pointers lesson page.
// IsPalindrome (LeetCode 125): ignoring case and non-alphanumerics, does it read the same both ways? func IsPalindrome(s string) bool { alnum := func(c byte) bool { return c >= '0' && c <= '9' || c >= 'a' && c <= 'z' || c >= 'A' && c <= 'Z' } lower := func(c byte) byte { if c >= 'A' && c <= 'Z' { return c + 32 } return c } left, right := 0, len(s)-1 for left < right { if !alnum(s[left]) { left++ } else if !alnum(s[right]) { right-- } else if lower(s[left]) != lower(s[right]) { return false } else { left++ right-- } } return true }The array is sorted. If the sum is too big, which end is responsible?
Left at start, right at end. If sum > target move right left; if sum < target move left right; else you found it.
Target: O(n) time, O(1) space
Types such as ListNode, TreeNode and Node are already defined in the LeetCode editor.
func twoSum(numbers []int, target int) []intTested with go test. Try it yourself first, then compare. It is explained step by step on the Two Pointers lesson page.
// TwoSumSorted (LeetCode 167): 1-based indices of two numbers in sorted input summing to target. func TwoSumSorted(numbers []int, target int) []int { left, right := 0, len(numbers)-1 for left < right { sum := numbers[left] + numbers[right] if sum == target { return []int{left + 1, right + 1} } else if sum < target { left++ } else { right-- } } return nil }Fix one number; the rest is the problem you just solved. How do you avoid duplicate triplets?
Sort. For each i (skipping equal neighbours) run two pointers on the rest looking for −nums[i]; after a hit, skip equal values on both sides.
Target: O(n²) time, O(1) extra space
Types such as ListNode, TreeNode and Node are already defined in the LeetCode editor.
func threeSum(nums []int) [][]intTested with go test. Try it yourself first, then compare. It is explained step by step on the Two Pointers lesson page.
// ThreeSum (LeetCode 15): unique triplets summing to zero. // Fix one number, then run the opposite-ends scan on the rest; skip duplicates. func ThreeSum(nums []int) [][]int { sort.Ints(nums) out := [][]int{} for i := 0; i < len(nums)-2; i++ { if nums[i] > 0 { break // everything after is positive too } if i > 0 && nums[i] == nums[i-1] { continue } left, right := i+1, len(nums)-1 for left < right { sum := nums[i] + nums[left] + nums[right] if sum < 0 { left++ } else if sum > 0 { right-- } else { out = append(out, []int{nums[i], nums[left], nums[right]}) left++ right-- for left < right && nums[left] == nums[left-1] { left++ } } } } return out }Area = width × the shorter wall. Starting from the widest container, what is the only way to improve?
Pointers at both ends; record the area, then move the pointer at the SHORTER wall inward (moving the taller one can never help).
Target: O(n) time, O(1) space
Types such as ListNode, TreeNode and Node are already defined in the LeetCode editor.
func maxArea(height []int) intTested with go test. Try it yourself first, then compare. It is explained step by step on the Two Pointers lesson page.
// MaxArea (LeetCode 11): most water between two vertical lines. // Width only shrinks, so the only way to improve is to move the shorter wall. func MaxArea(height []int) int { best, left, right := 0, 0, len(height)-1 for left < right { h := min(height[left], height[right]) best = max(best, h*(right-left)) if height[left] < height[right] { left++ } else { right-- } } return best }Water above one bar is limited by the tallest bar on its left and on its right — the smaller of the two.
Two pointers with leftMax and rightMax. Whichever side has the smaller max is the limiting side: add max − height for that side and move it.
Target: O(n) time, O(1) space
Types such as ListNode, TreeNode and Node are already defined in the LeetCode editor.
func trap(height []int) intTested with go test. Try it yourself first, then compare. It is explained step by step on the Two Pointers lesson page.
// Trap (LeetCode 42): water above a bar = min(tallest bar on its left, tallest bar on its right) - its height. // Two pointers: the side with the SHORTER wall is the limiting side, so its water level is already known. func Trap(height []int) int { left, right := 0, len(height)-1 leftMax, rightMax, water := 0, 0, 0 for left < right { if height[left] < height[right] { leftMax = max(leftMax, height[left]) // the right wall is at least this tall, so leftMax limits water += leftMax - height[left] left++ } else { rightMax = max(rightMax, height[right]) water += rightMax - height[right] right-- } } return water }