পাইথনে লিস্টে কোনো সংখ্যা এবং তার পরবর্তী ছোট সংখ্যার মধ্যে সর্বাধিক পার্থক্য বের করা

ধরুন, একটি সংখ্যার লিস্ট nums দেওয়া আছে। আমাদের লিস্টে যেকোনো একটি সংখ্যা এবং তার ठीक পরের ছোট সংখ্যা (Next Smaller Element) এর মধ্যে সর্বাধিক পার্থক্য বের করতে হবে। লক্ষ্য হলো লিনিয়ার টাইম (O(n))-এ সমাধান করা।

উদাহরণস্বরূপ, nums = [14, 2, 6, 35, 12] হলে আউটপুট হবে 21, কারণ ৩৫ এবং ১৪-এর পার্থক্য ২১ যা সর্বোচ্চ।

সমাধানের ধাপসমূহ (Bucket Sort ভিত্তিক পদ্ধতি)

max_val := nums-এর সর্বোচ্চ, min_val := সর্বনিম্ন
যদি max_val == min_val হয়, তবে 0 রিটার্ন করুন।
delta := (max_val - min_val) / (len(nums) - 1)
min_map এবং max_map নামক দুটি ডিকশনারি তৈরি করুন (ডিফল্ট মান যথাক্রমে +∞ এবং -∞)।
প্রতিটি num ∈ nums এর জন্য:
- idx = floor((num - min_val) / delta)
- max_map[idx] = max(max_map[idx], num)
- min_map[idx] = min(min_map[idx], num)
prev := min_val, res := 0
প্রতিটি বাকেট i (০ থেকে n-১) এর জন্য:
- যদি min_map[i] != inf হয়, তবে:
  - res = max(res, min_map[i] - prev)
  - prev = max_map[i]
res রিটার্ন করুন।

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

from collections import defaultdict
import math
class Solution:
    def solve(self, nums):
        max_val = max(nums)
        min_val = min(nums)
        if max_val == min_val:
            return 0
        delta = (max_val - min_val) / (len(nums) - 1)
        min_map = defaultdict(lambda: float("inf"))
        max_map = defaultdict(lambda: float("-inf"))
        res = 0
        for num in nums:
            idx = math.floor((num - min_val) / delta)
            max_map[idx] = max(max_map[idx], num)
            min_map[idx] = min(min_map[idx], num)
        prev = min_val
        for i in range(len(nums)):
            if min_map[i] != float("inf"):
                res = max(res, min_map[i] - prev)
                prev = max_map[i]
        return res

ob = Solution()
nums = [14, 2, 6, 35, 12]
print(ob.solve(nums))

ইনপুট

[14, 2, 6, 35, 12]