Algorithms: Two Pointers

Opposite ends:          Same direction:
[1, 2, 3, 4, 5]        [1, 2, 3, 4, 5]
 L           R           S  F
      →   ←                  →→

func twoSum(nums []int, target int) []int {
    left, right := 0, len(nums)-1
    for left < right {
        sum := nums[left] + nums[right]
        switch {
        case sum == target:
            return []int{left, right}
        case sum < target:
            left++   // cần tổng lớn hơn → tăng left
        default:
            right--  // cần tổng nhỏ hơn → giảm right
        }
    }
    return nil
}

// Remove duplicates in-place từ sorted array
func removeDuplicates(nums []int) int {
    slow := 0
    for fast := 1; fast < len(nums); fast++ {
        if nums[fast] != nums[slow] {
            slow++
            nums[slow] = nums[fast]
        }
    }
    return slow + 1
}

Sort trước: [-4, -1, -1, 0, 1, 2]
Fix a=-4: two pointers tìm b+c=4
Fix a=-1: two pointers tìm b+c=1
...

func threeSum(nums []int) [][]int {
    sort.Ints(nums)
    result := [][]int{}

    for i := 0; i < len(nums)-2; i++ {
        // Skip duplicate cho i
        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 {
                result = append(result, []int{nums[i], nums[left], nums[right]})
                // Skip duplicates
                for left < right && nums[left] == nums[left+1] {
                    left++
                }
                for left < right && nums[right] == nums[right-1] {
                    right--
                }
                left++
                right--
            } else if sum < 0 {
                left++
            } else {
                right--
            }
        }
    }
    return result
}

[1, 8, 6, 2, 5, 4, 8, 3, 7]
 L                         R
area = min(height[L], height[R]) × (R - L)
→ move pointer có height nhỏ hơn

func maxArea(height []int) int {
    left, right := 0, len(height)-1
    maxWater := 0
    for left < right {
        h := min(height[left], height[right])
        water := h * (right - left)
        if water > maxWater {
            maxWater = water
        }
        if height[left] < height[right] {
            left++
        } else {
            right--
        }
    }
    return maxWater
}

elevation: [0,1,0,2,1,0,1,3,2,1,2,1]
water:         1   1 2 1   1   1
               
Tại mỗi position i:
water[i] = min(maxLeft[i], maxRight[i]) - height[i]

func trap(height []int) int {
    left, right := 0, len(height)-1
    maxLeft, maxRight := 0, 0
    total := 0

    for left < right {
        if height[left] < height[right] {
            if height[left] >= maxLeft {
                maxLeft = height[left]
            } else {
                total += maxLeft - height[left]
            }
            left++
        } else {
            if height[right] >= maxRight {
                maxRight = height[right]
            } else {
                total += maxRight - height[right]
            }
            right--
        }
    }
    return total
}

[2, 0, 2, 1, 1, 0]
 lo=0, mid=0, hi=5

[0, 0, 1, 1, 2, 2]

func sortColors(nums []int) {
    lo, mid, hi := 0, 0, len(nums)-1
    for mid <= hi {
        switch nums[mid] {
        case 0:
            nums[lo], nums[mid] = nums[mid], nums[lo]
            lo++
            mid++
        case 1:
            mid++
        case 2:
            nums[mid], nums[hi] = nums[hi], nums[mid]
            hi-- // không tăng mid vì nums[hi] chưa được check
        }
    }
}

Slow: 1 step/turn
Fast: 2 steps/turn
→ Nếu có cycle, fast sẽ gặp slow trong cycle

func hasCycle(head *ListNode) bool {
    slow, fast := head, head
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
        if slow == fast {
            return true
        }
    }
    return false
}