Compute balances and array queries

Question

Given a list of transactions where each transaction has a userId and an amount (positive for credit, negative for debit), compute the final balance for every userId. LeetCode 209. Minimum Size Subarray Sum – Given an array of positive integers nums and an integer target, return the minimal length of a contiguous subarray whose sum is at least target; return 0 if none exists. LeetCode 307. Range Sum Query – Mutable – Design a data structure that supports point updates and range-sum queries on an integer array.

https://leetcode.com/problems/minimum-size-subarray-sum/description/ https://leetcode.com/problems/range-sum-query-mutable/description/

Compute Final Balances per User

Given a list of transactions where each transaction is a pair [userId, amount] (amount positive for a credit, negative for a debit), compute the final balance for every userId. Return a map from each userId to its net balance.

Users may appear multiple times across transactions; sum all of a user's amounts. A user's net balance may be zero or negative.

Example: [['a',100],['b',50],['a',-30],['b',20],['c',75]] -> {'a':70,'b':70,'c':75}.

Constraints

• 0 <= number of transactions <= 10^5
• Each amount fits in a 32-bit signed integer
• userId is a non-empty string
• A user's net balance may be zero or negative

Hints

1. A single hash map keyed by userId is enough.
2. Accumulate each amount into the running total for its userId; you only need one pass.
3. Use get(userId, 0) (or equivalent) so the first transaction for a new user starts from 0.

Minimum Size Subarray Sum (LeetCode 209)

Given an array of positive integers nums and an integer target, return the minimal length of a contiguous subarray of which the sum is greater than or equal to target. If there is no such subarray, return 0.

The signature is solution(target, nums).

Example: target=7, nums=[2,3,1,2,4,3] -> 2 (the subarray [4,3]).

Constraints

• 1 <= target <= 10^9
• 0 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^4 (all elements are positive)

Hints

1. All elements are positive, so a sliding window's sum grows when you extend the right end and shrinks when you advance the left end.
2. Expand the window to the right; whenever the running sum is >= target, record the length and contract from the left.
3. Track the minimum window length seen; return 0 if the total sum never reaches target.

Range Sum Query - Mutable (LeetCode 307)

Design a data structure that supports point updates and range-sum queries on an integer array, then replay a sequence of operations against an initial array.

The driver signature is solution(nums, operations) where nums is the initial array and operations is a list of operations applied in order:

• ['update', i, val] sets nums[i] = val.
• ['sumRange', l, r] returns the inclusive sum of nums[l..r].

Return the list of results, one entry per sumRange operation, in order.

Example: nums=[1,3,5], operations=[['sumRange',0,2],['update',1,2],['sumRange',0,2]] -> [9, 8].

Constraints

• 1 <= nums.length <= 3 * 10^4
• -100 <= nums[i], val <= 100
• 0 <= i, l, r < nums.length and l <= r
• 0 <= number of operations <= 3 * 10^4

Hints

1. A Fenwick tree (Binary Indexed Tree) or a segment tree supports both point updates and range-sum queries in O(log n).
2. For an update, apply the delta (newVal - currentVal) to the structure and remember the new current value so the next update on that index uses the correct delta.
3. Compute a range sum [l, r] as prefix(r) - prefix(l - 1); be careful with 0- vs 1-based indexing inside the BIT.