Two Pointers

ปัญหา

โจทย์เรื่อง array หลายข้อเป็นเรื่องของคู่: ค่าสองตัวที่บวกกันได้ target, ของหนึ่งชิ้นกับตัวที่ซ้ำกับมัน, ปลายสองข้างของช่วงที่จะกลับด้าน คำตอบแบบตรง ๆ คือลองทุกคู่ด้วย nested loop สองชั้น และค่า n ตัวก็มี n(n − 1)/2 คู่: 28 คู่สำหรับค่า 8 ตัวใน diagram และราว 5 แสนล้านคู่สำหรับล้านตัว hash set ทำให้ pair sum เหลือแค่รอบเดียวได้ แต่ต้องใช้ memory เพิ่ม O(n) และไม่สนลำดับที่ข้อมูลมีอยู่แล้วเลย

ถ้าข้อมูลมีลำดับ การเทียบครั้งเดียวก็ตัดทิ้งได้มากกว่าแค่คู่เดียว two pointers เปลี่ยนเรื่องนี้ให้เป็นการเดินรอบเดียว: index สองตัวเริ่มที่ตำแหน่งที่เลือกไว้ การเทียบทุกครั้งขยับหนึ่งในสองตัวนั้น และไม่มีตัวไหนถอยกลับ รวมกันแล้วเลยขยับไม่เกินราว n ครั้ง memory ที่ใช้เพิ่มก็มีแค่ index สองตัว

ทำงานยัง⁠ไง

เทคนิคนี้ใช้ได้เมื่อการเทียบแต่ละครั้งพิสูจน์ได้ว่าของใต้ pointer ตัวหนึ่งไม่มีทางอยู่ในคำตอบไหนที่ยังเป็นไปได้ pointer ตัวนั้นเลยขยับผ่านมันไปได้ถาวร input ที่เรียงแล้วคือที่มาปกติของการพิสูจน์แบบนี้ แต่ก็ไม่ใช่ที่มาเดียว

สำหรับ pair sum บน array ที่เรียงแล้ว lo เริ่มที่ index แรก และ hi เริ่มที่ index สุดท้าย invariant คือ: ถ้ามีคู่ไหนบวกกันได้ target ตัว index ทั้งสองของคู่นั้นต้องอยู่ใน [lo, hi]

1. คำนวณ s = a[lo] + a[hi] ถ้ามันเท่ากับ target ก็ return (lo, hi)
2. ถ้า s น้อยไป: a[hi] คือค่าที่ใหญ่ที่สุดที่ยังอยู่ในเกม เลย a[lo] บวกกับค่าไหนที่ยังอยู่ในเกมก็ได้ไม่เกิน s ก็ยังน้อยไปอยู่ดี ไม่มีคู่ที่เหลือคู่ไหนใช้ lo ได้ เลยทำ lo += 1
3. ถ้า s มากไป: a[lo] คือค่าที่เล็กที่สุดที่ยังอยู่ในเกม เลยค่าไหนที่ยังอยู่ในเกมบวกกับ a[hi] ก็ได้อย่างน้อย s ไม่มีคู่ที่เหลือคู่ไหนใช้ hi ได้ เลยทำ hi -= 1
4. เมื่อ lo มาถึง hi ช่วงนั้นก็ไม่มีคู่เหลือแล้ว แปลว่าไม่มีคำตอบ

ทุกขั้นรักษา invariant ไว้และทำให้ช่องว่างหดลงหนึ่ง เลยตรวจไม่เกิน n − 1 ครั้ง ตารางคู่ใน diagram แสดงการจดบันทึกนี้: การขยับแต่ละครั้งปลดค่าหนึ่งตัวออกไปพร้อมกับคู่ทั้งแถวหรือทั้งคอลัมน์ของมัน และแถวกับคอลัมน์ที่ถูกเคลียร์รวมกันได้ครบทุกคู่ 7 + 6 + 5 + 4 + 3 + 2 + 1 = 28

จากปลายสองข้าง

pointer ที่เริ่มจากปลายทั้งสองข้างแล้วมาเจอกันตรงกลาง เหมาะกับคำถามเรื่องคู่และความสมมาตร:

