Jatin-Shihora

Property of Modulus :-

Evaluate | a - b |
Case 1 :- (a-b) ; a>b
Case 2 :- (b-a) ; a<=b

Now,

Given Equation :- | a[i] - a[j] | + | i - j |

Jatin-Shihora

Monotonic Stack:

Whenever a problem requires enumerating values for indices on the basis of other values in an array, one should think of including a stack in the solution! And that too, a monotonic stack. It is simply a stack which contains values in a monotonic order; i.e either increasing or decreasing.

Imagine there is a data structure which contains the indices whose temperatures are in an increasing order. Then, enumerating the next index which has a greater temperature will be easy: we simply pop the elements till the top element has a greater temperature than the current index! Refer to the following picture for better understanding.

For example:

Imagine that the stack contains the indices {4, 5, 6, 7, 8} which have temperatures {10, 12, 14, 18, 20}. We are traversing from reverse and are currently at index 3 which has a temperature of 16 (indicated by the grey block). To find the next

Jatin-Shihora

Whenever we declare a vector like:

vector<int> v;

Here, we do not specify the size of our vector. Whenever we just want to add an element we just push it into the vector using the v.push _ back(val) function (where val is the value you want to push).

Suppose you haven't added any elements into the vector. Now, if you go on access any element position like v[0] or v[7] like one can when he declares an array, you will get a runtime error. Why? Because vectors are dynamic in nature. Since, you haven't declared any size or pushed any element it's size is zero. So no element exists right now.

But if you declare it using: