Coding interview Essentials

39. Max in manhattan neighborhood\(^{K}\)

Max in manhattan neighborhood\(^{K}\)

Introduction

This chapter discusses a very interesting problem based on the concept of the Manhattan distance [^35]; an alternative way to measure distances that is particularly useful in real life. Imagine you need to measure the distance between two points on a map. You can use the Euclidean distance and come up with a number that in reality is not going to be super helpful unless you can fly. This is because that number is not going to tell you the actual distance you need to cover if you want to get to your destination by moving on land. For example, what is the distance between the Empire State building and Times Square in New York? If you are not naturally equipped with wings then what you actually do is to jump in a car or a cab or a bike and follow the grid pattern of streets of Manhattan. This means that you would probably have to cover around 15 blocks north and 3 south (See Figure 43.1). The idea of measuring the distance by counting the number of steps we take in the north-south or west-east directions underlies what is known as the taxicab distance. In this framework, the distance is not represented as a straight line going from point A to point B (like it would for the Euclidean distance) but it is a zig-zagged sequence of vertical and horizontal segments, representing movements along the north-south and east-west axis. Therefore, the formula for measuring the taxicab distance is all about measuring the length of the horizontal and vertical segments. The formula for measuring the Manhattan distance in Equation [eq:max_manhattan:distance_formula] . \[d = |x_1-x_2|+|y_1-y_2| \label{eq:max_manhattan:distance_formula}\]

The problem in this chapter will challenge you to find, for each cell of a given matrix, the largest value in any cell sitting at a Manahtann distance below a certain threshold.

Figure 1: Taxicab distance from times square to the Trump’s tower. Notice that the black straight-line is depicting the Euclidean distance, and that the latter is shorter than the actual taxicab distance between the two points.

Problem statement

[example:max_manhattan:exercice1] Write a function that given

a matrix \(I\) of \(n\) rows and \(m\) columns and

an integer \(K > 0\)

returns a new matrix \(M\) of size \(n \times m\) where \(M[i][j]\) contains the maximum value among the elements in the Manhattan neighborhood of size \(K\) for the cell \((i,j)\). The Manhattan neighborhood of size \(K\) for a cell \((i,j)\) is composed of all cell \((p,q)\) such that: \[N(i,j, K) = \{(p,q) | |i-p|+|j-q| \leq K\} \label{eq:max_manhattan:neighbood_equation}\]

[example:max_manhattan:example1]
Given: \(I= \begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{bmatrix}\) and \(K=1\) the function return \(I= \begin{bmatrix} 4 & 5 & 6 \\ 7 & 8 & 9 \\ 8 & 9 & 9 \end{bmatrix}\)

[example:max_manhattan:example2]
Given: \(I= \begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{bmatrix}\) and \(K=2\) the function return \(I= \begin{bmatrix} 7 & 8 & 9 \\ 8 & 9 & 9 \\ 9 & 9 & 9 \end{bmatrix}\)

Clarification Questions

Discussion

Brute-force

This problem can be tackled by using a brute-force approach that blindly calculates the answer for each cell as per the problem statement. All that is needed to find the answer for the cell \((i,j)\) is to calculate the maximum among the cells that are at a Manhattan distance of at most \(K\) from it (the cells that are part of the Manhattan neighborhood of size \(K\)). Therefore, the problem boils down to figuring out the neighborhood for a given cell. Figure 43.2 shows an example of such a neighborhood where the numbers inside the cells represent the distance from the cell \((i,j)\) at the center.

Figure 2: Cells in the Manhattan neighborhood of size 3. The numbers in each cell represent the Manhattan distance from the central cell.

Given a cell \((i,j)\), figuring out exactly which cells are part of the neighborhood and which are not is not particularly difficult. Instead of coming up with a way of generating such a list of cells, it is easier to loop over all the cells within a square of size \(2K\) having cell \((i,j)\) at its center, and to ignore the ones that do not satisfy Equation [eq:max_manhattan:neighbood_equation]. Because both

the number of cells in the neighborhood and

the number of cell in such square

is quadratic in \(K\), then, asymptotically speaking, the additional work required by visiting cells that are inside the area of cells we are looping on but not part of the neighborhood does not really make any difference. Listing [list:max_manhattan:bruteforce] shows an implementation of this idea. This approach is clearly correct and has a time complexity of \(O(nmK^2)\) as for each of the \(nm\) cells of the matrix we do exactly \(K^2\) work. The space complexity is \(O(1)\) as no additional space is used other than the second matrix we must return.

