Longest Common Substring — Day 57(Python)

Image for post
Image for post
Photo by David Becker on Unsplash

Today’s problem is on Dynamic Programming. Let us look into the question without wasting much time.

718. Maximum Length of Repeated Subarray

Given two integer arrays A and B, return the maximum length of the subarray that appears in both arrays.

Example 1:

Note:

  1. 1 <= len(A), len(B) <= 1000
  2. 0 <= A[i], B[i] < 100

Let us analyze the question. We are given 2 input lists, and we need to find the longest repeated subarray. Isn’t it similar to Longest Common Subsequence? The only difference between both the questions is, the current question wants the longest subarray and LCS requires us to find the longest subsequence. What is the difference between subarray and subsequence?

According to GeeksForGeeks,

A subarray is a contiguous part of an array. An array that is inside another array. For example, consider the array [1, 2, 3, 4], There are 10 non-empty sub-arrays. The subarrays are (1), (2), (3), (4), (1,2), (2,3), (3,4), (1,2,3), (2,3,4) and (1,2,3,4).

A subsequence is a sequence that can be derived from another sequence by zero or more elements, without changing the order of the remaining elements.
For the same example, there are 15 sub-sequences. They are (1), (2), (3), (4), (1,2), (1,3),(1,4), (2,3), (2,4), (3,4), (1,2,3), (1,2,4), (1,3,4), (2,3,4), (1,2,3,4).

The only difference between subarray and subsequence is continuity. In the given question, we need to find the longest common subarray from the given 2 input list. Before we jump into finding the solution, let us recall the code for LCS using the Bottom-Up approach.

Similar to LCS we will be creating a 2D matrix of the size of both the input array. We will be initializing the matrix with INT MIN value.

Next, we will be filling our matrix with the calculated values.

We know when any of the arrays are empty, there cannot be anything that we can term as common. Since the 1st row represents an empty array and the 1st column represents an empty array, we will be initializing both with 0.

We will move to the main algorithm.

From LCS we know, if the element at index i-1 in array1 is equal to the elements at index j-1 in array2, then the current cell value will be 1+memo[i-1][j-1]. The same happens in this case too.

What if the elements are not equal? Since we are trying to find a subarray, in such a case, we are breaking our continuity, and hence, we will fill those cell values with 0.

In the end, we will be returning the maximum value present in our matrix.

Let us look into the complete code snippet.

Complexity analysis.

Time Complexity

We are traversing through a 2D array of size M*N, hence the time complexity is O(M*N), where M is the size of array1 and N is the size of array2.

Space Complexity.

We are creating a 2D array of size M*N, hence the space complexity is O(M*N), where M is the size of array1 and N is the size of the array2.

Link to Aditya Verma’s video

Software Engineer. Find me @ www.linkedin.com/in/annamariya-jt

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store