Range Sum Queries

easy
prefix-sum

Description

Given an integer array nums, an array queries where queries[i] = [x, y], and an integer limit, return a boolean array that represents the answer to each query. A query is true if the sum of the subarray from index x to y (inclusive) is less than limit, or false otherwise.

Example 1:
Input: nums = [1, 6, 3, 2, 7, 2], queries = [[0, 3], [2, 5], [2, 4]], limit = 13
Output: [true, false, true]
Explanation:
- Query [0, 3]: sum(1+6+3+2) = 12, 12 < 13, so true
- Query [2, 5]: sum(3+2+7+2) = 14, 14 < 13 is false, so false
- Query [2, 4]: sum(3+2+7) = 12, 12 < 13, so true

Example 2:
Input: nums = [1, 2, 3], queries = [[0, 2]], limit = 10
Output: [true]
Explanation: sum(1+2+3) = 6, 6 < 10, so true

Constraints

  • 1 <= nums.length <= 10^5
  • 1 <= queries.length <= 10^5
  • -10^4 <= nums[i] <= 10^4
  • 0 <= x <= y < nums.length
  • -10^9 <= limit <= 10^9

Complexity

Show Complexity
  • Time: O(n + q)
  • Space: O(n)

Hints

Show Hints
Pattern
Prefix sum for O(1) range sum queries
Approach
Compute prefix[i] = sum of nums[0..i-1]. Range sum [x,y] = prefix[y+1] - prefix[x]
Complexity
Build prefix sum in O(n), answer each query in O(1)

Solutions

Show PY Solution 
def solution(nums, queries, limit):
    length = len(nums)

    if length == 0:
        return []

    # preprocess prefix sum
    prefix_sums = [nums[0]]

    for i in range(1, len(nums)):
        prefix_sums.append(nums[i] + prefix_sums[-1])

    ans = []

    for q in queries:
        low, high = q
        s = prefix_sums[high]
        if low > 1:
            s -= prefix_sums[low - 1]

        if s < limit:
            ans.append(True)
        else:
            ans.append(False)

    return ans