HardNo. 2143LeetCode Premium
Choose Numbers From Two Arrays in Range — LeetCode 2143 Python Solution
- Pattern
- Dynamic Programming
- Topics
- Array, Dynamic Programming
- Reading time
- 4 min
- Source
- leetcode.com
The problem
You are given two 0-indexed integer arrays nums1 and nums2 of length n. A range [l, r] (inclusive) where 0 <= l <= r < n is balanced if: For every i in the range [l, r], you pick either nums1[i] or nums2[i].
Example
- Input
- nums1 = [1,2,5], nums2 = [2,6,3]
- Output
- 3
- Explanation
- The balanced ranges are:
Python solution
class Solution:
def countSubranges(self, nums1: List[int], nums2: List[int]) -> int:
n = len(nums1)
s1, s2 = sum(nums1), sum(nums2)
f = [[0] * (s1 + s2 + 1) for _ in range(n)]
ans = 0
mod = 10**9 + 7
for i, (a, b) in enumerate(zip(nums1, nums2)):
f[i][a + s2] += 1
f[i][-b + s2] += 1
if i:
for j in range(s1 + s2 + 1):
if j >= a:
f[i][j] = (f[i][j] + f[i - 1][j - a]) % mod
if j + b < s1 + s2 + 1:
f[i][j] = (f[i][j] + f[i - 1][j + b]) % mod
ans = (ans + f[i][s2]) % mod
return ansComplexity
- Time
- O(n·m) (typical)
- Space · auxiliary
- O(n·m)or optimized
Pattern: Dynamic Programming
Define a state, write the transition, and stop recomputing the same subproblem. LeetCode 2143. Choose Numbers From Two Arrays in Range is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Dynamic Programming.
The dynamic programming guide has the Python template for the pattern and the 481 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 2140 | Solving Questions With Brainpower | Medium |
| 0045 | Jump Game II | Medium |
| 0053 | Maximum Subarray | Medium |
| 0055 | Jump Game | Medium |
| 0063 | Unique Paths II | Medium |
| 0064 | Minimum Path Sum | Medium |
Frequently asked questions
- How hard is LeetCode 2143. Choose Numbers From Two Arrays in Range?
LeetCode 2143. Choose Numbers From Two Arrays in Range is rated Hard on LeetCode.
- What topics does LeetCode 2143. Choose Numbers From Two Arrays in Range cover?
LeetCode 2143. Choose Numbers From Two Arrays in Range is tagged Array and Dynamic Programming on LeetCode.
- Is LeetCode 2143. Choose Numbers From Two Arrays in Range a premium problem?
Yes. LeetCode 2143. Choose Numbers From Two Arrays in Range is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.