Grokking the Coding Interview: Patterns for Coding Questions
Ask Author
Back to course home

0% completed

Vote For New Content
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 -

  1. Storing the left/prefix sums in the result array itself
  2. 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
Comments
E
ethanedge 2 years ago

Where is the input array changed? Isn't Manish suggesting you manipulate the result array instead of creating new arrays?

M
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