Okay, so in this question my first instinct was that it's a 2D problem. I have been given multiple points on a 2D plane and I have to find the points whose summation distance is minimum from all the given points. My initial guess was to check all the points enclosed in the polygon formed by the given points and find out which points have the min summation distance from all given points but it obviously gave TLE. Eventually, I looked at the solution.

From the solution, I realized that I had to make two observations: 1st. The way of measuring distance is "summation distance" It is just |x2-x1| +|y2-y1| and not sqrt((x2-x1)^2+(y2-y1)^2). What this allows us to see is that if I have a point p1, then it's summation distance from all given points(q1,q2,q3...qn) is

|qx1-px1| + |qy1-py1| + |qx2-px1| + |qy2-py1| + |qx3-px1| + |qy3-py1| + ... + |qxn-px1|+ |qyn-py1|

=>

(|qx1-px1| + |qx2-px1| + |qx3-px1| + ... + |qxn-px1|)  +  (|qy1-py1| + |qy2-py1| + |qy3-py1| + ... + |qyn-py1|)

=>

Summation_distance_on_the_x_axis + Summation_distance_on_the_y_axis

Thus, this becomes similar to solving two one dimensional problems, rather than one two-dimensional problem.

2nd. The second observation is knowing how to solve the problem for one dimension. Now this turns out, it's a well known problem and the answer is that all the points between the left and right median have the same summation distance from all points. I dont know how to prove this yet. But emperically this seems true.

Hence, after we get all the points on the x and y axis(Lets put them in an x-list and y-list) that satisfy this condition in their individual axes, we multiply the number of points, because every combination of two points from the x-list and y-list will give a 2D point that have minimum summation distance from all points.

Hey, so I recently started solving the problem of max distance in an array.

The problem statement is this:

Given an array A of integers, find the maximum of j - i subjected to the constraint of A[i] <= A[j].

My approach to this is the following:

Consider the index pairs: (1,n-1),(2,n-1),(3,n-1)......(n-1,n-1)
                    (1,n-2),(2,n-2),(3,n-2)...(n-2,n-2)
                    and so on...
While looping through these pairs keep storing the max distance and skip the rows where a result greater than max distance is not possible. So, if index pair (1,n-1) generates a result, then all rows below that are not capable of generating a solution greater than that.

Here is the code. A is the given array as a vector<int>.

    int si=0;
    int ei=A.size()-1;
    int res=-1;
    while(ei>=0){
        int temp=si;
        while(((ei-temp)>res)&&(ei>=temp)){
            if(A[ei]>=A[temp]){
                res=ei-temp;
            }
            temp++;
        }
        ei--;
    }
    cout<<res<<endll;

I am solving this problem on interview bit[link] and it is showing a runtime error. Can somebody point out the flaw in this approach/code. I am not able to figure it out.

Thanks.

-----EDIT----- It turned out that I was supposed to solve it in O(nlogn). I think Interviewbit shows Runtime error, even for TLE. I am not sure if this is actually the case, but it has been suggested by many users.

I then solved the problem in O(n) time as suggested by the geeksforgeeks post.

vector<int> v;
cout<<v.size()-1;

The following will give you 18446744073709551615. This is because vector.size() returns a size_t type value, which is an alias for unsigned long int. In plain terms:

unsigned long int a=0;
cout<<a-1;

The above code will give the same result — 18446744073709551615.

Implications

for(int i=0;i<vector.size()-1;i++){
    ...
}

In the above for loop, if the vector has 0 elements, then the loop will be equivalent to:

for(int i=0;i<18446744073709551615;i++){
    ...
}

Which, I believe is not what you will be expecting. So the correct way to use for loops is the following:

for(int i=0;(i+1)<vector.size();i++){
    ...
}

---Edit---

As pointed out by Errichto and satyaki3794, we can just typecast vector.size() to an int, and use it normally. Like this:

for(int i=0;i<(int)vector.size()-1;i++){
    ...
}