นับ Subarray ของ Permutation 1..N ที่มี Median เท่ากับ M ใน Python

นับ Subarray ที่ Median = M จาก Permutation 1..N

กำหนดอาร์เรย์ A เป็น Permutation ของ 1..N และตัวเลข M หาจำนวน Subarray ที่ Median เท่ากับ M (Median ของความยาวคู่ = ตัวซ้ายของกลางสองตัว)

ตัวอย่าง: A=[3,5,6,4,2], M=5 → Subarrays: [3,5,6], [5], [5,6], [5,6,4] → 4 ตัว

อัลกอริทึม O(N) ใช้ Prefix Balance

1. แปลงอาร์เรย์: val < M → -1, val > M → +1, val == M → 0
2. คำนวณ Prefix Sum balance จากซ้ายไปขวา
3. ใช้ HashMap นับความถี่ของ balance ก่อนเจอ M
4. หลังเจอ M แล้ว สำหรับแต่ละตำแหน่ง ตรวจสอบ balance และ balance-1 ใน Map → บวกเข้า Result

โค้ดตัวอย่าง Python

def solve(arr, m):
    n = len(arr)
    mp = {0: 1}
    has = False
    bal = 0
    res = 0
    for x in arr:
        if x < m: bal -= 1
        elif x > m: bal += 1
        if x == m: has = True
        if has:
            res += mp.get(bal, 0) + mp.get(bal-1, 0)
        else:
            mp[bal] = mp.get(bal, 0) + 1
    return res

print(solve([3,5,6,4,2], 5))  # 4