# O(1) space, but used more time, why?

• If you imagine P[i][j] as: the max length of common subarray end with A[i] and B[j], then you will get a matrix for P[][].
And I found that, if you walk through this matrix across the diagonal line each time, you will be able to use only 1 var to store P[i-1][j-1] each time. So you don't need an array !
But after I changed my code in the way above, the runtime is longer than before. I can't figure out the reason, since I still walk through each P[i][j] once to get the answer.

My code is shown below:

``````class Solution(object):
def findLength(self, A, B):
"""
:type A: List[int]
:type B: List[int]
:rtype: int
"""
# O(1) space
# O(m*n) time
lA, lB = len(A), len(B)
maxP = 0

# traverse the upper diagonal
for j in range(lB):
P = 0
i = 0
while i < lA and j < lB:
if A[i] == B[j]:
P = P + 1
else:
P = 0
maxP = max(P, maxP)
i += 1
j += 1

# traverse the lower diagonal
for i in range(lA):
P = 0
j = 0
while i < lA and j < lB:
if A[i] == B[j]:
P = P + 1
else:
P = 0
maxP = max(P, maxP)
i += 1
j += 1

return maxP``````

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