Maximum Length of Repeated Subarray | leetcode 718 | Live coding session

[@algorithmo134]

I thought my battery was low but it was from your video :)

[@CodeWithSunchitDudeja]

hahaha

[@gmmkeshav]

you are the best

[@CodeWithSunchitDudeja]

So are you guys +1

[@jessanraj9086]

Great explanation

[@CodeWithSunchitDudeja]

Glad it was helpful!

[@krateskim4169]

awesome

Great and amazing short solution.

[@theinvestorengineer]

great video! really need to wrap my head around on these DP tables

[@jessanraj9086]

Hi sunchit bro ,I'm curious regarding what would the time complexity be if we don't use the 2d - dynamic programming approach

[@praveenj3112]

Thank you so much for great explanation.

[@tathagatnegi5923]

Thanks

[@paolavela8233]

You briefly touched on returning the values of the subarray- Could you please explain that further ?

[@CodeWithSunchitDudeja]

find the location of maximum entry in the matrix, and traverse in the upwards diagonal direction to build your result. Refer to the diagram you will understand.

[@NS-te8jx]

this solution exceeds time limit for the following case
import numpy as np
class Solution(object):
def findLength(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: int
"""
max_sub = 0

# create a dynamix programming matrix of size mxn
d = np.zeros((len(nums1)+1, len(nums2)+1), dtype=np.int32)

for i, c1 in enumerate(nums1):
i+=1
for j, c2 in enumerate(nums2):
j+=1
# because we added an extra space to the front of both nums
if c1==c2:
d[i][j] = d[i-1][j-1]+1
if d[i][j] > max_sub:
max_sub = d[i][j]
return max_sub
input = [0,0,0,1,0,1,1,0,1,1,0,0,0,0,1,0,0,0,1,1,1,0,0,0,1,0,1,1,0,0,0,0,1,1,1,1,1,0,0,1,0,1,1,1,0,1,1,1,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,0,1,1,1,1,0,0,0,0,0,1,0,1,1,0,0,1,1,0,1,1,0,0,1,1,0,1,0,0,0,1,1,1,0,1,0,1,0,1,0,1,1,0,0,1,0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,0,1,0,0,0,0,1,1,1,0,1,0,0,0,1,1,0,1,0,0,0,0,1,1,1,0,0,0,0,0,1,1,1,1,1,0,1,1,1,0,1,1,1,0,0,0,1,0,1,0,0,1,0,0,1,1,0,0,0,0,0,0,1,1,1,0,1,0,1,0,0,1,0,0,0,0,0,0,0,1,1,0,0,1,1,0,0,1,1,1,0,1,0,0,1,1,1,1,0,1,0,0,1,0,1,1,1,0,0,1,1,1,0,1,1,1,1,1,0,0,0,0,0,1,1,0,1,0,0,1,1,0,0,1,0,0,0,1,1,0,0,1,1,1,0,1,0,0,0,1,0,1,1,1,0,1,0,0,1,1,1,1,1,0,1,0,0,1,0,0,0,1,1,1,0,0,1,1,1,1,1,1,1,1,0,0,1,1,0,1,0,0,0,0,0,0,0,0,1,1,1,1,1,0,1,1,0,1,1,0,1,0,1,0,1,1,0,0,0,1,1,1,1,1,0,0,0,1,1,1,0,1,0,0,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,1,0,0,0,1,0,0,1,1,1,1,0,1,1,1,1,0,0,0,1,1,0,0,0,1,1,1,1,0,1,1,1,1,0,0,0,1,1,1,1,1,1,1,1,1,0,0,1,1,1,0,1,1,0,1,0,1,1,0,1,1,0,0,0,0,0,1,0,1,1,0,1,0,1,1,0,1,1,1,1,0,1,1,1,1,1,1,1,1,1,0,0,1,1,0,0,1,0,1,1,0,1,0,1,1,0,1,1,1,1,1,1,0,1,0,0,0,1,0,1,1,0,0,1,0,0,1,1,0,0,0,1,1,1,0,0,1,0,1,1,1,0,1,1,0,0,1,1,0,1,1,0,0,1,0,0,1,1,0,1,0,0,1,0,0,0,0,0,0,0,0,1,1,1,1,0,1,0,0,0,1,1,1,1,1,1,1,0,0,0,1,1,0,0,0,0,1,1,0,0,0,1,1,0,0,0,0,1,0,0,1,0,1,0,1,0,0,0,0,1,0,0,0,1,1,1,1,0,0,1,1,0,1,1,0,1,0,0,1,1,0,0,1,1,0,0,1,0,1,0,0,0,1,0,1,0,0,0,0,1,0,0,1,0,0,1,1,0,0,0,1,1,1,0,0,0,1,1,1,0,1,0,0,0,1,1,0,0,0,1,0,0,1,1,0,0,0,0,0,0,0,0,1,1,1,0,0,1,0,1,1,1,0,1,0,0,1,1,0,0,0,1,0,1,1,0,0,0,1,0,1,1,0,1,1,1,0,0,0,0,1,1,1,1,0,0,1,1,1,1,1,1,0,0,1,1,0,0,0,1,0,0,1,1,1,0,1,0,0,1,1,0,0,0,0,0,0,0,1,1,0,0,0,1,1,1,1,0,0,0,0,0,1,0,1,0,0,1,0,0,0,0,1,1,1,0,0,1,1,0,1,0,1,1,1,1,1,1,0,0,1,1,0,0,1,0,1,1,1,0,1,1,0,0,1,1,1,0,0,0,0,0,1,0,1,1,1,1,0,1,1,0,0,0,0,0,0,0,1,1,0,0,1,1,0,1,1,1,1,1,0,0,1,0,0,0,0,1,1,0,0,0,1,0,1,1,0,1,1,0,0,0,0,0,1,0,0,0,1,1,0,1,1,0,0,1,1,1,0,0,0,1,1,0,1,0,1,0,0,1,1,1,0,1,1,0,1,1,0,1,0,0,1,1,0,0,0,1,0,0,0,0,1,1,0,1,0,0,1,0,1,0,1,0,1,1,0,0,0,0,1,1,0,1,0,0,1,1,1,1,1,0,0,1,0,1,0,0,1,1,0,0,0,0,0,1,0,0,0,1,0,1,1,1,1,1,0,0,1,1,1,1,1,0,0,0,0,0,0,0,0,0,1,0,1,0]
[0,1,0,1,0,1,0,1,1,1,0,1,0,1,1,0,0,0,0,0,0,0,0,0,1,1,1,0,0,0,0,1,1,0,1,0,1,1,0,0,0,0,1,0,0,0,1,0,1,1,0,1,0,1,0,0,1,1,0,0,0,0,1,0,0,1,0,1,0,0,1,0,0,0,1,0,0,1,0,1,0,1,1,0,1,1,0,1,0,1,0,0,0,1,1,0,0,0,1,1,1,0,0,1,1,1,0,1,1,0,0,1,1,0,0,1,0,0,0,1,0,1,0,0,0,0,0,1,0,0,0,0,1,1,0,1,1,0,0,0,1,1,1,0,1,1,0,1,0,1,0,1,0,0,1,1,1,1,1,1,1,0,0,1,1,0,1,0,0,1,1,1,1,0,1,1,1,0,0,1,1,0,1,0,0,0,0,1,1,0,0,1,0,1,1,1,1,1,0,0,1,1,0,0,1,0,1,1,0,0,0,0,0,1,1,1,0,0,1,1,0,0,0,0,0,0,0,0,0,1,0,0,1,0,1,0,0,0,1,0,1,1,1,0,1,1,0,1,1,0,1,0,0,0,0,0,1,1,0,0,0,0,1,0,0,0,1,0,1,1,1,1,0,0,1,1,1,0,1,0,1,0,1,0,0,0,0,0,0,1,1,1,1,1,1,0,1,1,1,0,0,0,1,1,1,0,0,0,0,1,1,1,1,0,1,1,1,1,0,0,0,0,1,0,1,1,1,1,0,1,0,0,1,1,1,1,1,0,0,0,0,0,1,1,1,1,0,0,1,0,1,0,0,0,0,1,0,1,1,0,0,0,0,0,0,1,0,1,0,1,0,1,0,0,0,0,0,1,0,0,0,0,0,0,1,1,1,1,0,1,0,1,0,0,0,0,1,0,0,0,1,0,1,0,1,1,1,1,1,0,1,0,0,1,1,1,1,0,0,0,0,0,0,0,0,0,1,1,0,1,1,0,1,1,0,1,0,0,0,0,0,0,1,1,0,1,1,1,1,0,0,0,1,0,1,1,1,1,0,1,0,1,0,0,1,1,1,0,1,1,1,1,1,1,1,0,0,1,1,1,1,0,0,1,1,0,0,0,1,0,1,0,0,1,0,1,1,0,1,0,0,1,1,1,0,1,0,0,0,1,0,0,1,1,1,0,1,1,1,1,0,1,0,1,0,0,1,1,0,1,0,0,1,0,1,0,1,0,1,1,0,0,1,1,1,1,0,1,0,1,1,0,1,0,0,1,1,0,1,0,1,0,1,0,1,0,1,0,0,1,0,0,0,1,0,0,1,1,0,0,0,0,0,0,0,0,1,1,1,0,0,1,0,1,1,1,0,1,0,0,1,1,0,0,0,1,0,1,1,0,0,0,1,0,1,1,0,1,1,1,0,0,0,0,1,1,1,1,0,0,1,1,1,1,1,1,0,0,1,1,0,0,0,1,0,0,1,1,1,0,1,0,0,1,1,0,0,0,0,0,0,0,1,1,0,0,0,1,1,1,1,0,0,0,0,0,1,0,1,0,0,1,0,0,0,0,1,1,1,0,0,1,1,0,1,0,1,1,1,1,1,1,0,0,1,1,0,0,1,0,1,1,1,0,1,1,0,0,1,1,1,0,0,0,0,0,1,0,1,1,1,1,0,1,1,0,0,0,0,0,0,0,1,1,0,0,1,1,0,1,1,1,1,1,0,0,1,0,0,0,0,1,1,0,0,0,1,0,1,1,0,1,1,0,0,0,0,0,1,0,0,0,1,1,0,1,1,0,0,1,1,1,0,0,0,1,1,0,1,0,1,0,0,1,1,1,0,1,1,0,1,1,0,1,0,0,1,1,0,0,1,0,0,0,0,1,1,1,1,1,0,1,1,0,1,0,1,0,1,0,1,0,1,1,0,0,0,1,1,0,0,0,1,1,1,1,0,1,1,0,0,0,1,0,1,0,0,0,1,1,0,1,1,1,1,1,0,1,0,1,0,1,1,0,0,1,0,1,0,1,1,0,1,0,0,1,0,0,0,0,1,1,0,0,0,0,1,1,0,0,0,1,0,0,0,1,0,0,1,1,0,0,0,0,1,1,1,1,0,0,1,1,1,1,1,0,1,0,0,0,1,0,0,1,0,0,1,1,1,1,1,0,1,0,1,0,0,0,0,1,0,1,0,0,0,0,0,1,0,0,0,1,0,1,0,1,1,1,1,0,0,0,0,0,0,1,1,0,0,1,1,0,1,1,1,0,1,0,0,1]
output = TimeLimit exceeded

[@SumitKumar-hd5vg]

Thanks sir

[@syedhabeebuddin101]

Thanks a lot dude !
btw...what's your good name ?

[@GurgaonKiEngineer]

Bhaia , Why do we take the dp size length+1

[@shauryakapoor2122]

1:50 --> Listen again