0
$\begingroup$

There are two questions that I am trying to draw a comparison between:

Q1: Maximum Absolute Difference
You are given an array of N integers, A1, A2 ,…, AN. Return maximum value of f(i, j) for all 1 ≤ i, j ≤ N.
f(i, j) is defined as |A[i] - A[j]| + |i - j|, where |x| denotes absolute value of x.

Q2: Min Steps in Infinite Grid 
You are in an infinite 2D grid where you can move in any of the 8 directions : 
    (x,y) to 
    (x+1, y), 
    (x - 1, y), 
    (x, y+1), 
    (x, y-1), 
    (x-1, y-1), 
    (x+1,y+1), 
    (x-1,y+1), 
    (x+1,y-1) 

I was reading up about the Q2 and I came across this stackoverflow question. Here, the accepted answer reduces this question to given a list of points in 2D space (x[i], y[i]), find two farthest points (with respect to Manhattan distance)

Reading up, I think both these questions are exactly the same except that Q1 is asking for Manhattan Distance in 1D and Q2 is asking for Manhattan Distance in 2D.

I am not very clear about this. Can someone please verify my observation?

$\endgroup$
1
$\begingroup$

It is nice that you try to draw a comparison between two similar situations. However, it looks like you are driving too fast to stay on the right road. Henceforth I will be moving somewhat slowly so as to stay on the correct path.

What is generally considered as a distance? You might react, hi, I know what is a distance! Cool then. Here is the widely-agreed general definition of a distance according to Wikipedia as well as my years of practice in math and computer science.

In mathematics, in particular geometry, a distance function on a given set $M$ is a function $d: M \times M \to R$, where $R$ denotes the set of real numbers, that satisfies the following conditions:

  • $d(x,y) ≥ 0$, and $d(x,y) = 0$ if and only if $x = y$. (Distance is positive between two different points, and is zero precisely from a point to itself.)
  • It is symmetric: $d(x,y) = d(y,x)$. (The distance between $x$ and $y$ is the same in either direction.)
  • It satisfies the triangle inequality: $d(x,z) ≤ d(x,y) + d(y,z)$. (The distance between two points is the shortest distance along any path). Such a distance function is known as a metric. Together with the set, it makes up a metric space.

Now let us write out explicitly our distance functions and metric spaces.

  1. In Q1, $f$ defines a distance function on all integers from 1 to $N$ such that $f(i,j) = |A[i] - A[j]| + |i - j|$. All integers from 1 to $N$, together with $f$ forms a metric space, say, $M1$.
  2. Let $\Bbb Z^2$ be all the grid points in 2D. Let $d2$ be the minimal steps needed for you to move from point (x,y) to point (p,q), where each step must be one of the eight kind of steps listed. Then $\Bbb Z^2$, together with $d2$ forms a metric space, say, $M2$. Note that $d2((0,0),(0,1))=1$, $d2((0,0),(1,0))=1\,$ and $d2((0,0),(1,1))=1$.
  3. Denote the Manhattan distance by $ma$, i.e., $ma((x,y),(p,q))=|x-p| + |y-q|$. $\Bbb Z^2$, together with $ma$ forms a metric space, say, $MA$. Note that $ma((0,0),(0,1))=1$, $ma((0,0),(1,0))=1\,$ and $ma((0,0),(1,1))=2$.

