Sum of Absolute Differences in a Sorted Array | Build Intuition | 2 Approaches | Leetcode - 1685

This is the 72nd Video of our Array Playlist.
In this video we will try to solve a very good and tricky problem - Sum of Absolute Differences in a Sorted Array (Leetcode -1685).

I will explain the intuition so easily that you will never forget and start seeing this as cakewalk EASYYY.
We will do live coding after explanation and see if we are able to pass all the test cases.

Problem Name : Sum of Absolute Differences in a Sorted Array
Company Tags : ADOBE

╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝

#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge#leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview#interviewtips #interviewpreparation #interview_ds_algo #hinglish #github #design #data #google #video #instagram #facebook

[ytritik-stgr]

Bhaiya please it's a request from my side, never stop teaching .... you are a true gem in teaching

[wearevacationuncoverers]

0:09 This always boosts my confidence.

[codeandtalk]

Absolute makes problem hard 😢 but bro explained like ❤❤❤❤

[deepakdass]

Sir, ONE REQUEST from my side

I have been following your channel since last 2 months. I just love your teaching style, you have helped me a lot in making my problem solving skills better. I am about to start following your GRAPH playlist after my exams end. I have one request for you.

Please try to make videos for LEETCODE contests as well, if possible, I think that will help us to learn devloping intuition in contest.

[nirmaljaat]

Very Easy to Understand

class Solution {
public:
vector<int> nums) {
int sum=0;
for(int & i: nums){
sum+=i;
}
int n=nums.size();
vector<int> ans;
int l=nums[0];

sum-=nums[0];
for(int i=1;i<n;i++){
int rs=sum-nums[i]*(n-i);
int ls=abs(l-(nums[i]*i));
ans.push_back(rs+ls);

sum-=nums[i];
l+=nums[i];
}
return ans;
}
};

[Ramneet]

I got the intuition that we have to make and imade two arrays prefix and suffix sum array but unable to get the formula.Glad I came up till this solution, I even solved yesterday's, say before yesterday question by own, thx a lot, even did with 0(1) space solution.

[DeepakSingh-fdix]

Sir, this biweekly contest question about finding the minimum number of coins for fruits seems quite tricky and interesting. If you could explain it, it would help me a lot

[infinitygaming]

solved this question without any hints

[dchennaraidu]

Bhai, legend ho app! 🙏🏼 Appreciate your skills and patience to break it down and explain clearly!

[infinitygaming]

class Solution:
def getSumAbsoluteDifferences(self, nums: List[int]) -> List[int]:
prefix_sum = [nums[0]]
for i in range(1, len(nums)):
prefix_sum.append(nums[i] + prefix_sum[i-1])
arr = []
for i in range(len(nums)):
left = ((nums[i]*(i+1) )-prefix_sum[i])
right = (nums[i]*(len(nums) - (i+1))) - (prefix_sum[-1] - prefix_sum[i])
term = abs(left) + abs(right)
arr.append(term)
return arr

[de_coder]

Was able to do it by approach 1, calculating prefix sum on the way was good.

[thor]

Solved the question by my own after looking at the test cases, but watching your video made me understand the underlying logic.

My java sol : (3 ms Beats 99.36% of users with Java.)


class Solution {
public int[] nums) {
int len = nums.length;
int[] prefixSum = new int[len + 1];
prefixSum[0] = 0;
int sum = 0;
int index = 1;
for (int i = 0; i < len; i++) {
sum += nums[i];
prefixSum[index] = sum;
index++;
}
for (int i = 0; i < len; i++) {
int x = (prefixSum[len] - prefixSum[i]) - (nums[i] * (len - i));
int y = (nums[i] * i) - prefixSum[i];
nums[i] = x + y;
}
return nums;
}
}

[dhairyachauhan]

Took me like 40 mins to think of the solution but happy to tell that i did it on my own :)

my solution :-

class Solution {
public:
typedef long long ll;
vector<int> nums) {
int n = nums.size();
vector<ll>prefix(n, 0);
vector<ll>suffix(n, 0);

int sum = 0;
for(int i = 0;i<n;i++){
sum += nums[i];
prefix[i] = (i+1)*nums[i] - sum;
}
sum = 0;
for(int j = n-1;j>=0;j--){
sum += nums[j];
suffix[j] = sum - (n-j)*nums[j];
}

vector<int>ans(n, 0);
for(int i =0 ;i<n;i++){
ans[i] = prefix[i] + suffix[i];
}

return ans;

}
};

INTUITION :-
I OBSERVED A PATTERN [2, 3, 5]
2 -> N, -VE, -VE
3-> +VE, N,-VE
5-> +VE, +VE, N

THE ABSOLUTE VALUE OF 2 AND 5 WERE CORRECT BUT NOT FOR 3 REASON BEING THERE WAS
ONE +VE AND ONE -VE, EITHER USE ALL +VE OR ALL -VE.

SO I THOUGH SINCE IT WAS SORTED ALL THE VALUES TILL AND BEFORE THE CURRENT NO. WILL ALWAYS BE POSITIVE SO I STORED
(CURRENT NO. * LENGTH - SUM TILL THE LENGTH IN THE ARRAY) [prefix[i] = (i+1)*nums[i] - sum;]
EG:

[2, 3, 5]

AND SINCE THE OTHER HALF WOULD CAUSE A PROBLEM I STORED

[2, 3, 5]
IN THE SUFFIX ARRAY AS (suffix[j] = sum - (n-j)*nums[j];)
NOW BOTH WILL BE POSITIVE AND I WILL GET MY ANSWER.

YES I COULD HAVE USED ONLY ONE PREFIX ARRAY BUT IT IS MORE UNDERSTANDABLE IN 2 ARRAYS.

[thekindspill]

Done. It was easy as compared to usual Weekends problems. Thanks a lot for your explanation

[sauravchandra]

Seemed like an easy one, and like always your way of thinking is so clear and your explanations so simple.

My implementation:
class Solution {
public:
vector<int> nums) {
int n=nums.size(), pre=0;
vector<int> preSum(n, 0);

for(int i=0;i<n;i++){
pre+=nums[i];
preSum[i]=pre;
}

for(int i=n-1;i>=0;i--){
int leftSum = (pre-preSum[i]) - (nums[i]*(n-1-i));

int rightSum= 0;
if(i>0) rightSum += (nums[i]*i)-preSum[i-1];

preSum[i]=leftSum+rightSum;
}

return preSum;
}
};

[biswarupacharjya]

Sir if possible linklist playlist 🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

[crazyduniya]

how you get confidence to directly submit your code, without running on example test cases

[factsmotivation]

Anyone can say me how can i join whatapp group, i am unable to join whatapp group, help...

[dayashankarlakhotia]

public int getSumAbsoluteDifferences (int[]nums){
int n=nums.length;
int[]ans=new int [n];int[]prefix =new int [n]; int[]suffix =new int [n];
prefix[0]=nums[0];
for(int i=1;i<n;i++)
prefix [i]=prefix [i-1]+nums[i];
suffix [n-1]=nums[n-1];
for(int i=n-2;i>=0;i--){
suffix [i]=suffix [i+1]+nums[i];
for(int i=0;i<nums.length;++i){
int left=nums[i]*(i+1)-prefix[i];
int right =suffix[i]-nums[i]*(n-i);
ans[i]=left +right;
}
return ans;
}
}
🎉😂❤