This is our solution and implementation to problem #985: Sum of Even Numbers After Queries on LeetCode.
Our code is written in Java. If you want to code your solution in a different language, no worries, as the core concepts will carry over from language to language. This page includes our analysis of the problem, our implementation strategy a breakdown on the space and time complexity, and the full code implementation.
If you would like to view the original problem and solve it, please visit: Sum of Even Numbers After Queries on LeetCode.
Problem Analysis
We are given an input array nums and an array of arrays queries. We can consider queries to be an array where each element has two items, meaning we do not need to think much about it being an array of arrays. Each query within queries has two items:
- A value which will be used to modify an entry in nums.
- An index which points to a particular entry in nums. During each query, we'll:
- Modify the number at index in nums by adding val to its existing value.
- Determine the sum of all even numbers in nums including the modification we've just made.
- Record that sum in an array which we'll return at the end.
A simple way of implementing an algorithm to satisfy this would be to: for each query, modify nums as described above and then iterate through nums to calculate the sum of even numbers. This approach will get the job done, but not in an efficient manner. If we analyze it's time complexity, we'll see that for each item in queries, we need to iterate through the entire array of nums, making the time complexity O(n*q), which is analagous to O(n^2).
To make this more efficient, we'll need to see if there's any way we can avoid iterating through nums for every single query. The reason the approach described above required this was to re-calculate the sum of even numbers, but we should be able to re-use calculations from previous runs to find the sums more efficiently. The section below will describe how to do just that.
Implementation Strategy
We will re-use calculations of even-number sums by keeping a running sum value as we iterate through the queries. When we make updates based on the val and index provided by the query, we'll update that running sum based on whether our new value is even and whether the old nums value was even. With this, we only need to perform a summation once at the beginning, then we can work with a single number value throught the rest of the algorithm. The full steps are given below:
- Iterate through nums, take a sum of the even numbers, and store in evenSums.
- For each query:
- Determine the combined value of the query's val plus nums[query-index], where query-index is the index value provided by the query.
- If nums[query-index] was even, subtract it from evenSums.
- If combined is even, add it to evenSums.
- Set nums[query-index] to combined.
- Add evenSums to the list of answers.
- Return the list of answers.
Space and Time Complexity
This solution has a time complexity of O(n+q), where n is the number of elements in nums and q is the number of queries. The space complexity is O(1), not including the return value itself, as it only needs to use a constant number of variables throughout.
Full Code
Our solution is given in the Java files below. This solution uses more than one code file. The Main.java file is used as a runner to test locally and includes a few test cases, some from the examples provided by LeetCode and some designed for our own test purposes. The Solution.java file contains the main logic for the solution.
All of our solutions are hosted on GitHub. The code on this page was pulled from the repo.