Range Sum Queries With Prefix Sums
Updated
Problem statement
You are given an integer array nums and a list of queries. Each query [left, right] asks for the sum nums[left] + nums[left + 1] + ... + nums[right] (both ends included, indices start at 0).
Return an array whose i-th value is the answer to queries[i]. A sum can be larger than a 32-bit integer can hold, so return 64-bit integers.
Aim to build a prefix-sum array once in O(n) time and then answer each query in O(1). At these sizes the judge cannot tell this apart from adding each range one value at a time, so the goal is not checked.
Function
rangeSums(nums: int[], queries: int[][]) → long[]Examples
Example 1
nums = [3,-1,4,-1,5]queries = [[0,2],[1,3],[4,4]]return = [6,2,5]Indices 0 to 2 hold 3, -1 and 4, which add up to 6. Indices 1 to 3 give -1 + 4 + -1 = 2. Index 4 alone gives 5.
Example 2
nums = [1000000000,1000000000,1000000000]queries = [[0,2],[0,0]]return = [3000000000,1000000000]The first range adds up to 3000000000, which is too big for a 32-bit integer. A 64-bit total is needed.
Example 3
nums = [-7]queries = [[0,0]]return = [-7]A single number: the only range is index 0 to 0, and its sum is -7.
Constraints
1 <= nums.length <= 10^4-10^9 <= nums[i] <= 10^91 <= queries.length <= 1500queries[i] = [left, right]with0 <= left <= right < nums.length
More Adobe Phone Screen questions
- Evaluate a Parenthesized Integer ExpressionPHONE SCREEN · Seen Oct 2026
- All Elements of Two BSTs in OrderPHONE SCREEN · Seen Aug 2026
- Rotate an Array In PlaceOA · PHONE SCREEN · Seen Aug 2026
- Binary Tree Level-Order Traversal by LevelsPHONE SCREEN · ONSITE INTERVIEW · Seen Aug 2026
- Count Occurrences in a Sorted ArrayPHONE SCREEN · ONSITE INTERVIEW · Seen Jul 2026
- Count Pairs with Absolute Difference KPHONE SCREEN · Seen Jul 2026
- Count Subsets with Sum KPHONE SCREEN · Seen Jul 2026
- Numbers with Exactly Three DivisorsPHONE SCREEN · Seen Jul 2026
- Sum of Even Nodes on a Path in a Numbered Binary TreePHONE SCREEN · Seen Jul 2026
- Largest Value in Every Sliding WindowPHONE SCREEN · Seen Jul 2026
Similar questions at other companies
- Wallet Balance on a Selected DayBharatPe · PHONE SCREEN
- Index With Equal Sums on Both SidesBloomberg LP · PHONE SCREENBloomberg LP interview questions
- Parking-Lot Occupancy TimelineGoogle · PHONE SCREENGoogle interview questions
- Calculate Server Shutdown PenaltyStripe · PHONE SCREEN · ONSITE INTERVIEWStripe interview questions
- Find an Equal-Sum SplitMeta · PHONE SCREENMeta interview questions
- Peak Chat Load Across AgentsCresta · PHONE SCREENCresta interview questions
- Trapping Rain WaterGoldman Sachs · PHONE SCREENGoldman Sachs interview questions
- Count Non-Overlapping Pairs of Rectangles That Sum to KWisdomAI · PHONE SCREEN
- Best Improvement Period of at Least K IntervalsAmazon · PHONE SCREEN
- Majority Labels over Audio IntervalsNooks · PHONE SCREEN