โปรแกรมหา Smallest Common Element ในทุก Row ของ Matrix (Python)

ปัญหา

กำหนด 2D matrix ที่แต่ละ row เรียงจากน้อยไปมาก หาตัวเลขน้อยที่สุดที่มีในทุก row ถ้าไม่มี → -1

ตัวอย่าง: [[2,3,5], [5,10,10], [1,3,5]] → 5

วิธีแก้: Set Intersection

ใช้ Set intersection ระหว่างทุก row

อัลกอริทึม

1. ถ้า matrix ว่าง → -1
2. first = set ของ row แรก
3. สำหรับแต่ละ row: first &= set(row) (intersection)
4. ถ้า first ว่าง → -1
5. คืนค่า min(first)

โค้ด Python

class Solution:
    def solve(self, matrix):
        if not matrix:
            return -1
        first = set(matrix[0])
        for row in matrix:
            first &= set(row)
            if not first:
                return -1
        return min(first)

# ทดสอบ
ob = Solution()
matrix = [
    [2, 3, 5],
    [5, 10, 10],
    [1, 3, 5]
]
print(ob.solve(matrix))  # 5

# ไม่มี common
matrix2 = [[1,2,3], [4,5,6], [7,8,9]]
print(ob.solve(matrix2))  # -1

ความซับซ้อน

• Time: O(R × C) - R rows, C columns
• Space: O(C) - set size

วิธีอื่น: 3 Pointers (ใช้ความเรียงลำดับ)

เนื่องจากแต่ละ row เรียงแล้ว ใช้ 3 pointers เดินพร้อมกัน

def solve_three_pointers(self, matrix):
    if not matrix:
        return -1
    R, C = len(matrix), len(matrix[0])
    pointers = [0] * R
    
    while True:
        # หาค่าสูงสุดใน current pointers
        max_val = max(matrix[i][pointers[i]] for i in range(R))
        
        # ขยับ pointers ที่น้อยกว่า max_val
        all_equal = True
        for i in range(R):
            while pointers[i] < C and matrix[i][pointers[i]] < max_val:
                pointers[i] += 1
            if pointers[i] == C:
                return -1
            if matrix[i][pointers[i]] != max_val:
                all_equal = False
        
        if all_equal:
            return max_val

เปรียบเทียบ

LeetCode 1198: Find Smallest Common Element in All Rows

โจทย์นี้คือ LeetCode 1198 โดยตรง