You are given an integer array nums and an array queries where queries[i] = [vali, indexi].
For each query i, first, apply nums[indexi] = nums[indexi] + vali, then print the sum of the even values of nums.
Return an integer array answer where answer[i] is the answer to the ith query.
Example 1:
Input: nums = [1,2,3,4], queries = [[1,0],[-3,1],[-4,0],[2,3]] Output: [8,6,2,4] Explanation: At the beginning, the array is [1,2,3,4]. After adding 1 to nums[0], the array is [2,2,3,4], and the sum of even values is 2 + 2 + 4 = 8. After adding -3 to nums[1], the array is [2,-1,3,4], and the sum of even values is 2 + 4 = 6. After adding -4 to nums[0], the array is [-2,-1,3,4], and the sum of even values is -2 + 4 = 2. After adding 2 to nums[3], the array is [-2,-1,3,6], and the sum of even values is -2 + 6 = 4.
Example 2:
Input: nums = [1], queries = [[4,0]] Output: [0]
Constraints:
1 <= nums.length <= 104-104 <= nums[i] <= 1041 <= queries.length <= 104-104 <= vali <= 1040 <= indexi < nums.lengthIn this approach, we will maintain a running sum of even numbers. For each query, before updating the number at the given index, we check if it's even and subtract it from our running total if it is. After updating, we check if the new number is even and add it to the total if it is. This method avoids recalculating the sum of all even numbers from scratch after each query, thus optimizing the solution.
We first calculate the initial sum of even numbers. For each query, if the number at the query index in nums is even, we subtract it from the evenSum. We then apply the query change and check if the new number is even. If so, add it to the evenSum. This way, each query is processed in constant time.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n + m), where n is the length of nums and m is the number of queries.
Space Complexity: O(1), as we use only constant extra space.
This approach calculates the sum of even numbers from scratch after each query. Though straightforward, it may not be the most efficient, as it recalculates the sum fully rather than in an incremental manner.
Each query is independently processed by updating the indicated index and recalculating the entire array's evenSum afterward. While direct, this method lacks the efficiency of the first approach as every query starts with a new sum computation.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n * m), as the even sum is recalculated n times for each query m.
Space Complexity: O(1), aside from the storage for results.
| Approach | Complexity |
|---|---|
| Incremental Update Approach | Time Complexity: O(n + m), where n is the length of nums and m is the number of queries. |
| Recompute Even Sum After Each Query | Time Complexity: O(n * m), as the even sum is recalculated n times for each query m. |
LeetCode Sum of Even Numbers After Queries Solution Explained - Java • Nick White • 5,612 views views
Watch 9 more video solutions →Practice Sum of Even Numbers After Queries with our built-in code editor and test cases.
Practice on FleetCode