# Rolling Array

## 2-D array, rolling in an array

1. The array has 2 states, cur and pre
2. If dp\[i] needs the updates from cur and pre, rolling from head; if dp\[i] needs the both updates from pre, rolling form tail

### 62 Unique Path

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).How many possible unique paths are there?

```java
// Tran: dp[i][j] = dp[i-1][j] + dp[i][j-1]
// Init: dp[i][0] = dp[0][j] = 0
// Ans: dp[m-1][n-1]
public int uniquePaths(int m, int n) {
    int[][] dp = new int[n][m];
    for(int i=0; i<n; i++) dp[i][0] = 1;
    for(int j=0; j<m; j++) dp[0][j] = 1;

    for(int i=1; i<n; i++){
        for(int j=1; j<m; j++){
            dp[i][j] = dp[i-1][j] + dp[i][j-1];
        }
    }
    return dp[n-1][m-1];
}
```

* Improve 1: `dp[i][j]` only relates to `dp[i-1][j]`, `dp[i][j-1]`. We only needs to maintain 2 rows and switch the row every row iteration. Space O(2n)
* Improve 2: `dp[i][j]` can be update by just `dp[i-1][j]` and current `dp[i][j]`. Space O(n)

```java
public int uniquePaths(int m, int n) {
    int[] dp = new int[m];
    dp[0][0] = 1;

    for(int i=1; i<n; i++){
        for(int j=1; j<m; j++){
            dp[i][j] += dp[i-1][j];
        }
    }
    return [m-1];
}
```

### 64 Minimum Path Sum

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

1. Init first column and first column
2. f\[i]\[j] = min{f\[i-1]\[j], f\[i]\[j-1]} + A\[i]\[j]

```java
 public int minPathSum(int[][] grid) {
    int m = grid.length;
    int n = grid[0].length;
    int[][] a = new int[m][n];
    a[0][0] = grid[0][0];

    // init row
    for (int i=1; i<m; i++){
        a[i][0] = a[i-1][0] + grid[i][0];
    }

    // init col
    for (int j=1; j<n; j++){
        a[0][j] = a[0][j-1] + grid[0][j];
    }

    for (int i=1; i<m; i++){
        for (int j=1; j<n; j++){
            a[i][j] = Math.min(a[i-1][j], a[i][j-1]) + grid[i][j];
        }
    }
    return a[m-1][n-1];
}
```

* Rolling array

```java
public int minPathSum(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    int[] dp = new int[n];

    for(int j=0; j<n; j++) dp[j] = j == 0 ? grid[0][j] : dp[j-1] + grid[0][j];

    for(int i=1; i<m; i++){
        for(int j=0; j<n; j++){
            if(j==0) dp[j] = grid[i][j] + dp[j];
            else dp[j] = grid[i][j] + Math.min(dp[j], dp[j-1]);
        }
    }
    return dp[n-1];
}
```

### 72. Edit Distance

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

Insert a character Delete a character Replace a character

* State: f\[i]\[j]表示s1前i個字符經過幾次編輯可以變成s2前j個字符
* Func: f\[i]\[j] = f\[i-1]\[j-1], s1\[i-1]=s2\[j-1] 不用編輯

  f\[i]\[j] = 1+ min{f\[i-1]\[j-1],f\[i-1]\[j],f\[i]\[j-1]}

```python
def minDistance(self, word1: str, word2: str) -> int:
    m, n = len(word1), len(word2)
    dp = [[0]*(n+1) for _ in range(m+1)]
    for i in range(m+1): dp[i][0] = i
    for j in range(n+1): dp[0][j] = j
        
    for i in range(1, m+1):
        for j in range(1, n+1):
            if word1[i-1] == word2[j-1]:
                dp[i][j] = dp[i-1][j-1]
            else:
                               # add          delete       replace
                dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
                
    return dp[m][n]
```

* Rolling Array
* Use pre to record dp\[i-1]\[j-1]