• Pair sum แบบข้างบน Closest pair sum ขยับแบบเดียวกัน และจำผลรวมที่ดีที่สุดที่เจอไว้ ส่วน การนับคู่ที่ผลรวมไม่เกิน k จะบวก hi − lo เข้าไปทุกครั้งที่ a[lo] + a[hi] ≤ k (a[lo] จับคู่ได้กับทุกตัวจนถึง hi) แล้วขยับ lo ไม่อย่างนั้นก็ขยับ hi
• Three-sum (ค่าสามตัวที่บวกกันได้ t): sort ครั้งเดียว แล้วตรึงค่า a[i] ทีละตัว แล้วรัน pair sum บนค่าที่อยู่หลังมันด้วย target t − a[i] รวมเป็น n รอบ รอบละ O(n) คือ O(n²) ทั้งหมด ขณะที่การลองทุกสามตัวเสีย O(n³) การข้ามค่าที่ซ้ำกันช่วยกันไม่ให้มีชุดสามตัวซ้ำในคำตอบ
• Palindrome: เทียบ s[lo] กับ s[hi] แล้วขยับทั้งคู่เข้าหากัน ตัวที่ไม่ตรงตัวแรกก็ตัดสินได้เลย
• กลับด้านแบบ in place: สลับ a[lo] กับ a[hi] แล้วขยับทั้งคู่เข้าหากันจนมาเจอกัน สลับ ⌊n/2⌋ ครั้ง
• ภาชนะที่ใส่น้ำได้มากที่สุด: จากแถวของกำแพงที่สูงต่างกัน เลือกกำแพงสองอันที่ใส่น้ำได้มากที่สุด คือระยะห่างระหว่างสองอันคูณกับความสูงของอันที่เตี้ยกว่า ความสูงไม่ได้เรียงไว้ แต่การขยับก็ยังปลอดภัย ถ้าจับคู่กำแพงที่เตี้ยกว่ากับกำแพงไหนก็ตามที่อยู่ลึกเข้าไป ความกว้างจะน้อยลงและความสูงไม่มากขึ้น ภาชนะไหนที่ใช้กำแพงที่เตี้ยกว่าเลยชนะอันปัจจุบันไม่ได้ แล้ว pointer ของมันก็ขยับเข้าด้านใน

ทิศเดียวกัน

pointer ที่ขยับไปข้างหน้าทั้งคู่ เหมาะกับการเขียน sequence ใหม่ในรอบเดียว หรือการเดินไปบนสอง sequence คู่กัน:

• ลบค่าซ้ำ (ขั้นที่ 4): r อ่านทุกตัว และ w บอกว่าของที่เก็บไว้ตัวถัดไปจะลงตรงไหน เพราะ w ไม่เคยแซง r การเขียนเลยไม่มีทางทับของที่ยังไม่ได้อ่าน loop เดียวกันนี้ใช้ ลบ ทุกสำเนาของค่าหนึ่ง หรือ กรอง ด้วยเงื่อนไขอะไรก็ได้: ก็อปของไปที่ w ถ้าผ่าน ไม่อย่างนั้นก็ข้าม แล้ว return w เป็นความยาวใหม่
• Partitioning: partition แบบ Lomuto ใน Quicksort ไล่ดูด้วย index ตัวหนึ่ง และใช้อีกตัวจำปลายของกลุ่มค่าเล็ก ทั้งคู่เลยขยับไปทางขวา ส่วนวิธีดั้งเดิมของ Hoare ขยับ index สองตัวเข้าหากันแทน โจทย์ Dutch national flag ของ Dijkstra แบ่งค่าเป็นสามกลุ่ม (น้อยกว่า เท่ากับ และมากกว่า pivot) ในรอบเดียวด้วย index สามตัว
• Merging: หนึ่ง pointer ต่อ input ที่เรียงแล้วหนึ่งชุด หยิบตัวที่เล็กกว่าในสองตัวปัจจุบัน แล้วเลื่อน pointer ฝั่งนั้น นี่คือขั้น merge ของ Merge Sort และของ merge join ใน database
• Slow pointer กับ fast pointer เดินบน linked list ด้วยความเร็วต่างกัน เมื่อตัวเร็ว (สอง link ต่อขั้น) ไปถึงปลาย ตัวช้า (หนึ่ง link ต่อขั้น) จะอยู่ตรงกลาง และคู่เดียวกันนี้ก็ใช้หา cycle ได้ (ดูด้านล่าง) อีกแบบหนึ่งให้ความเร็วเท่ากัน แต่ให้ pointer ตัวหนึ่งเริ่มล่วงหน้าไป k node: เมื่อมันไปถึงปลาย อีกตัวจะอยู่ที่ node ที่ k นับจากท้าย

