# [C++] DP solution with space optimized

• For the regular DP solution, we'd need a 2D array of size m*n where m is the size of array A and n is the size of array B. However, when I had code like this:

``````vector<vector<int>> dp (m+1, vector<int> (n+1, 0));
``````

I got an `Memory Limit Exceeded` error, I suppose it's because for some test cases, this caused stack to overflow. This problem can be addressed by allocating the 2D array on heap instead of stack:

``````auto dp_ptr = new vector<vector<int>>(m+1, vector<int> (n+1, 0));
auto dp = *dp_ptr;
``````

However, for this problem, we don't have to use a 2D array actually. A 1D array is good enough since we only need to find out the maximum length of the repeated subarray of A and B. Here is how: we just need to pick an array of shorter length, say n < m, so B is shorter, then allocating a 1D array:

``````vector<int> dp (n+1, 0);
``````

For any `i` where `0 < i < m`, `dp[j]` means the maximum length of repeated subarray ends at A[i] and B[j-1]. So `dp[j] = 0` if `A[i] != B[j-1]` and `dp[j] = 1 + dp[j-1]` if `A[i] == B[j-1]`, note here `dp[j-1]` means the maximum length of repeated subarray ends at A[i-1] and B[j-2], it was computed when i was i - 1.

Below is the full code:

``````class Solution3 {
private:
// A.size >= B.size
int _findLength(vector<int>& A, vector<int>& B) {
int m = A.size();
int n = B.size();
int max_len = 0;

vector<int> dp (n+1, 0);
for (int i = 0; i < m; ++i) {
for (int j = n; j >= 1; --j) {
if (B[j-1] == A[i]) dp[j] = 1 + dp[j-1];
else dp[j] = 0;
max_len = max(max_len, dp[j]);
}
}

return max_len;
}

public:
int findLength(vector<int>& A, vector<int>& B) {
int max_len;

if (B.size() <= A.size()) {
max_len =_findLength(A, B);
} else {
max_len =_findLength(B, A);
}

return max_len;
}
};
``````

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