O(N) Time Complexity and O(1) Space complexity video solution

Tags: #<Tag:0x00007f2424ec0ac8> #<Tag:0x00007f2424ec0960>


This question can be solved in O(N) Time and O(1) space complexity by using simple mathematics concepts of absolute operator.

We can deduce this express into 4 different forms after removing the absolute operator and applying specific conditions.

Cases can be A[i]>A[j] or A[i]<=A[j] and simultaneously i>j and i<=j can be the cases so using these conditions we can formulate 4 different expressions which do not involve use of absolute operator.
After that we just need to find the maximum value possible through each expression by iterating on array of numbers only once.

If you still face any difficulties while solving this question then you can refer to the video solution

Video Link:- https://youtu.be/Ov4weYCIipg


Great Video Solution Vaibhav! I have a doubt that when we have cases (a[I]+i )-(a[j]+j) when I>j and a[I]>a[j] so when we compute max and min for (a[I]+i) for every value of i we will have 2 cases:
Consider we get max at index i and min at index j
so there are two cases
(i) i>j
how do we confirm that at that maximum value we have a[i] also greater than a[j]
(ii) j>i