Slow pointer กับ fast pointer: หา cycle

linked list วนกลับมาหาตัวเองได้ และ sequence ที่ได้จากการเรียก function ซ้ำไปเรื่อย ๆ (x, f(x), f(f(x)), …) ก็เหมือนกัน ถ้าใช้ set ของ node ที่เคยไปแล้วก็หา loop ได้ โดยใช้ memory เพิ่ม O(n) ส่วน tortoise and hare ของ Floyd ใช้แค่ reference สองตัว:

• slow pointer ตาม link หนึ่งเส้นต่อขั้น และ fast pointer ตามสองเส้น ถ้าไม่มี cycle ตัว fast pointer จะวิ่งหลุดปลาย ถ้ามี ทั้งคู่จะเข้าไปอยู่ใน cycle และนับจากนั้น fast pointer จะไล่ทันขึ้นมาหนึ่ง node ต่อขั้น มันเลยมาตกที่ slow pointer ก่อนที่ slow pointer จะวนครบหนึ่งรอบ ถ้ามี μ node อยู่ก่อน cycle และ cycle มี λ node ทั้งคู่จะเจอกันใน cycle ภายใน μ + λ ขั้นของ slow pointer
• cycle เริ่มตรงไหน: ตอนที่เจอกัน slow pointer เดินไปแล้วเป็นจำนวนขั้นที่เป็นพหุคูณของ λ ให้เอา pointer ตัวหนึ่งกลับไปที่ head แล้วขยับทั้งคู่ทีละ link หลังผ่านไป μ ขั้น ตัวแรกจะอยู่ที่ node แรกของ cycle ส่วนตัวที่สองที่อยู่ล่วงหน้าไปเป็นจำนวนรอบเต็มบนเส้นทางเดียวกัน ก็อยู่ที่ node นั้นด้วย ตรงนั้นเลยเป็นจุดที่มันเจอกัน มันเจอกันก่อนหน้านั้นไม่ได้ เพราะก่อนหน้านั้นตัวหนึ่งอยู่นอก cycle และอีกตัวอยู่ใน cycle
• cycle ยาวเท่าไร: จากจุดที่เจอกัน ให้เดิน pointer ตัวหนึ่งวนไปจนกลับมาที่เดิม แล้วนับจำนวน link

Donald Knuth ให้เครดิตวิธีนี้กับ Robert W. Floyd ในเล่ม 2 ของ The Art of Computer Programming แล้ว Richard Brent ก็ตีพิมพ์ variant ที่เร็วกว่าในปี 1980 ใน variant นี้ slow pointer รออยู่กับที่ ขณะที่ fast pointer เดินทีละขั้น และทุกครั้งที่จำนวนขั้นนับจากการกระโดดครั้งล่าสุดถึงกำลังของสอง (1, 2, 4, 8, …) slow pointer จะกระโดดไปอยู่ที่ fast pointer พอ fast pointer มาตกที่ตัวที่รออยู่ จำนวนขั้นนับจากการกระโดดครั้งล่าสุดก็คือความยาวของ cycle ส่วนแต่ละขั้นของวิธีนี้ตาม link แค่เส้นเดียว ขณะที่ขั้นหนึ่งของ Floyd ตามสามเส้น Brent รายงานว่าวิธีของเขาหา cycle ได้เร็วกว่าราว 36% โดยเฉลี่ย และเขาใช้มันสร้างเวอร์ชันของ Pollard's rho method (วิธีแยกตัวประกอบ integer ที่อาศัยการหา cycle เป็นหลัก) ที่เร็วขึ้นราว 24%

Sort ก่อน หรือใช้ hash set?