```java
public int minDistance(String word1, String word2) {
    int m = word1.length();
    int n = word2.length();
    int pre = 0;

    int[] dp = new int[n+1];

    for(int j=0; j<=n; j++){
        dp[j] = j;
    }

    for(int i=1; i<=m; i++){
        for(int j=0; j<=n; j++){
            int tmp = dp[j];
            if(j==0) dp[j] = i;
            else if(word1.charAt(i-1) == word2.charAt(j-1)) dp[j] = pre;
            else dp[j] = 1 + Math.min(pre, Math.min(dp[j], dp[j-1]));
            pre = tmp;
        }
    }

    return dp[n];
}
```

### 221. Maximal Square

Given a 2D binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.

* State: dp\[i]\[j]是包含matrix\[i-1]\[j-1]的最小邊長&#x20;
* Func: if(matrix\[i-1]\[j-1]==1) dp\[i]\[j]=min(dp\[i-1]\[j],dp\[i]\[j-1],dp\[i-1]\[j-1])+1
* Ans: dp\[m+1]\[n+1]

![](/files/-LrHBS_QcPKbSNaVv9fu)

1 Time O(m*n), Space O(m*n)

```java
public int maximalSquare(char[][] matrix) {
    if(matrix.length == 0 || matrix[0].length == 0) return 0;
    int m = matrix.length;
    int n = matrix[0].length;
    int len = 0;

    int[][] dp = new int[m+1][n+1];

    for(int i=1; i<=m; i++){
        for(int j=1; j<=n; j++){
            if(matrix[i-1][j-1] == '1'){
                dp[i][j] = Math.min(dp[i-1][j-1], Math.min(dp[i-1][j], dp[i][j-1]))+1;
                len = Math.max(len, dp[i][j]);
            }
        }
    }
    return len*len;
}
```

2 Time O(m\*n), Space O(n)

* A value pre the record the dp\[i-1]\[j-1] value
* Update dp\[j] if not '1'

```java
public int maximalSquare(char[][] matrix) {
    if(matrix.length == 0 || matrix[0].length == 0) return 0;
    int m = matrix.length;
    int n = matrix[0].length;
    int len = 0;
    int pre = 0;

    int[] dp = new int[n+1];

    for(int i=1; i<=m; i++){
        for(int j=1; j<=n; j++){
            int tmp = dp[j];
            if(matrix[i-1][j-1] == '1'){
                dp[j] = Math.min(pre, Math.min(dp[j], dp[j-1]))+1;
                len = Math.max(len, dp[j]);
            }else{
                dp[j] = 0;
            }
            pre = tmp;
        }
    }
    return len*len;
}
```

\=> Compare [Maximal Rectangle](/code-interview-note/stack/increasing-stack.md)

## 304. Range Sum Query 2D - Immutable

Given a 2D matrix matrix, find the sum of the elements inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).

![](/files/-M46U27sYKq38D_0HyLD)

The above rectangle (with the red border) is defined by (row1, col1) = **(2, 1)** and (row2, col2) = **(4, 3)**, which contains sum = **8**

```python
class NumMatrix:
    """
    regionAB = regionOB - regionOA - regionOB + regionOA
    
    Pre-calculate region
    dp: i個row j個col組成的方形面積
    dp[i][j] = dp[i-1][j]+dp[i][j-1]+matrix[i][j]-dp[i-1][j-1]
    """
    def __init__(self, matrix: List[List[int]]):
        if not matrix or not matrix[0]: return 
        m, n = len(matrix), len(matrix[0])
        self.dp = [[0] * (n+1) for _ in range(m+1)]

        for i in range(1, m+1):
            for j in range(1, n+1):
                self.dp[i][j] = matrix[i-1][j-1] + self.dp[i-1][j] + self.dp[i][j-1] - self.dp[i-1][j-1]

    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        # 注意左上角的點是包含col and row的，左上角是dp[row][col]
        return self.dp[row2+1][col2+1] - self.dp[row1][col2+1] - self.dp[row2+1][col1] + self.dp[row1][col1]
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://netjimmy.gitbook.io/code-interview-note/dynamic/rolling-array.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.