[Hard] 329. Longest Increasing Path in a Matrix (Java)

https://leetcode.com/problems/longest-increasing-path-in-a-matrix/description/

Longest Increasing Path in a Matrix - LeetCode

배고프다

---

※  Question Summary

▶ Given an m x n integers matrix, return the length of the longest increasing path in matrix

▶ From each cell, you can only move left,right,up,down.

▶ Input : 2D integer array (with constraints)

▶ Output : Return the length of the longest increasing path in matrix

---

◈ Constraints

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 200
• 0 <= matrix[i][j] <= 2^31 - 1

---

◈ Input - 1

[[9,9,4],[6,6,8],[2,1,1]]

◈ Output - 1

4

◈ Input - 2

[[3,4,5],[3,2,6],[2,2,1]]

◈ Output - 2

4

◈ Input - 3

[[1]]

◈ Output - 3

1

---

 ◎  HOW TO SOLVE IT

▶ make class which name 'Point' to store row,col and the length of the increasing path

▶ Utilize 1D arrays, 'dr' and 'dc', to explore the up, down, left, and right directions

▶ use BFS to search the maxtrix from each cell

 1. Check if it's outside the boundary when performing BFS.

 2. Increase the count if it's on an increasing path.

▶ use 2d array DP to skip search  if the count is already known.

     (  I add this later since i got time limit exceeded :(  )

example )

▶ Return the length of the longest increasing path in matrix

---

class Point {
    int m_nRow;
    int m_nCol;
    int m_nCount;
    
    Point() {

    }

    Point(int nRow, int nCol, int nCount) {
        this.m_nRow = nRow;
        this.m_nCol = nCol;
        this.m_nCount = nCount;
    }
}

class Solution {
    // East West North South
    static int[] dr = {0, 0, 1, -1};
    static int[] dc = {1,-1, 0, 0};
    static int[][] narrDp;
    public int longestIncreasingPath(int[][] matrix) {
        int nMax = 0;
        narrDp = new int[matrix.length][matrix[0].length];
        for(int i = 0; i < matrix.length; i++) {
            for(int j = 0; j < matrix[i].length; j++) {
                // use BFS to find longest path
                int nResult = BFS(i, j, matrix);
                if(nMax < nResult)
                    nMax = nResult;
            }
        }

        return nMax;
    }

    static public int BFS(int i, int j, int[][] matrix) {
        int nResult = 1;
        Queue<Point> pBFS = new LinkedList<>();
        pBFS.add(new Point(i, j, 1));

        while(!pBFS.isEmpty()) {
            Point pTemp = pBFS.poll();
            
            int nNow = matrix[pTemp.m_nRow][pTemp.m_nCol];
            // you don't have to search if you already know
            if(narrDp[pTemp.m_nRow][pTemp.m_nCol] < pTemp.m_nCount)
                narrDp[pTemp.m_nRow][pTemp.m_nCol] = pTemp.m_nCount;
            else
                continue;
            
            // can move up,down,left,right
            for(int k = 0; k < dr.length; k++) {
                int nRow = pTemp.m_nRow + dr[k];
                int nCol = pTemp.m_nCol + dc[k];
                
                // can't move outside the boundary
                if(nRow < 0 || nCol < 0 || nRow >= matrix.length || nCol >= matrix[0].length)
                    continue;

                // only move on increasing path
                if(nNow <= matrix[nRow][nCol])
                    continue;

                // you are increasing path when you get here
                if(nResult < pTemp.m_nCount + 1)
                    nResult = pTemp.m_nCount + 1;

                pBFS.add(new Point(nRow, nCol, pTemp.m_nCount+1));
            }
        }

        return nResult;
    }
}

---

I HOPE YOUR DAY GOES WELL :)