পাইথনে লিনিয়ার টাইমে আকার ৩-এর সর্টেড সাবসিকোয়েন্স খুঁজুন

ধরি আমাদের কাছে N সংখ্যার একটি অ্যারে আছে, আমাদের যাচাই করতে হবে কি তিনটি উপাদান আছে যাতে b[i] < b[j] < b[k] এবং i < j < k লিনিয়ার (O(n)) সময়ে। যদি একাধিক такие ট্রিপলেট থাকে, তবে যেকোনো একটি প্রিন্ট করুন।

উদাহরণ

ইনপুট: [13, 12, 11, 6, 7, 3, 31]

আউটপুট: [6, 7, 31]

সমাধানের ধাপসমূহ

1. n := A-এর আকার
2. maximum := n-1, minimum := 0
3. smaller := আকার 1000-এর একটি অ্যারে, 0 দিয়ে পূরণ করা
4. smaller[0] := -1
5. i = 1 থেকে n-1 পর্যন্ত লুপ চালান:
   • যদি A[i] <= A[minimum], তবে minimum := i এবং smaller[i] := -1
   • অন্যথায় smaller[i] := minimum
6. greater := আকার 1000-এর একটি অ্যারে, 0 দিয়ে পূরণ করা
7. greater[n-1] := -1
8. i = n-2 থেকে 0 পর্যন্ত উল্টো লুপ চালান:
   • যদি A[i] >= A[maximum], তবে maximum := i এবং greater[i] := -1
   • অন্যথায় greater[i] := maximum
9. i = 0 থেকে n-1 পর্যন্ত লুপ চালান:
   • যদি smaller[i] != -1 এবং greater[i] != -1, তবে A[smaller[i]], A[i], A[greater[i]] রিটার্ন করুন
10. "Nothing" রিটার্ন করুন

পাইথন কোড উদাহরণ

def find_inc_seq(A):
    n = len(A)
    maximum = n-1
    minimum = 0
    smaller = [0]*10000
    smaller[0] = -1
    for i in range(1, n):
        if (A[i] <= A[minimum]):
            minimum = i
            smaller[i] = -1
        else:
            smaller[i] = minimum
    greater = [0]*10000
    greater[n-1] = -1
    for i in range(n-2, -1, -1):
        if (A[i] >= A[maximum]):
            maximum = i
            greater[i] = -1
        else:
            greater[i] = maximum
    for i in range(0, n):
        if smaller[i] != -1 and greater[i] != -1:
            return A[smaller[i]], A[i], A[greater[i]]
    return "Nothing"

arr = [13, 12, 11, 6, 7, 3, 31]
print(find_inc_seq(arr))

ইনপুট

[13, 12, 11, 6, 7, 3, 31]

আউটপুট

(6, 7, 31)