[LeetCode] – Update Matrix Solution

    by nikoo28

    In this problem, we are given a matrix consisting of 0s and 1s. The goal is to update matrix and compute the distance of each cell containing 1 to the nearest 0. The distance between two adjacent cells is considered to be 1.

    The key challenge in this problem is efficiently determining the minimum distance for each cell while avoiding unnecessary computations.

    Input:
    mat = [[0,0,0],
    [0,1,0],
    [1,1,1]]

    Output:
    [[0, 0, 0],
    [0, 1, 0],
    [1, 2, 1]]

    Explanation:
    Each cell containing 1 is replaced by its shortest distance to the nearest 0.

    A straightforward approach is to traverse the entire matrix for each cell containing 1, performing a breadth-first search (BFS) or depth-first search (DFS) to find the nearest 0. However, this results in high time complexity.

    Steps:

    1. Iterate over all the cells in the matrix.
    2. For each cell with value 0, add it to a queue.
    3. Until the queue is empty, pop a 0, and use BFS to find the distance to each 1
    4. Store the minimum distance found.
    5. Repeat this process for all 0s in the queue
    image showing iteration in each direction to update matrix
    Fig: Apply BFS for every visited node and mark steps

    Complexity Analysis:

    Since each BFS/DFS runs independently for each 1 in the matrix, the worst-case time complexity is O(m * n * (m + n)), which is highly inefficient for large matrices.

    This brute force method is impractical for large inputs, so we need a more optimized approach.

    To efficiently compute the minimum distance, we can use Dynamic Programming (DP) with Two Passes. The idea is to use a bottom-up and top-down scan to propagate distances efficiently.

    Steps:

    1. Initialize a result matrix with maximum values (except for 0s, which remain 0).
    2. First pass (Top-left to Bottom-right):
      • If the current cell is 1, update it by considering the minimum value from the top and left neighbors plus 1.
    3. Second pass (Bottom-right to Top-left):
      • If the current cell is 1, update it by considering the minimum value from the bottom and right neighbors plus 1.
    4. Return the updated result matrix.
    update matrix with top and left values
    update matrix with minimum of bottom, right and prev values
    Fig: 2 steps to update the matrix
      int[][] updateMatrix(int[][] mat) {
        int rows = mat.length;
        int cols = mat[0].length;
        int[][] result = new int[rows][cols];
    
        // Initialize the result matrix with maximum values
        for (int i = 0; i < rows; i++)
          for (int j = 0; j < cols; j++)
            result[i][j] = Integer.MAX_VALUE;
    
        // First pass: top-left to bottom-right
        for (int i = 0; i < rows; i++)
          for (int j = 0; j < cols; j++)
            if (mat[i][j] == 0) result[i][j] = 0;
            else {
              if (i > 0)
                result[i][j] = Math.min(result[i][j], result[i - 1][j] + 1);
              if (j > 0)
                result[i][j] = Math.min(result[i][j], result[i][j - 1] + 1);
            }
    
        // Second pass: bottom-right to top-left
        for (int i = rows - 1; i >= 0; i--)
          for (int j = cols - 1; j >= 0; j--)
            if (mat[i][j] != 0) {
              if (i < rows - 1)
                result[i][j] = Math.min(result[i][j], result[i + 1][j] + 1);
              if (j < cols - 1)
                result[i][j] = Math.min(result[i][j], result[i][j + 1] + 1);
            }
    
        return result;
      }Code language: Java (java)

    Complexity Analysis:

    • Time Complexity: O(m × n), since each cell is updated at most twice.
    • Space Complexity: O(1) if modifying the input matrix in-place; otherwise, O(m × n) for an auxiliary matrix.
    YouTube player
    0 comments
    0 FacebookTwitterLinkedinWhatsappEmail
  • ArraysStrings

    [Leetcode] – Word Break Solution

    by nikoo28
    4 minutes read

    In the given problem statement, we have a string s and a dictionary wordDict containing a list of words. We need to determine if s can be segmented into a space-separated sequence of dictionary words. The tricky part of this problem is ensuring that every segment of the string matches words from the dictionary. A brute-force approach could generate all possible segmentations, but that would be highly inefficient. Input: s = “studyalgorithms”wordDict = [“study”, “algorithms”]Output: trueExplanation: Since “studyalgorithms” can be split into “study” and “algorithms”, both of which are in …

    0 FacebookTwitterLinkedinWhatsappEmail
  • Arrays

    [Leetcode] – Insert Interval Solution

    by nikoo28
    4 minutes read

    In this problem, we are given a list of non-overlapping intervals sorted by their start times, along with a new interval. The goal is to insert the new interval into the list while ensuring the intervals remain non-overlapping and sorted. If necessary, overlapping intervals should be merged. The tricky part of this problem lies in handling overlapping intervals efficiently while maintaining the sorted order. We also need to consider edge cases, such as when the new interval does not overlap with any existing intervals or when it encompasses multiple intervals. …

    0 FacebookTwitterLinkedinWhatsappEmail
  • System DesignTheory

    Message Queue in System Design

    by nikoo28
    3 minutes read

    Continuing with our System Design series we’ll be discussing message queue, an essential component in building scalable, decoupled systems. Message queues help systems handle communication between different parts asynchronously, ensuring smooth data flow even during heavy traffic. What is a Message Queue? A message queue is a system that allows different parts of a system to communicate with each other in an asynchronous manner. It acts as a buffer between a producer (the part that sends messages) and a consumer (the part that processes messages), allowing the producer to continue …

    0 FacebookTwitterLinkedinWhatsappEmail
  • System DesignTheory

    Proxy in System Design

    by nikoo28
    5 minutes read

    Let’s continue the journey in System Design. In this post, we’ll explore the concept of forward and reverse proxy, which play a crucial role in optimizing and securing web traffic. Proxies act as intermediaries, improving efficiency, security, and management of requests between clients and servers. What is a Proxy? A proxy is essentially an intermediary that sits between a client and a server, forwarding requests and responses between the two. It can be used for various purposes such as load balancing, security, caching, and more. Real-World Example: Imagine a bookstore …

    0 FacebookTwitterLinkedinWhatsappEmail
  • System DesignTheory

    Indexing in System Design

    by nikoo28
    3 minutes read

    Let us continue our System Design series! In this post, we’ll dive into the concept of indexing in databases. Indexing is a technique that allows for faster data retrieval by organizing and optimizing the way data is stored. What is Indexing? Indexing is like creating a shortcut for finding the right data quickly. Instead of scanning the entire database, the index helps you jump directly to the location of the data you need, improving the performance of your queries. Real-World Example: Let’s go back to our bookstore analogy. Imagine you …

    0 FacebookTwitterLinkedinWhatsappEmail

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More