Linear time; Combinations; Difference sequence
Intuition\nWe need to find an non-decreasing suquence $a$ and a non-increasing sequence $b$ such that $a(i)+b(i)=nums[i]$. Instead of finding $a$ and $b$, we fi
# Intuition\nWe need to find an non-decreasing suquence $a$ and a non-increasing sequence $b$ such that $a(i)+b(i)=nums[i]$. Instead of finding $a$ and $b$, we find the number of valid difference sequence $d$ of $a$.\n\n# Approach\nLet $d$ be the difference sequence of $a$, i.e., $d(i)=a(i)-a(i-1)$. By the constraints, we have $d(i)\\geq \\max(0,nums[i]-nums[i-1])$. Thus, the problem is trnasformed to the number of sequences $d$ of length $n$ such that $d(i)\\geq \\max(0,nums[i]-nums[i-1])$ and $0\\leq sum(d) \\leq nums[-1]$, or equivalently $d$ has length $n+1$ and $sum(d)=nums[-1]$. The answer is the combination $C(p+n,p)$, where $p$ is $nums[-1]-\\sum_i \\max(0,nums[i]-nums[i-1])$. \n\n# Complexity\n- Time complexity: $O(n+m)$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $O(1)$ extra space\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution:\n    # i<=j and x-i>=y-j, j>=y-x+i; j>=i+max(0,y-x)\n    # d(i) >= max(0,nums[i]-nums[i-1])\n    def countOfPairs(self, nums: List[int]) -> int:\n        mod = 10**9+7\n        d = nums[-1] - sum(max(0,v-u) for u,v in zip(nums,nums[1:]))\n        if d<0: return 0\n        n = len(nums)\n        # total diff, for i in [0,d], partition into n nonnegative\n        ans = comb(n+d,d)%mod\n        return ans\n        \n```
['Python3']