Now please follow my observations below.

  • $M1$ can be considered as a part of $MA$. Why? Define $e$: $i\mapsto (A(i),i)$. Then you can see that $d1(i,j)=ma(e(i), e(j))$, i.e., the distance between $i$ and $j$ in $M1$ is the same as the distance between $e(i)$ and $e(j)$ in $M2$. You can imagine that $e$ just embeds all integers $1, 2, \cdots, N$ in $M1$ to $MA$, keeping their pairwise distances. This is the simple reason why the accepted answer to Q1 can reduce it to given a list of points in 2D space (x[i], y[i]), find two farthest points (with respect to Manhattan distance).
  • $M1$ may or may not be considered as part of $M2$. It depends on how sequence $A$ is defined.
    1. Let $A_k$ be 0 for all $k$. Then $M1$ is just those 1D integers with their usual Euclidean distance among them. It can be embedded easily into the $M2$, keep their pairwise distances.
    2. Let $A_1=0$, $A_2=1$, $A_3=0$, $A_4=1$. Then you will find the four integers 1,2,3,4 in $M1$ has pairwise distance 2 except that $d1(1,4)=4$. However, you cannot find that kind of 4 points in $M2$. This particular example shows that your intuition "both these questions are exactly the same" is suspicious.
  • The distance in $M2$ is not a Manhattan Distance. You can have 8 points each of which is 1 distance away from any given points in $M2$. For example, $(1,0), (1,1), (0,1), (-1, 1), (-1,0), (-1,-1), (0, -1), (1, -1)$ are 1 distance away from $(0,0)$ in $M2$. However, there is only 4 points each of which is 1 distance away from any given point in $MA$. For example, $(1,0), (0,1), (-1,0), (0, -1)$ are 1 distance away from $(0,0)$ in $MA$. You can also check that $(0,0), (0,1), (1,1)$ is the vertices of an equilateral triangle in $M2$ with side length 1. However, you will not be able to find such an triangle in the Manhattan space $MA$.

Hopefully I have cleared all your doubts. Here are a few exercises for you to arrive at a better understanding of the concepts.

Exercise 0. Verify that $d1$, $d2$ and $ma$ are distance functions according to the definition.

Exercise 1. Suppose $A_1, A_2, \cdots, A_n$ is an increasing sequence of integers. Show that $M1$ can be considered a part of $M2$. Show that $M1$ can also be considered as a part of $MA$.

Exercise 2. Find 4 points in $M2$ whose pairwise distance are the same. Show that there is no 4 points in $MA$ whose pairwise distances are the same.

Exercise 3. Given an $m$ by $n$ grid in $M2$ with its bottom left corner $A$ at $(0,0)$ and its upper right corner $B$ at $(m, n)$. $0\le m \le 20$. $0\le n \le 20$. Compute the number of paths starting at $A$ and ending at $B$, where you must always move closer to $B$ along the path.

$\endgroup$
  • $\begingroup$ Thanks for that detailed explanation. I am trying to grasp it in parts and am stuck at: ma((0,0),(1,1))=1 , ma((0,0),(1,1))=1 and ma((0,0),(1,1))=2. Why is it that for the same pair of points, the distance is sometimes 1 and sometimes 2? $\endgroup$ – user248884 Oct 20 '18 at 12:49
  • $\begingroup$ Thanks for pointing out my typos. I must have been interrupted while copying and pasting my examples during my long writing. I just corrected those typos. Please take another look at my examples for $d2$ and $ma$. $\endgroup$ – Apass.Jack Oct 20 '18 at 13:39
  • $\begingroup$ Thank you! Yes, the edits have helped me understand that point. But now, I am stuck at: the distance between i and j in M1 is the same as the distance between e(i) and e(j) in M2. Why can we state this? I understand this has to do with the mapping you defined, but it doesn't follow linearly from that. What am I missing? Assuming it is the pairwise distance, how are we connecting this to the question (given a list of points in 2D space (x[i], y[i]), find two farthest points (with respect to Manhattan distance)) $\endgroup$ – user248884 Oct 20 '18 at 16:07
  • 1
    $\begingroup$ The distance between $i$ and $j$ in M1, $f(i,j)$ is $|A(i)-A(j)| + |i-j|$ by definition. The distance between $e(i)=(A(i),i)$ and $e(j)=(A(j),j)$ in M2, $ma(e(i), e(j)$ is $|A(i)-A(j)| + |i-j|$ by definition. So those two distances are the dame. Image $i$ in M1 is $e(i)$ in M1 (and $j$ in M1 is $e(j)$ in M2), you can see the maximal distance among the former is the maximal distance among the later. $\endgroup$ – Apass.Jack Oct 23 '18 at 1:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.