two pointers ต้องอาศัยลำดับ กับ input ที่ไม่ได้เรียง การ sort ก่อนเสีย O(n log n) มากกว่าการเดินรอบเดียวที่เป็น O(n) ไปแล้ว และการ sort ก็ย้ายค่าออกจาก index เดิมของมัน (sort เป็นคู่ (value, index) ถ้าอยากเก็บไว้) สำหรับ query pair sum ครั้งเดียวบนข้อมูลที่ไม่ได้เรียง hash set ทำได้ดีกว่า: เดินผ่านค่าทั้งหมดรอบเดียว และสำหรับ x แต่ละตัว ก็ตรวจว่าเคยเห็น target − x มาแล้วหรือยัง ก่อนจะเพิ่ม x เข้าไป วิธีนี้ใช้เวลา O(n) แบบ expected แต่ใช้ memory เพิ่ม O(n) และหาได้แค่คู่ที่ตรงเป๊ะ (ดู Hash Table) two pointers ชนะเมื่อข้อมูลเรียงอยู่แล้วหรือยัง⁠ไงก็ต้อง sort อยู่ดี เมื่อ memory ตึง และกับคำถามที่ hash ตอบไม่ได้ อย่างผลรวมที่ใกล้ที่สุด หรือจำนวนคู่ที่ต่ำกว่าขอบเขต ส่วน Binary Search อยู่ตรงกลาง: สำหรับ a[i] แต่ละตัว ให้ค้นหา target − a[i] ในส่วนที่เหลือของ array ที่เรียงแล้ว รวมเป็น O(n log n)

query planner ของ database ก็เลือกจากสามรูปแบบเดียวกันนี้ตอน join สอง table ตัว PostgreSQL เขียนกลยุทธ์การ join ไว้สามแบบ: nested loop join ไล่ดู input ฝั่งขวาหนึ่งรอบต่อทุก row ของฝั่งซ้าย (ทุกคู่) merge join sort input ทั้งสองฝั่งตาม join key หรืออ่านมันตามลำดับนั้นจาก index แล้วไล่ดูทั้งสองไปพร้อมกัน (two pointers) และ hash join โหลด input ฝั่งขวาลงใน hash table แล้ว probe มันด้วยแต่ละ row ของฝั่งซ้าย

โค้ด

def pair_sum(a, target):
    """Return indexes (i, j) with i < j and a[i] + a[j] == target in sorted a, or None."""
    lo, hi = 0, len(a) - 1
    while lo < hi:
        s = a[lo] + a[hi]
        if s == target:
            return lo, hi
        if s < target:
            lo += 1          # a[lo] is too small even with the largest value left
        else:
            hi -= 1          # a[hi] is too big even with the smallest value left
    return None


def dedupe_sorted(a):
    """Keep one copy of each value at the front of sorted a, in place; return how many."""
    if not a:
        return 0
    w = 1                    # a[:w] holds the values kept so far
    for r in range(1, len(a)):
        if a[r] != a[w - 1]: # a new value: copy it to the next free slot
            a[w] = a[r]
            w += 1
    return w


class Node:
    def __init__(self, value, next=None):
        self.value, self.next = value, next


def has_cycle(head):
    """Floyd's tortoise and hare: slow moves one link, fast moves two."""
    slow = fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:     # fast can only catch up with slow inside a cycle
            return True
    return False             # fast reached the end of the list


a = [2, 3, 5, 8, 11, 14, 18, 21]
print(pair_sum(a, 25), pair_sum(a, 4))      # (4, 5) None
d = [1, 1, 2, 3, 3, 3, 4, 5, 5]
k = dedupe_sorted(d)
print(k, d[:k])                             # 5 [1, 2, 3, 4, 5]
nodes = [Node(v) for v in range(5)]
for x, y in zip(nodes, nodes[1:]):
    x.next = y
print(has_cycle(nodes[0]))                  # False
nodes[-1].next = nodes[2]                   # 4 -> 2 closes a loop
print(has_cycle(nodes[0]))                  # True

