مساعدة في حل مسألة "Zero array transformation" من موقع "LeetCode"

ما قمت به جيد كبداية، لكن بطيء بسبب التعقيد الزمني،  حيث أنك تعيد معالجة كل عنصر في النطاق لكل استعلام، ويتحقق من المصفوفة بأكملها بعد كل خطوة، ولا حاجة لإعادة معالجة العناصر التي أصبحت 0 بالفعل، والتحقق المتكرر من المصفوفة بأكملها مكلف من حيث التعقيد الزمني.

بالتالي عليك تقليل عدد العمليات لكل استعلام، وتتبع متى تصبح العناصر صفراً بطريقة أكثر كفاءة، الفكرة هي الإعتماد على مصفوفة التأثير Difference Array أو تتبع المتبقي لتجنب معالجة كل عنصر بشكل فردي في كل استعلام مع استخدام هيكل بيانات كقائمة أو مجموعة لتتبع العناصر غير الصفرية فقط.

واحتفظ بنسخة من المصفوفة الأصلية لتتبع القيم المتبقية، ثم لكل استعلام قم بتطبيق التخفيض على النطاق [l,r] باستخدام قيمة val، وتتبع عدد العناصر التي أصبحت 0 بعد كل استعلام، ثم أوقف العملية بمجرد أن تصبح جميع العناصر 0.

class Solution:
    def minZeroArray(self, nums, queries):  
        n = len(nums)
        
        if all(num == 0 for num in nums):
            return 0
        
        remaining = nums[:]  
        non_zero_count = sum(1 for x in nums if x > 0)
        
        for i, (start, end, val) in enumerate(queries):
            if start < 0 or end >= n or start > end:
                continue
                
            for j in range(start, end + 1):
                if remaining[j] > 0:  
                    old_val = remaining[j]
                    remaining[j] = max(0, remaining[j] - val)
                    if old_val > 0 and remaining[j] == 0:
                        non_zero_count -= 1
            
            if non_zero_count == 0:
                return i + 1
        
        return -1

لاحظ متغير non_zero_count لمعرفة عدد العناصر التي ما زالت أكبر من 0، وذلك يلغي الحاجة لاستخدام all() في كل خطوة لتقليل التعقيد.

لا تزال لدي نفس المشكلة. 

الحل صحيح، أين المشكلة؟

المشكلة تظهر لي عند الحالة "623" (مثل الكود الخاص بي) , عند الضغط على Submit

نحتاج إذن إيجاد أقل عدد ممكن من الاستعلامات الأولى التي تكفي لجعل المصفوفة كلها أصفارًا، وذلك من خلال البحث الثنائي نبدأ بتجربة عدد معين من الاستعلامات منتصف العدد الكلي، ثم نرى هل  العدد كافٍ لجعل المصفوفة صفرية أم لا، في حال كافٍ، نحاول عددًا أقل، ولو العكس نجرب عدد أكبر، وتلك طريقة سريعة لإيجاد العدد الأمثل.

ثم مصفوفة الفروق  لتطبيق التغييرات على مدى معين من الأرقام في المصفوفة بسرعة بدلاً من تغيير كل رقم في المدى مباشرة، حيث نغير فقط أول وآخر رقم في المدى بطريقة معينة، ثم نحسب المجموع التراكمي لاحقًا لنرى التأثير على كل رقم.

وبعد استخدام مصفوفة الفروق وتطبيق تأثير الاستعلامات، نحسب المجموع التراكمي للأرقام، وهو يمثل القيمة النهائية لكل رقم في المصفوفة بعد تطبيق الاستعلامات، ونتأكد هل كل القيم أصبحت صفرًا أم لا.

class Solution:
    def minZeroArray(self, nums, queries):
        n = len(nums)
        q = len(queries)
        
        if all(x == 0 for x in nums):
            return 0
        
        left, right = 0, q
        answer = -1
        
        while left <= right:
            mid = (left + right) // 2
            diff = [0] * (n + 1)
            for i in range(mid):
                l, r, val = queries[i]
                diff[l] += val
                if r + 1 < n:
                    diff[r + 1] -= val
                else:
                    pass
            
            current_sum = 0
            valid = True
            for j in range(n):
                current_sum += diff[j]
                if current_sum < nums[j]:
                    valid = False
                    break
            
            if valid:
                answer = mid
                right = mid - 1
            else:
                left = mid + 1
        
        return answer if answer != -1 else -1