Listing 1: Brute Force solution to the problem of finding the max cell within the manhattan neighborhood of size $K$.

//! This function returns the max value among the cells of I that are part of
//! the
// manhattan neighborhood of size K for cell at (i,j)
/*!
  \param I the input matrix
  \param cell the coordinate of the cell for which the max value is to be
  calculated \param K the size of the manhattan neighborhood \return the max
  value for (i,j) among all cells (p,q) satisfying: |i-p|+|j-q| <= K
*/
using Matrix = std::vector<std::vector<int>>;
using Cell   = std::pair<int, int>;

auto find_max_in_manhattan_neigh_k(const Matrix& I,
                                   const Cell& cell,
                                   const int K)
{
  const int rows    = I.size();
  const int cols    = I.back().size();
  const auto [i, j] = cell;
  assert(i >= 0 && i < rows && j >= 0 && j < cols);

  int ans = I[i][j];
  for (int p = std::max(0, i - K); p <= std::min(rows - 1, i + K); p++)
  {
    for (int q = std::max(0, j - K); q <= std::min(cols - 1, j + K); q++)
    {
      if (std::abs(i - p) + std::abs(j - q) <= K)
      {
        ans = std::max(ans, I[p][q]);
      }
    }
  }
  return ans;
}

Matrix max_manhattan_matrix_k_bruteforce(const Matrix& I, const unsigned K)
{
  const int rows = I.size();
  const int cols = I.back().size();

  Matrix M(I);
  for (int i = 0; i < rows; i++)
  {
    for (int j = 0; j < cols; j++)
    {
      M[i][j] = find_max_in_manhattan_neigh_k(I, Cell(i, j), K);
    }
  }
  return M;
}

Dynamic Programming

As previously stated, the brute-force solution works by blindly finding the solution for each cell without taking into consideration whether we can use the information already calculated for other cells. Consider the matrix shown in Figure 43.3 showing the neighborhood of size \(1\) for the cells

\((x,y)\) (center)

\((x+1,y)\) (right)

\((x-1,y)\) (left)

\((x,y-1)\) (top)

\((x,y+1)\) (down)

and Figure 43.4 showing the neighborhood of size \(2\) for the cell \((x,y)\). Note that the latter is composed by the union of the neighborhoods of size \(1\) shown in Figure 43.3. Therefore, if we know the answer for \(K=1\) for the cells

\((x,y)\)

\((x+1,y)\)

\((x-1,y)\)

\((x,y-1)\)

\((x,y+1)\)

we can easily calculate the answer for \(K=2\) for the cell \((x,y)\) without having to look at all the \(12\) cells composing its Manhattan neighborhood of size \(2\).

Figure 3: Manhattan neighborhoods of size 1 for the cells: (x,y) (center), (x+1,y) (right), (x-1,y) (left), (x,y-1) (top) and (x,y+1) (down).
Figure 4: Neighborhood of size 2 for the cell (x,y) obtained by the union of the neighborhood depicted in Figure43.3.

[]

We can apply the same line of reasoning to find the answer for \(K=3\). Figure 43.5 shows the neighborhoods of size \(2\) for the cells

\((x,y)\)

\((x+1,y)\)

\((x-1,y)\)

\((x,y-1)\)

\((x,y+1)\)

and and Figure 43.6 shows the neighborhood of size \(3\) for the cell \((x,y)\). Also in this case the latter can be obtained by the union of all the cells in Figure 43.5 and therefore, if we have the answer for all the sub-problems where \(K=2\) we can obtain the answer for the sub-problems where \(K=3\) without having to scan the entirety of the neighborhood of size \(3\) for \((x,y)\). We only have to find the maximum among \(5\) elements instead of having to look into \(25\) cells. This idea can be generalized and its formalization is shown in Equation [eq:max_manhattan:dpformula]. The formula is saying that we can obtain the answer for \(K=0\) by simply returning the value of the cell \((i,j)\). For \(K>0\), we only have to return the max among the neighboring north,south, west and east cells of \((i,j)\) for the same subproblem where \(K-1\).

