Longest Increasing Subarray (2D)


  • 5
    E

    Given a 2D array such as below:

    1, 6, 7
    2, 5, 8
    3, 4. 9
    

    Find the longest increasing subarray and return that length. At every index, you can move to any of its four neighbors: right, down, left, and up, but you cannot jump or move to its diagonal neighbor.

    The longest increasing subarray of the above example is of length 9:

     1    6 -> 7
     |    ^    |
     v    |    v
     2    5    8
     |    ^    |
     v    |    v
     3 -> 4    9
    

    The solution for the following example is 10:

    13, 2,  5, 6
    12, 3,  0, 7
    11, 10, 9, 8
    

    and the path is

    2->5->6->7->8->9->10->11->12->13

  • 0
    H

    This question was pretty tough although it seems easy!!! Took me few hours to complete my code! :)


  • 0
    H

    Here is my runnable code.

    At beginning, I thought it was a simple DFS question but it turned out it was very tricky as you should need to keep track of your path and expand some certain neighboring items. So the change I applied to my stack was to just expand the first next bigger number if not yet visited.

    If there is no neighboring item satisfying these conditions, the trace of the stack is our path and we just store the maximum path that has been so far found!

    My item class for sorting the items of the matrix:

    public class Item implements Comparable<Item>{
        int row, col, val;
    
        public Item(int row, int col, int val){
            this.row = row;
            this.col = col;
            this.val = val;
        }
    
        public int compareTo(Item o){
            return (val - o.val);
        }
    }
    

    Here is the main body of my code.

    public class LongestSubArray {
    
        int[][] matrix;
        int maxRow, maxCol;
        boolean[][] visited;
        Set<Integer> included = new HashSet<>();
        LinkedList<Integer> maxPath;
        int maxPathLength = 0;
        public LongestSubArray(int[][] matrix) {
            this.matrix = matrix;
            maxRow = matrix.length - 1;
            maxCol = matrix[0].length - 1;
        }
    
        public List<Integer> findLongestSubArray() {
            List<Item> items = new ArrayList<>();
    
            for (int i = 0; i < matrix.length; i++)
                for (int j = 0; j < matrix[0].length; j++)
                    items.add(new Item(i, j, matrix[i][j]));
    
            Collections.sort(items);
    
            for (Item item : items) {
                if (!included.contains(item.val)) {
                    visited = new boolean[maxRow + 1][maxCol + 1];
                    visited[item.row][item.col] = true;
                    findLongestPath(item);
                }
            }
            return maxPath;
        }
    
        public void findLongestPath(Item item) {
    
            LinkedList<Item> stack = new LinkedList<>();
            stack.addLast(item);
            Item currentItem;
    
            while (!stack.isEmpty()) {
                currentItem = stack.getLast();
    
    
                int minRow = -1, minCol = -1, minNeighbor = Integer.MAX_VALUE;
    
                if (currentItem.row + 1 <= maxRow && !visited[currentItem.row + 1][currentItem.col] &&
                        minNeighbor > matrix[currentItem.row + 1][currentItem.col] &&
                        matrix[currentItem.row + 1][currentItem.col] > matrix[currentItem.row][currentItem.col]) {
                    minNeighbor = matrix[currentItem.row + 1][currentItem.col];
                    minRow = currentItem.row + 1;
                    minCol = currentItem.col;
                }
    
                if (currentItem.row - 1 >= 0 && !visited[currentItem.row - 1][currentItem.col] &&
                        minNeighbor > matrix[currentItem.row - 1][currentItem.col] &&
                        matrix[currentItem.row - 1][currentItem.col] > matrix[currentItem.row][currentItem.col]) {
                    minNeighbor = matrix[currentItem.row - 1][currentItem.col];
                    minRow = currentItem.row - 1;
                    minCol = currentItem.col;
                }
    
                if (currentItem.col + 1 <= maxCol && !visited[currentItem.row][currentItem.col + 1] &&
                        minNeighbor > matrix[currentItem.row][currentItem.col + 1] &&
                        matrix[currentItem.row][currentItem.col + 1] > matrix[currentItem.row][currentItem.col]) {
                    minNeighbor = matrix[currentItem.row][currentItem.col + 1];
                    minRow = currentItem.row;
                    minCol = currentItem.col + 1;
                }
    
                if (currentItem.col - 1 >= 0 && !visited[currentItem.row][currentItem.col - 1] &&
                        minNeighbor > matrix[currentItem.row][currentItem.col - 1] &&
                        matrix[currentItem.row][currentItem.col - 1] > matrix[currentItem.row][currentItem.col]) {
                    minNeighbor = matrix[currentItem.row][currentItem.col - 1];
                    minRow = currentItem.row;
                    minCol = currentItem.col - 1;
                }
    
    
                if (minNeighbor < Integer.MAX_VALUE) {
                    stack.addLast(new Item(minRow, minCol, minNeighbor));
                    visited[minRow][minCol] = true;
                } else {
                    if (maxPathLength < stack.size()) {
                        maxPath = new LinkedList<>();
                        for (Item tempItem : stack) {
                            maxPath.add(tempItem.val);
                            included.add(tempItem.val);
                        }
                        maxPathLength = maxPath.size();
                    }
                    stack.removeLast();
                }
            }
        }
    }
    

  • 1

  • 0
    P
    public class LongestIncreasingPath {
    private int[] XMOVE = {0,1,-1,0};
    private int[] YMOVE = {1,0,0,-1};
    
    public int longestIncreasingPath(int[][] matrix) {
    
        int rows = matrix.length;
        if(rows==0) {
            return 0;
        }
        int cols = matrix[0].length;
        int res = 0;
        boolean[][] visited = new boolean[rows][cols];
        int[][] count = new int[rows][cols];
    
        for (int i=0;i<rows;i++) {
            for (int j=0;j<cols;j++) {
                res = Math.max(getMaxPath(i,j,rows,cols,0,matrix,visited,count),res);
            }
        }
        return res;
    
    }
    
    private int getMaxPath(int i,int j,int rows,int cols,int maxValue,int[][] matrix,boolean[][] visited,int[][] count) {
        visited[i][j] = true;
    
        /*
        If count[i][j] !=0 it means that there is a path starting from it which has been
        already calculated so no need to do repeated computations.
         */
        if(count[i][j]!=0) {
            visited[i][j] = false;
            return maxValue+count[i][j];
        }
    
        maxValue++;
        int loopMax= 0;
        for (int k=0;k<4;k++) {
            int nextX = i+XMOVE[k];
            int nextY = j+YMOVE[k];
            if(isValid(nextX,nextY,rows,cols,visited,matrix,matrix[i][j])) {
                loopMax =  Math.max(loopMax,getMaxPath(nextX,nextY,rows,cols,0,matrix,visited,count));
            }
        }
        maxValue = maxValue + loopMax;
    
        count[i][j] = maxValue;
        visited[i][j] = false;
    
        return maxValue;
    
    }
    
    private boolean isValid(int x,int y,int rows,int cols,boolean[][] visited,int[][] matrix,int currentValue) {
        return (x>=0 && y>=0 && x<rows && y<cols && !visited[x][y] && (matrix[x][y]>currentValue));
    }}

  • 0
    D

    A working java solution:

    private static int len(int[][] m) {
            int[][] dp = new int[m.length][m[0].length];
            int max = 0;
            for (int i = 0; i < m.length; i++) {
                Arrays.fill(dp[i], -1);
            }
    
            for (int i = 0; i < m.length; i++) {
                for (int j = 0; j < m[i].length; j++)
                    max = Math.max(max, len(m, i, j, dp));
            }
            return max;
        }
    
        private static int len(int[][] m, int i, int j, int[][] dp) {
    
            if (!isValid(m, i, j)) {
                return 0;
            }
    
            if (dp[i][j] != -1) {
                return dp[i][j];
            }
    
            int max = 1;
    
            if (i > 0 && m[i][j] < m[i - 1][j]) {
                max = 1 + len(m, i - 1, j, dp);
            }
    
            if (j > 0 && m[i][j] < m[i][j - 1]) {
                max = Math.max(max, 1 + len(m, i, j - 1, dp));
            }
    
            if (i < m.length - 1 && m[i + 1][j] > m[i][j]) {
                max = Math.max(max, 1 + len(m, i + 1, j, dp));
            }
    
            if (j < m[i].length - 1 && m[i][j + 1] > m[i][j]) {
                max = Math.max(max, 1 + len(m, i, j + 1, dp));
            }
    
            dp[i][j] = max;
            return max;
        }
    
        private static boolean isValid(int[][] m, int i, int j) {
            return !(i < 0 || j < 0 || i >= m.length || j >= m[i].length);
        }
    

  • 0
    P

    Javascript, O(nlogn)
    I could solve the problem with dynamic programming.

    1. Collect all values of elements
    2. Sort collected array in descending order
    3. Start from maximum number. (The number has no path. Cause the value d[maximum]=0)
    4. For the next element, d[next-smaller] = max(d[left], d[top], d[right], d[bottom])
      The number is 2nd max number. So the above approach works.

    Working code is as following:

    const longestIncreasing = (ary2d) => {
        let sorted = []
            , d = {}
            , maxLen = Number.MIN_VALUE
            , maxf = (...args) => args.reduce((m, c) => Math.max(m, c), args[0])
            ;
        for (let j = 0; j < ary2d.length; ++j) {
            let ary = ary2d[j];
            for (let i = 0; i < ary.length; ++i) {
                sorted.push([j, i, ary[i]]);
            }
        }
    
        let pathLen = (j, i, cur) => {
            return (
            j < 0
            || j >= ary2d.length
            || i < 0
            || i >= ary2d[0].length
            || (ary2d[j][i] < cur)) ? Number.MIN_VALUE : ((d[ary2d[j][i]] || 0) + 1);
        };
    
        sorted.sort((n1, n2) => n2[2] - n1[2]);
        sorted.forEach(([j, i, v]) => {
            d[v] = maxf(
                pathLen(j - 1, i, v),
                pathLen(j, i + 1, v),
                pathLen(j + 1, i, v),
                pathLen(j, i - 1, v),
                0
            )
            ;
            maxLen = Math.max(d[v], maxLen);
        });
    
        return maxLen + 1;
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.