পাইথন - স্ট্রিক্টলি ডিক্রিজিং এবং ইনক্রিজিং সিকোয়েন্স তৈরিতে অংশগ্রহণকারী এলিমেন্ট খুঁজে বের করা

একটি ধনাত্মক সংখ্যার অ্যারে দেওয়া থাকলে, এমন একটি পয়েন্ট খুঁজে বের করতে হবে যেখানে থেকে আগের সিকোয়েন্সটি স্ট্রিক্টলি ডিক্রিজিং (strictly decreasing) এবং পরে স্ট্রিক্টলি ইনক্রিজিং (strictly increasing)। এই পয়েন্টটি "ভ্যালি" (Valley) বা নিম্নতম পয়েন্ট হিসেবে কাজ করে। দুটি সিকোয়েন্সই কমপক্ষে দৈর্ঘ্য ২-এর হতে হবে।

সমস্যা বিবরণ

ইনপুট: [5, 4, 3, 4]
আউটপুট: 3

ব্যাখ্যা: {5, 4, 3} স্ট্রিক্টলি ডিক্রিজিং, {3, 4} স্ট্রিক্টলি ইনক্রিজিং। পিভট = ৩।

অ্যালগরিদম: স্টেট 머신 (State Machine) অ্যাপ্রোচ

def find_valley_element(arr):
    """
    স্ট্রিক্টলি ডিক্রিজিং → স্ট্রিক্টলি ইনক্রিজিং ট্রানজিশন পয়েন্ট খুঁজুন।
    রিটার্ন: পিভট ভ্যালু বা -1 যদি না পাওয়া যায়।
    """
    n = len(arr)
    if n < 4:  # কমপক্ষে ৪ এলিমেন্ট: ২ ডিক্রিজ + ২ ইনক্রিজ (পিভট শেয়ারড)
        return -1
    
    increase = 1  # ইনক্রিজিং সিকোয়েন্স লেন্থ (পিভট সহ)
    decrease = 1  # ডিক্রিজিং সিকোয়েন্স লেন্থ (পিভট সহ)
    pivot = -1
    
    for i in range(1, n):
        if arr[i] < arr[i - 1]:  # ডিক্রিজিং
            if increase == 1:  # এখনও ডিক্রিজিং ফেজে
                decrease += 1
            else:  # ইতিমধ্যে ইনক্রিজিং শুরু হয়েছে, আবার ডিক্রিজিং → ইনভ্যালিড
                return -1
        
        elif arr[i] > arr[i - 1]:  # ইনক্রিজিং
            if increase == 1:  # প্রথম ইনক্রিজিং → পিভট সেট
                pivot = arr[i - 1]
            if decrease >= 2:  # ডিক্রিজিং সিকোয়েন্স ভ্যালিড
                increase += 1
            else:  # ডিক্রিজিং সিকোয়েন্স যথেষ্ট লম্বা নয়
                return -1
        
        else:  # arr[i] == arr[i-1] → স্ট্রিক্ট না, ইনভ্যালিড
            return -1
    
    # শেষে দুটি সিকোয়েন্সই ভ্যালিড কিনা চেক
    if increase >= 2 and decrease >= 2:
        return pivot
    return -1

# টেস্ট
test_cases = [
    [5, 4, 3, 4],           # 3
    [10, 8, 6, 7, 9],       # 6
    [5, 4, 3, 2, 1],        # -1 (শুধু ডিক্রিজিং)
    [1, 2, 3, 4, 5],        # -1 (শুধু ইনক্রিজিং)
    [5, 4, 4, 5],           # -1 (ইকুয়াল ভ্যালু)
    [5, 3, 4, 2, 6],        # -1 (মাল্টিপল ট্রানজিশন)
    [9, 7, 5, 3, 4, 6, 8],  # 3
]

for arr in test_cases:
    print(f"{arr} -> {find_valley_element(arr)}")

আউটপুট

[5, 4, 3, 4] -> 3
[10, 8, 6, 7, 9] -> 6
[5, 4, 3, 2, 1] -> -1
[1, 2, 3, 4, 5] -> -1
[5, 4, 4, 5] -> -1
[5, 3, 4, 2, 6] -> -1
[9, 7, 5, 3, 4, 6, 8] -> 3

অ্যালগরিদম ব্যাখ্যা (State Machine)

এজ কেস হ্যান্ডলিং

• ফ্ল্যাট রিজন (Equal values): স্ট্রিক্ট শর্ত ভাঙায় → ইনভ্যালিড।
• মাল্টিপল ভ্যালি: ডিক্রিজ → ইনক্রিজ → ডিক্রিজ → ইনক্রিজ → ইনভ্যালিড।
• শুধু ইনক্রিজিং/ডিক্রিজিং: একটি ফেজ মিসিং → ইনভ্যালিড।
• পিভট ডুপ্লিকেট: [5, 3, 3, 4] → ইনভ্যালিড (স্ট্রিক্ট না)।

কমপ্লেক্সিটি

• টাইম: O(N) — একক পাস
• স্পেস: O(1) — কনস্ট্যান্ট এক্সট্রা স্পেস

বিকল্প: দ্বি-পাস (Two-Pass) অ্যাপ্রোচ (আসান বোঝার জন্য)

def find_valley_two_pass(arr):
    n = len(arr)
    if n < 4:
        return -1
    
    # ১. বাম থেকে ডিক্রিজিং লেন্থ
    dec_len = [1] * n
    for i in range(1, n):
        if arr[i] < arr[i-1]:
            dec_len[i] = dec_len[i-1] + 1
        else:
            dec_len[i] = 1
    
    # ২. ডান থেকে ইনক্রিজিং লেন্থ
    inc_len = [1] * n
    for i in range(n-2, -1, -1):
        if arr[i] < arr[i+1]:
            inc_len[i] = inc_len[i+1] + 1
        else:
            inc_len[i] = 1
    
    # ৩. পিভট খুঁজুন: dec_len[i]>=2 এবং inc_len[i]>=2
    for i in range(1, n-1):
        if dec_len[i] >= 2 and inc_len[i] >= 2:
            return arr[i]
    
    return -1