\[\begin{cases} S(0,i,j) = I[i][j] \\ S(K,i,j) = \max \Big [ S(K-1,i,j), S(K-1,i+1,j),\;S(K-1,i-1,j),\;S(K-1,i,j+1),\;S(K-1,i,j-1) \Big ] \\ \end{cases} \label{eq:max_manhattan:dpformula}\]

Figure 5: Manhattan neighborhoods of size 1 for the cells: (x,y) (center), (x+1,y) (right), (x-1,y) (left), (x,y-1) (top) and (x,y+1) (down).
Figure 6: Neighborhood of size 3 for the cell (x,y) obtained by the union of the neighborhood depicted in Figure43.5.

[]

As with all dynamic programming problems, we have two ways to write the solution:

  1. top-down, where we use memoization to avoid making duplicate work

  2. bottom-up, where we solve subproblems in an ordered manner from the simplest to the hardest.

Top-down

The top-down approach is possibly the easiest to write as we can translate \(S(K,i,j)\) (see Equation [eq:max_manhattan:dpformula]) into a C++ recursive function, and we can use memoization (in the form of a cache of size \(K\times n\times m\)) to store intermediate values of \(S\) and avoid duplicate work. Listing [list:max_manhattan:dp_topdown] shows an implementation of this approach where such a cache is implemented via a hashmap, which maps the arguments of \(S\), all triplets \((K,i,j)\), to integers. Notice that the function and the function are the machinery that makes us use tuples of type as keys in the Cache (which has type ). uses to calculate the hash value for a given . The main driver function is named and the sole purpose is to create the memoization cache and then to call the C++ equivalent of function \(S\) (see Equation [eq:max_manhattan:dpformula]): . The latter is a recursive function that takes as input

the original input matrix \(I\) (which is never modified and is only passed along as a reference),

\(K\), the max distance at which we search for the max value in \(I\) ,

, which contains the coordinate of the cell for which we are finding an answer and finally

the memoization cache where we store the answers for a given \(K\) and .

The first thing we do is to unpack the cell into two separate variables representing the row and the column of a cell: \(i,j\). If the coordinates of the cell are outside the boundaries of \(I\) then there is no answer for such a cell and we return the smallest possible int. Moreover if \(K=0\), as per Equation [eq:max_manhattan:dpformula], the answer is the value of the cell \((i,j)\) When we have already calculated the solution to this problem (i.e. for the same values of \(K,i,j\)) then we simply return the memoized value. In all other cases we have to do the actual work and perform the recursive calls to get the answer for the subproblems for the neighboring cells at the previous value of \(K\):

.

The time and space complexity of this approach is \(O(nmK)\). The proof is quite simple and it boils down to the following facts:

  1. there are exactly \(n\times m \times K\) different unique ways we can call the recursive function.

  2. each function call is memoized. This means that redundant work is avoided, therefore we do not do the work for a recursive call that has already been fully executed.

Each entry in the memoization cache costs \(4\) integers for a total of \(O(nmK)\).

Listing 2: DP top-down solution to the problem of finding the max cell within the manhattan neighborhood of size $K$.

using Matrix = std::vector<std::vector<int>>;
using Cell   = std::pair<int, int>;