pair_sum ถูกตรวจเทียบกับการค้นหาแบบ brute force บน list ที่เรียงแล้วแบบสุ่ม 20,000 ชุดที่มีค่าซ้ำและค่าติดลบ (คู่ไหนที่ brute force เจอก็นับเป็นคำตอบที่ถูก และ None ต้องแปลว่าไม่มีคู่เลย) รวมถึง list ว่าง ของชิ้นเดียว คู่ของค่าที่เท่ากัน และ target ที่ไม่มีคำตอบ dedupe_sorted ถูกตรวจเทียบกับ sorted(set(a)) บน list สุ่ม 20,000 ชุด รวมถึง list ว่าง list ตัวเดียว และ list ที่ค่าเท่ากันหมด ส่วน has_cycle ถูกตรวจเทียบกับการเดินที่ใช้ set ของ node ที่เคยไปแล้ว บน list สุ่ม 20,000 ชุดทั้งที่มีและไม่มี loop รวมถึง node ที่ชี้กลับมาหาตัวเอง

Complexity

pair_sum กับ has_cycle แค่อ่าน เรื่อง stable กับ in place เลยใช้กับสองตัวนี้ไม่ได้ ส่วน dedupe_sorted เขียน list ใหม่แบบ in place และเก็บสำเนาแรกของแต่ละค่าไว้ตามลำดับ

ใช้ตอนไหนดี

• array ที่เรียงแล้ว หรือข้อมูลที่ sort ครั้งเดียวแล้ว query หลายครั้ง: ผลรวมของคู่และของสามตัว ผลรวมที่ใกล้ที่สุด นับคู่ที่ต่ำกว่าขอบเขต หา intersection หรือ merge list ที่เรียงแล้วสองชุด
• เขียน array ใหม่แบบ in place ในรอบเดียว: ลบค่าซ้ำหรือของที่ไม่ต้องการ, บีบอัด, partition, กลับด้าน
• linked list ที่ไม่มี index ให้กระโดดไป: node ตรงกลาง, node ที่ k นับจากท้าย, การหา cycle
• การค้นหาไหนก็ตามที่การเทียบพิสูจน์ได้ว่าของที่ปลายข้างหนึ่งไม่มีทางเป็นส่วนของคำตอบที่ดีกว่า แบบโจทย์ภาชนะใส่น้ำ
• ไม่ใช่ตอนที่ไม่มีการเทียบไหนให้ทิ้งฝั่งหนึ่งได้: input ที่ไม่ได้เรียงและการ sort เสียมากกว่าที่ประหยัดได้ หรือคำถามที่ต้องใช้ทุกคู่ (แค่ output อย่างเดียวก็อาจมี O(n²) คู่) ถ้าคำตอบขึ้นกับทุกอย่างที่อยู่ระหว่าง pointer สองตัว อย่างผลรวมของช่วงที่ต่อเนื่องกัน ปลายทั้งสองจะขยับไปข้างหน้า และ sliding window จะเหมาะกว่า

ได้อะไร เสียอะไร

• ต้องมีลำดับอยู่ก่อน การ sort ก่อนเสีย O(n log n) และย้ายของออกจาก index เดิม สำหรับ query แบบตรงตัวครั้งเดียวบนข้อมูลที่ไม่ได้เรียง เวลา O(n) แบบ expected ของ hash set ชนะการ sort
• ค่าซ้ำต้องตัดสินใจ pair_sum หยุดที่คู่แรกที่ตรง ถ้าจะ list ทุกคู่ที่ตรงต้องนับ run ของค่าที่เท่ากันในแต่ละฝั่ง และ list นั้นเองก็อาจยาวถึง O(n²): input ที่ค่าเท่ากันหมดจะตรงทุกคู่
• จากปลายสองข้างต้องถอยหลังได้ hi ขยับไปทางซ้าย แต่ singly linked list ทำแบบนั้นไม่ได้ pair sum บนนั้นเลยต้องใช้ array หรือ doubly linked list ส่วน pattern ทิศเดียวกัน (slow กับ fast, merging) เดินไปข้างหน้าอย่างเดียว
• การบีบอัดทิ้งหางไว้ dedupe_sorted return ความยาวใหม่ และทิ้งค่าเก่าไว้หลังจากนั้น แบบที่ std::unique ของ C++ ทำ ตัดทิ้งด้วย del a[k:] หรือใช้แค่ k ตัวแรก
• Off-by-one และ overflow เงื่อนไข while lo < hi ทำให้ index สองตัวไม่ใช่ตัวเดียวกัน ถ้าใช้ <= จะทำให้ของชิ้นหนึ่งจับคู่กับตัวเองได้ ถ้าใช้ integer แบบ fixed-width ตัว a[lo] + a[hi] อาจ overflow กับค่าใหญ่ ๆ เป็นกับดักเดียวกับ bug ของ midpoint ใน binary search เลยควรขยาย type ให้กว้างขึ้น

