0% completed
Presented solution should be optimized further
Manish Giri
Nov 12, 2023
In the presented solution, you are creating and storing two additional arrays, for storing the prefix and suffix sums. For a brute force solution, this is fine but you should provide an optimized version. It's disappointing that such a solution is not given.
There is no need to create additional arrays that cause O(n) space complexity. This can be done in O(1) space by -
- Storing the left/prefix sums in the result array itself
- Use an int variable to hold the right/suffix sum and manipulate the result array itself.
Solution -
public class Solution { public int[] findDifferenceArray(int[] nums) { int n = nums.length; int[] differenceArray = new int[n]; int currLeftSum = 0; for(int i = 0; i < n; i++) { if(i == 0) { differenceArray[i] = 0; } else { currLeftSum += nums[i-1]; differenceArray[i] = currLeftSum; } } int currRightSum = 0; for(int i = n-1; i >= 0; i--) { differenceArray[i] = Math.abs(differenceArray[i] - currRightSum); currRightSum += nums[i]; } return differenceArray; }
2
0
Comments
ethanedge 2 years ago
Where is the input array changed? Isn't Manish suggesting you manipulate the result array instead of creating new arrays?
Matthew Ibarra2 years ago
While this is better space, it's still O(N) space because your differenceArray is going to always be of size n.
I believe in DGs answer, they thought you were getting O(1) but just modifying the input array directly to avoid making an extra array. Just a misunderstand ...
On this page
Problem Statement
Examples
Solution
Step-by-step Algorithm
Algorithm Walkthrough
Code
Complexity Analysis
Time Complexity
Space Complexity