Range Sum Query – Immutable Given an integer array nums
, handle multiple queries of the following type:
- Calculate the sum of the elements of
nums
between indicesleft
andright
inclusive whereleft <= right
.
Implement the NumArray
class:
NumArray(int[] nums)
Initializes the object with the integer arraynums
.int sumRange(int left, int right)
Returns the sum of the elements ofnums
between indicesleft
andright
inclusive (i.e.nums[left] + nums[left + 1] + ... + nums[right]
).
Example 1:
Input ["NumArray", "sumRange", "sumRange", "sumRange"] [[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]] Output[null, 1, -1, -3]
Explanation NumArray numArray = new NumArray([-2, 0, 3, -5, 2, -1]); numArray.sumRange(0, 2); // return (-2) + 0 + 3 = 1 numArray.sumRange(2, 5); // return 3 + (-5) + 2 + (-1) = -1 numArray.sumRange(0, 5); // return (-2) + 0 + 3 + (-5) + 2 + (-1) = -3
Constraints:
1 <= nums.length <= 104
-105 <= nums[i] <= 105
0 <= left <= right < nums.length
- At most
104
calls will be made tosumRange
.
Range Sum Query – Immutable Solutions
✅Time: O(n)
✅Space: O(n)
C++
class Solution:
def removeInvalidParentheses(self, s: str) -> List[str]:
def getLeftAndRightCounts(s: str) -> tuple:
l = 0
r = 0
for c in s:
if c == '(':
l += 1
elif c == ')':
if l == 0:
r += 1
else:
l -= 1
return l, r
def isValid(s: str):
count = 0 # number of '(' - # of ')'
for c in s:
if c == '(':
count += 1
elif c == ')':
count -= 1
if count < 0:
return False
return True # count == 0
ans = []
def dfs(s: str, start: int, l: int, r: int) -> None:
if l == 0 and r == 0 and isValid(s):
ans.append(s)
return
for i in range(start, len(s)):
if i > start and s[i] == s[i - 1]:
continue
if r > 0 and s[i] == ')': # delete s[i]
dfs(s[:i] + s[i + 1:], i, l, r - 1)
elif l > 0 and s[i] == '(': # delete s[i]
dfs(s[:i] + s[i + 1:], i, l - 1, r)
l, r = getLeftAndRightCounts(s)
dfs(s, 0, l, r)
return ans
Java
class NumArray {
public NumArray(int[] nums) {
prefix = new int[nums.length + 1];
for (int i = 0; i < nums.length; ++i)
prefix[i + 1] = nums[i] + prefix[i];
}
public int sumRange(int left, int right) {
return prefix[right + 1] - prefix[left];
}
private int[] prefix;
}
Python
class NumArray:
def __init__(self, nums: List[int]):
self.prefix = [0] + list(itertools.accumulate(nums))
def sumRange(self, left: int, right: int) -> int:
return self.prefix[right + 1] - self.prefix[left]
Watch Tutorial
Checkout more Solutions here