Range Sum Query Immutable - Leetcode 303 - Python

แชร์
ฝัง
  • เผยแพร่เมื่อ 27 พ.ย. 2024

ความคิดเห็น • 12

  • @cesarfa-b3t
    @cesarfa-b3t ปีที่แล้ว +7

    A trick I like to use for the prefix array is to subtract left and add nums[left] instead of going one position over so we don't have to worry about boundary check, for example: prefix[right] - prefix[left] + nums[left]

    • @samcarter8828
      @samcarter8828 ปีที่แล้ว

      Nice trick

    • @gradientO
      @gradientO ปีที่แล้ว +1

      but that requires us to store the nums array. Using prefix array, we dont need that

    • @tsunami8892
      @tsunami8892 ปีที่แล้ว +1

      also that can be - prefix[right] - (prefix[left - 1] || 0)

    • @ChrisCox-wv7oo
      @ChrisCox-wv7oo ปีที่แล้ว

      prefix[-1] returns the last element in Python

  • @shavvasatya7131
    @shavvasatya7131 ปีที่แล้ว +5

    Great as usual.

  • @flatmapper
    @flatmapper ปีที่แล้ว +2

    2:00 Why O(n^2)?
    O(n^2) is the time complexity of finding pairs.
    Intuitively the time complexity is greater to find every subarray

    • @MsPokemonmaster145
      @MsPokemonmaster145 4 หลายเดือนก่อน

      He is saying that the number of subarrays is O(n^2) (To be exact, n*(n-1)). You are right tho to find all sums it would take O(n^3).

  • @sanooosai
    @sanooosai 9 หลายเดือนก่อน

    thank you

  • @flatmapper
    @flatmapper ปีที่แล้ว

    Amazing!

  • @MianyunNi
    @MianyunNi ปีที่แล้ว

    what if left = 0, right = 0; -2 + (-2)

  • @mehedihassan-pf6yh
    @mehedihassan-pf6yh 6 หลายเดือนก่อน +1

    You wrote left > 0 then but as index , left can be 0 to indicate first index