template <typename SeedType, typename T, typename... Rest>
void hash_combine(SeedType& seed, const T& v, const Rest&... rest)
{
  seed ^= std::hash<T>{}(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
  (hash_combine(seed, rest), ...);
}
struct TupleHash
    : public std::unary_function<std::tuple<int, int, int>, std::size_t>
{
  std::size_t operator()(const std::tuple<int, int, int>& k) const
  {
    size_t seed = 0;
    hash_combine(seed, std::get<0>(k), std::get<1>(k), std::get<2>(k));
    return seed;
  }
};

using Cache = std::unordered_map<std::tuple<int, int, int>, int, TupleHash>;

int max_manhattan_matrix_k_DP_topdown_helper(const Matrix& I,
                                             const unsigned K,
                                             const Cell& cell,
                                             Cache& cache)
{
  const auto [i, j] = cell;
  if (i < 0 || j < 0 || i >= I.size() || j >= I.back().size())
    return std::numeric_limits<int>::min();

  if (K == 0)
    return I[i][j];

  const auto key = std::make_tuple(K, i, j);
  if (const auto& it = cache.find(key); it != cache.end())
    return it->second;

  const auto ans = std::max(
      {I[i][j],
       max_manhattan_matrix_k_DP_topdown_helper(I, K - 1, {i - 1, j}, cache),
       max_manhattan_matrix_k_DP_topdown_helper(I, K - 1, {i + 1, j}, cache),
       max_manhattan_matrix_k_DP_topdown_helper(I, K - 1, {i, j + 1}, cache),
       max_manhattan_matrix_k_DP_topdown_helper(I, K - 1, {i, j - 1}, cache)});

  cache[key] = ans;
  return ans;
}

Matrix max_manhattan_matrix_k_DP_topdown(const Matrix& I, const unsigned K)
{
  const int rows = I.size();
  const int cols = I.back().size();
  Cache cache;

  Matrix M(I);
  for (int i = 0; i < rows; i++)
    for (int j = 0; j < cols; j++)
      M[i][j] = max_manhattan_matrix_k_DP_topdown_helper(I, K, {i, j}, cache);

  return M;
}

Bottom-up

If we pay closer attention to Equation [eq:max_manhattan:dpformula] or, equivalently to the top-down implementation in Listing [list:max_manhattan:dp_topdown] we immediately notice that in order to calculate all the values of \(S(K,i,j)\) for a given \(K\) we only need the values of \(S\) for \(K-1\). Because we know the solution to the sub-problems where \(K=0\), we can immediately solve all the problems where \(K=1\). At this point the values for the sub-problems where \(K=0\) are not needed anymore and we can throw them away and use that space to store the solution for the sub-problems where \(K=1\). Now that we have the solution for all sub-problems where \(K=1\), we can proceed and calculate the solutions for \(K=2\). We apply the same line of reasoning to the rest of the sub-problems until we reach the value of \(K\) we need.

The bottom-up approach is built on this idea and works by iteratively computing the answers for sub-problems where \(K-1\) before moving on to calculating the answer for the sub-problems for the next value of \(K\). This can be implemented by using two matrices of the same size of \(I\):

  • \(M_{K-1}\): storing the values of the sub-problems for the previous value of \(K\) we are trying to compute during this step.

  • \(M_{K}\) which is the space where we write the answers for the sub-problems we calculate during this step.

When \(M_{K}\) is full and ready, it can be copied into \(M_{K-1}\) and continue to process the next value of \(K\). In other words, \(M_{K}\) is a working space where the solutions to the sub-problems for the current \(K\) are stored, and \(M_{K-1}\) contains all the answers for the sub-problems necessary to calculate the answers at the step.

The computation of a value of \(M_{K}\) uses the same idea as the top-down approach: the value of to \(M_K[i][j]\) is the maximum among the following five values:

\(M_{K-1}[i][j]\)

\(M_{K-1}[i+1][j]\)

\(M_{K-1}[i-1][j]\)

\(M_{K-1}[i][j+1]\)

\(M_{K-1}[i][j-1]\)

Note that at any time all the space we need is the space for storing the solution for the sub-problems for two different values of \(K\). This translates into a significant reduction in space complexity compared to the top-down approach described in Section 43.3.2.1 which is \(O(nm)\) in this approach.

Listing [list:max_manhattan:dp_bottomup] shows an implementation of this idea. Note that in the actual code \(M_{K-1}\) and \(M_{K}\) are the variables and , respectively.

Listing 3: DP bottom-down solution to the problem of finding the max cell within the manhattan neighborhood of size $K$.

Matrix max_manhattan_matrix_k_DP_bottomup(const Matrix& I, const unsigned K)
{
  const auto rows = I.size();
  assert(rows > 0);
  const auto cols = I.back().size();
  assert(cols > 0);

  std::array<Matrix, 2> cache = {I, I};
  Matrix& previous            = cache[0];
  Matrix& current             = cache[1];

  for (int k = 1; k <= K; k++)
  {
    for (int i = 0; i < rows; i++)
    {
      for (int j = 0; j < cols; j++)
      {
        auto ans = previous[i][j];
        if (i - 1 >= 0)
          ans = std::max(ans, previous[i - 1][j]);
        if (i + 1 < rows)
          ans = std::max(ans, previous[i + 1][j]);
        if (j - 1 >= 0)
          ans = std::max(ans, previous[i][j - 1]);
        if (j + 1 < cols)
          ans = std::max(ans, previous[i][j + 1]);

        current[i][j] = ans;
      }
    }
    std::swap(current, previous);
  }
  return previous;
}