DEV Community

Cover image for 2290. Minimum Obstacle Removal to Reach Corner
MD ARIFUL HAQUE
MD ARIFUL HAQUE

Posted on

2290. Minimum Obstacle Removal to Reach Corner

2290. Minimum Obstacle Removal to Reach Corner

Difficulty: Hard

Topics: Array, Breadth-First Search, Graph, Heap (Priority Queue), Matrix, Shortest Path

You are given a 0-indexed 2D integer array grid of size m x n. Each cell has one of two values:

  • 0 represents an empty cell,
  • 1 represents an obstacle that may be removed.

You can move up, down, left, or right from and to an empty cell.

Return the minimum number of obstacles to remove so you can move from the upper left corner (0, 0) to the lower right corner (m - 1, n - 1).

Example 1:

example1drawio-1

  • Input: grid = [[0,1,1],[1,1,0],[1,1,0]]
  • Output: 2
  • Explanation: We can remove the obstacles at (0, 1) and (0, 2) to create a path from (0, 0) to (2, 2).
    • It can be shown that we need to remove at least 2 obstacles, so we return 2.
    • Note that there may be other ways to remove 2 obstacles to create a path.

Example 2:

example1drawio

  • Input: grid = [[0,1,0,0,0],[0,1,0,1,0],[0,0,0,1,0]]
  • Output: 0
  • Explanation: We can move from (0, 0) to (2, 4) without removing any obstacles, so we return 0.

Constraints:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 105
  • 2 <= m * n <= 105
  • grid[i][j] is either 0 or 1.
  • grid[0][0] == grid[m - 1][n - 1] == 0

Hint:

  1. Model the grid as a graph where cells are nodes and edges are between adjacent cells. Edges to cells with obstacles have a cost of 1 and all other edges have a cost of 0.
  2. Could you use 0-1 Breadth-First Search or Dijkstra’s algorithm?

Solution:

We need to model this problem using a graph where each cell in the grid is a node. The goal is to navigate from the top-left corner (0, 0) to the bottom-right corner (m-1, n-1), while minimizing the number of obstacles (1s) we need to remove.

Approach:

  1. Graph Representation:

    • Each cell in the grid is a node.
    • Movement between adjacent cells (up, down, left, right) is treated as an edge.
    • If an edge moves through a cell with a 1 (obstacle), the cost is 1 (remove the obstacle), and if it moves through a 0 (empty cell), the cost is 0.
  2. Algorithm Choice:

    • Since we need to minimize the number of obstacles removed, we can use 0-1 BFS (Breadth-First Search with a deque) or Dijkstra's algorithm with a priority queue.
    • 0-1 BFS is suitable here because each edge has a cost of either 0 or 1.
  3. 0-1 BFS:

    • We use a deque (double-ended queue) to process nodes with different costs:
      • Push cells with cost 0 to the front of the deque.
      • Push cells with cost 1 to the back of the deque.
    • The idea is to explore the grid and always expand the path that does not require obstacle removal first, and only remove obstacles when necessary.

Let's implement this solution in PHP: 2290. Minimum Obstacle Removal to Reach Corner

<?php
/**
 * @param Integer[][] $grid
 * @return Integer
 */
function minimumObstacles($grid) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test Case 1
$grid1 = [
    [0, 1, 1],
    [1, 1, 0],
    [1, 1, 0]
];
echo minimumObstacles($grid1) . PHP_EOL; // Output: 2

// Test Case 2
$grid2 = [
    [0, 1, 0, 0, 0],
    [0, 1, 0, 1, 0],
    [0, 0, 0, 1, 0]
];
echo minimumObstacles($grid2) . PHP_EOL; // Output: 0
?>
Enter fullscreen mode Exit fullscreen mode

Explanation:

  1. Input Parsing:

    • The grid is taken as a 2D array.
    • Rows and columns are calculated for bounds checking.
  2. Deque Implementation:

    • SplDoublyLinkedList is used to simulate the deque. It supports adding elements at the front (unshift) or the back (push).
  3. Visited Array:

    • Keeps track of cells already visited to avoid redundant processing.
  4. 0-1 BFS Logic:

    • Start from (0, 0) with a cost of 0.
    • For each neighboring cell:
      • If it's empty (grid[nx][ny] == 0), add it to the front of the deque with the same cost.
      • If it's an obstacle (grid[nx][ny] == 1), add it to the back of the deque with an incremented cost.
  5. Return the Result:

    • When the bottom-right corner is reached, return the cost.
    • If no valid path exists (though the problem guarantees one), return -1.

Complexity:

  • Time Complexity: O(m x n), where m is the number of rows and n is the number of columns. Each cell is processed once.
  • Space Complexity: O(m x n), for the visited array and deque.

This implementation works efficiently within the given constraints.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

Image of AssemblyAI tool

Challenge Submission: SpeechCraft - AI-Powered Speech Analysis for Better Communication

SpeechCraft is an advanced real-time speech analytics platform that transforms spoken words into actionable insights. Using cutting-edge AI technology from AssemblyAI, it provides instant transcription while analyzing multiple dimensions of speech performance.

Read full post

Top comments (0)

Heroku

Simplify your DevOps and maximize your time.

Since 2007, Heroku has been the go-to platform for developers as it monitors uptime, performance, and infrastructure concerns, allowing you to focus on writing code.

Learn More

👋 Kindness is contagious

Discover a treasure trove of wisdom within this insightful piece, highly respected in the nurturing DEV Community enviroment. Developers, whether novice or expert, are encouraged to participate and add to our shared knowledge basin.

A simple "thank you" can illuminate someone's day. Express your appreciation in the comments section!

On DEV, sharing ideas smoothens our journey and strengthens our community ties. Learn something useful? Offering a quick thanks to the author is deeply appreciated.

Okay