Search Space: Interview Problem Survey

classic binary search is used to solve many problems like leetcode 35. Where we would like to find the position we insert a given value into an already sorted list.

Example instance;

[1,3,5,6], 5

Example solution;

2

Example code;

function searchInsert(vector<int> list, int to_insert) {
  int pivot, left = 0; right = list.length()-1;
  while(left <= right) {
    pivot = (left+right) >> 2;
    if(list[pivot] == to_insert) {
      return pivot;
    }
    if(to_insert > list[pivot]) {
      left = pivot + 1;
    } else {
      right = pivot - 1;
    }
  }
}

Similar to depth-first search or breadth-first search. This algorithm can be used as a sub-routine when search in a space if the space is already structured.

Lets look at leetcode 778 Where we are given a slowly filling pool and must swim from one end of the pool to the next. Where we use binary search to guess our constraint; time. Then perform traditional depth-first search to reach the end.

Example instance;

[[0,2],[1,3]]

Example solution;

3

Example code;

class Solution {
private:
  bool possible(int time, vector<vector<int>> grid, int i, int j) 
  {
    int RN = grid.size();
    int CN = grid.at(0).size();

    if(i == RN-1 && j == CN-1) return true;

    if(i + 1 < RN && grid.at(i+1).at(j) < time) {
      return possible(time, grid, i+1, j);
    }
    if(i - 1 >= 0 && grid.at(i-1).at(j) < time) {
      return possible(time, grid, i-1, j);
    }
    if(j + 1 < CN && grid.at(i).at(j+1) < time) {
      return possible(time, grid, i, j+1);
    }
    if(j - 1 >= 0 && grid.at(i).at(j-1) < time) {
      return possible(time, grid, i, j-1);
    }
    return false;
  }
public:
  int swimInWater(vector<vector<int>> grid) {
    int L = 1, H = grid.size() * grid.at(0).size();
    while(start < max_time) {
      int M = (L+H) >> 1;
      if(!possible(M, grid, 0, 0)) {
        L = M+1;
      } else {
        H = M-1;
      }
    }
  }
}

This problem can also be solved with Dijkstra's algorithm and Union-Find. The intuition behind Dijkstra's being to first identify Optimal Sub-structure

Example Dijkstra's;

struct V {
  int v, x, y
  V(int v_, int x_, int y_) : v(v_), x(x_), y(y_) {}
  bool operator< (const V &c) const { return this.v > c.v; } 
}

class Solution {
private:
  priority_queue<V> pq;
  int M;
  int N;  
public:
  int swimInWater(vector<vector<int>> grid) {
    M = grid.size();
    N = grid.at(0).size();

    pq.push(V(grid[0][0], 0,0));
    vector<vector<bool>> seen(M, vector<int>(N));
    int res = 0;
    seen[0][0] = true;

    while(!pq.empty()) {
      V p = pq.top(); 
      pq.pop();
      res = max(res, p.v);
      if(p.x == M - 1 && p.y == N - 1) {
        return res;
      }
      if(p.x + 1 < M && !seen[p.x+1][p.y]) {
        seen[p.x+1][p.y] = true;
        pq.push(V(grid[p.x+1][p.y], p.x, p.y);
      }
      if(p.x - 1 < M && !seen[p.x-1][p.y]) {
        seen[p.x-1][p.y] = true;
        pq.push(V(grid[p.x-1][p.y], p.x, p.y);
      }
      if(p.y + 1 < M && !seen[p.x][p.y+1]) {
        seen[p.x][p.y+1] = true;
        pq.push(V(grid[p.x][p.y+1], p.x, p.y);
      }
      if(p.y - 1 < M && !seen[p.x][p.y-1]) {
        seen[p.x][p.y-1] = true;
        pq.push(V(grid[p.x][p.y-1], p.x, p.y);
      }
    }
  }
}

This differences between this question and network delay where we already used Dijsktra's is that we only care about reaching the end node, so instead of keep track of the largest ingress to the node we check if we have seen the node before.

Another method being union-find, which more directly answers the question is the groups which connect the start to end node.