ข้อควรรู้ตอนลงมือทำ

• Merge ข้อมูลที่เรียงแล้ว: ขั้น merge ของ Merge Sort ถือ index ไว้หนึ่งตัวต่อหนึ่งครึ่ง list.sort ของ CPython เป็น natural merge sort แบบ adaptive: มัน merge sorted run ที่อยู่ติดกันโดยมี pointer อยู่ในแต่ละ run ก็อป head ที่เล็กกว่าไปที่ output และ gallop ล่วงหน้าเมื่อ run หนึ่งชนะติดกันไปเรื่อย ๆ (listobject.c)
• Merge join: merge join ของ PostgreSQL ถือ cursor ไว้ใน input ที่เรียงแล้วแต่ละฝั่ง และเลื่อนฝั่งที่มี key เล็กกว่า (เอกสาร planner) ส่วนที่ละเอียดอ่อนคือค่าซ้ำ เมื่อ outer row ตัวถัดไปมี key ซ้ำ inner cursor ต้องกลับไปที่ inner row ตัวแรกที่มี key นั้น executor เลย mark ตำแหน่งนั้นไว้แล้วค่อย restore (nodeMergejoin.c)
• Partitioning: quicksort partition ด้วย index สองตัว แบบ Lomuto ขยับไปทางเดียวกัน และแบบ Hoare ขยับเข้าหากัน ส่วน three-way partitioning (Dutch national flag) ทำให้ quicksort ยังเร็วกับ input ที่มี key เท่ากันเยอะ
• กลับด้านแบบ in place: list.reverse() ของ CPython เรียก helper ตัวเล็ก ๆ ชื่อ reverse_slice ที่สลับปลายสองข้างแล้วขยับทั้งคู่เข้าหากันจนมาเจอกัน list.sort ใช้ helper ตัวเดียวกันนี้เปลี่ยน run ที่เรียงจากมากไปน้อยที่มันเจอให้เป็นจากน้อยไปมาก และสำหรับ reverse=True มันจะกลับด้าน list ทั้งก่อนและหลัง stable sort แบบไปข้างหน้า ทำให้ของที่เท่ากันยังอยู่ตามลำดับเดิม slices.Reverse ของ Go กลับด้าน slice แบบ in place
• การบีบอัด: std::unique ของ C++ เก็บตัวแรกของแต่ละ run ของค่าที่เท่ากัน เทียบ n − 1 ครั้งพอดี และ return จุดท้ายเชิงตรรกะใหม่ แล้วปล่อยของที่อยู่หลังจากนั้นไว้ในสถานะที่ valid แต่ไม่ได้ระบุ เลยมักตามด้วยการเรียก erase ของ container ส่วน slices.Compact ของ Go ทำแบบเดียวกันและเติมหางที่เหลือด้วยค่าศูนย์ ใน CPython การลบ extended slice อย่าง del a[::2] บีบอัด list ในรอบเดียว: สำหรับของแต่ละตัวที่ลบ มันเลื่อนกลุ่มของที่เก็บไว้ที่อยู่หลังตัวนั้นลงมาเท่ากับจำนวนที่ลบไปแล้วจนถึงตอนนั้น แล้วค่อยหด list
• การหา cycle: algorithm ของ Floyd และของ Brent หาคาบของ sequence ใด ๆ ที่ได้จากการเรียก function ซ้ำ ๆ โดยใช้ memory O(1) และนี่ก็คือสิ่งที่ Pollard's rho method ต้องการ และใช้ตรวจโครงสร้างที่ link กันว่ามี loop ไหมโดยไม่ต้อง mark node