Today I have done leetcode's September LeetCoding Challenge with cpp.

September LeetCoding Challenge 16

Description

Path With Minimum Effort

You are a hiker preparing for an upcoming hike. You are given heights, a 2D array of size rows x columns, where heights[row][col] represents the height of cell (row, col). You are situated in the top-left cell, (0, 0), and you hope to travel to the bottom-right cell, (rows-1, columns-1) (i.e., 0-indexed). You can move up, down, left, or right, and you wish to find a route that requires the minimum effort.

A route's effort is the maximum absolute difference in heights between two consecutive cells of the route.

Return the minimum effort required to travel from the top-left cell to the bottom-right cell.

Example 1:

Input: heights = [[1,2,2],[3,8,2],[5,3,5]]
Output: 2
Explanation: The route of [1,3,5,3,5] has a maximum absolute difference of 2 in consecutive cells.
This is better than the route of [1,2,2,2,5], where the maximum absolute difference is 3.

Example 2:

Input: heights = [[1,2,3],[3,8,4],[5,3,5]]
Output: 1
Explanation: The route of [1,2,3,4,5] has a maximum absolute difference of 1 in consecutive cells, which is better than route [1,3,5,3,5].

Example 3:

Input: heights = [[1,2,1,1,1],[1,2,1,2,1],[1,2,1,2,1],[1,2,1,2,1],[1,1,1,2,1]]
Output: 0
Explanation: This route does not require any effort.

Constraints:

rows == heights.length
columns == heights[i].length
1 <= rows, columns <= 100
1 <= heights[i][j] <= 10⁶

Solution

auto speedup = []() {
  cin.tie(nullptr);
  cout.tie(nullptr);
  ios::sync_with_stdio(false);
  return 0;
}();

using pi = pair<int, int>;
bool vis[100][100];
class Solution {
  int rows;
  int cols;
  int moves[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
  bool verify(vector<vector<int>>& heights, int effort) {
    memset(vis, 0, sizeof(vis));
    queue<pi> q;
    q.push({0, 0});
    vis[0][0] = true;
    while(q.size()) {
      auto [row, col] = q.front();
      q.pop();
      if(row == rows - 1 && col == cols - 1) return true;
      for(int i = 0; i < 4; ++i) {
        int newRow = row + moves[i][0];
        int newCol = col + moves[i][1];
        if(newRow < 0 || newCol < 0 || newRow >= rows || newCol >= cols) continue;
        if(vis[newRow][newCol]) continue;
        if(abs(heights[newRow][newCol] - heights[row][col]) > effort) continue;
        vis[newRow][newCol] = true;
        q.push({newRow, newCol});
      }
    }
    return false;
  }
public:
  int minimumEffortPath(vector<vector<int>>& heights) {
    rows = heights.size();
    cols = heights.front().size();
    int mmin = INT_MAX;
    int mmax = INT_MIN;
    for(auto &row :heights) {
      mmin = min(mmin, *min_element(row.begin(), row.end()));
      mmax = max(mmax, *max_element(row.begin(), row.end()));
    }
    int low = 0;
    int high = mmax - mmin;
    while(low < high) {
      int mid = (low + high) >> 1;
      if(!verify(heights, mid)) {
        low = mid + 1;
      } else {
        high = mid;
      }
    }
    return low;
  }
};

// Accepted
// 75/75 cases passed (294 ms)
// Your runtime beats 56.19 % of cpp submissions
// Your memory usage beats 43.06 % of cpp submissions (39.2 MB)

2023-09-16 Daily Challenge

September LeetCoding Challenge 16

Description

Solution