718. Maximum Length of Repeated Subarray

MediumArrayBinary SearchDynamic ProgrammingSliding WindowHash FunctionRolling Hash

Problem Description

The problem is to find the maximum length of a subarray that appears in both given integer arrays nums1 and nums2. A subarray is a contiguous part of an array. The challenge is to identify the longest sequence of elements that nums1 and nums2 have in common, wherever that sequence may appear within the arrays.

Thus, the key point in this challenge is to compare elements at different positions across both arrays and keep track of the length of the current matching subarrays, equipping ourselves to identify the maximum length out of these subarrays.

Intuition

Our approach leverages a classic technique in computer science known as dynamic programming. Specifically, we use a 2D array (let's call it f) where f[i][j] represents the length of the longest common subarray ending with nums1[i-1] and nums2[j-1].

Here's the intuition broken down into steps:

Construct a 2D list f with dimensions (m+1) x (n+1), where m and n are the lengths of nums1 and nums2, respectively. Initialize all elements to 0.
Loop through each element in nums1 (index i) and nums2 (index j).
If we find a match (nums1[i - 1] == nums2[j - 1]), this extends a common subarray. Therefore, we set f[i][j] to be f[i - 1][j - 1] + 1, effectively saying, "the longest common subarray ending here is one longer than the longest at the previous indices.
Track the maximum length found during this process with a variable ans.
After exploring all elements from both arrays, ans holds the length of the longest matching subarray found.

Learn more about Binary Search, Dynamic Programming and Sliding Window patterns.

Solution Approach

The solution implements a dynamic programming approach to solve the problem efficiently by avoiding the recomputation of overlapping subproblems. Let's walk through the logical steps and explain how the solution is implemented:

Initialization: Create a 2D list f of size (m+1) x (n+1) filled with zeros, where m and n are the lengths of nums1 and nums2, respectively. Here, each element f[i][j] is meant to hold the length of the longest common subarray that ends with elements nums1[i-1] and nums2[j-1].
Nested Loops for Comparison: Utilize two nested loops to iterate over both arrays. The outer loop runs through nums1 using index i, while the inner loop runs through nums2 using index j. Both indices start from 1 since the 0-th row and column of f will be used as a base for the dynamic programming algorithm and should remain zeroes.
Matching Elements: Inside the inner loop, check if the elements nums1[i-1] and nums2[j-1] match. This is important because we are looking for a common subarray, so we are only interested in matching elements.
Updating f: If a match is found, update f[i][j] to f[i-1][j-1] + 1. This step carries over the length from the previous matching subarray and adds one for the current match. It is the core of the dynamic programming approach as it builds upon previously computed values.
Tracking the Maximum Length: Keep updating a variable ans with the maximum value in the 2D list f as we go, by comparing ans with f[i][j] at each step.

Following this logic, the final value held in ans after the loops complete execution will be the length of the longest common subarray between nums1 and nums2. This is because ans is updated each time we extend the length of a subarray, and it only keeps the maximum length encountered.

The dynamic programming pattern here exploits the "optimal substructure" property of the problem (the longest subarray ending at an index can be found from longest subarrays ending at previous indices) and avoids redundant calculations, providing an optimally efficient solution.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's illustrate the solution approach with small example arrays nums1 and nums2.

Suppose nums1 = [1, 2, 8, 3] and nums2 = [5, 1, 8, 3, 9].

Initialization: We create a 2D list f with dimensions (4+1) x (5+1) (as nums1 has length 4 and nums2 has length 5), so f will be a 5x6 grid of zeros. This grid will store the lengths of the longest common subarrays found to our point.
Nested Loops for Comparison: Begin with nested loops; with i iterating from 1 to 4 (for nums1) and j iterating from 1 to 5 (for nums2).
Matching Elements & Updating f:
- When i=1 and j=2, we find that nums1[0] == nums2[1] (which is 1). So, we update f[1][2] to f[0][1] + 1. Since f[0][1] is 0, f[1][2] becomes 1.
- As loops continue, no more matches are found until i=3 and j=3, where nums1[2] == nums2[2] (which is 8); f[3][3] is updated to f[2][2] + 1 and f[3][3] becomes 1.
- Finally, at i=4 and j=4, nums1[3] == nums2[3] (which is 3). Since we had a match at the previous indices (nums1[2] == nums2[2] was 8), f[i][j] becomes f[3][3] + 1. f[3][3] was 1, so now f[4][4] is 2. This is the longest subarray we've encountered.
Tracking the Maximum Length: ans is updated each time f[i][j] is bigger than the current ans. It starts at 0 and becomes 1 after the first match, and then 2 after the last match.

The loops conclude with ans holding the value 2, which is the maximum length of a subarray that appears in both nums1 and nums2 (the subarray being [8, 3]).

This walk-through has demonstrated how the dynamic programming approach efficiently solves the problem by using previously computed values to build up a solution, avoiding unnecessary recomputation.

Solution Implementation

1from typing import List
2
3class Solution:
4    def findLength(self, nums1: List[int], nums2: List[int]) -> int:
5        # Get the lengths of the input arrays.
6        length_nums1, length_nums2 = len(nums1), len(nums2)
7      
8        # Initialize the DP table with all values set to 0.
9        # The table dimensions will be (length_nums1 + 1) x (length_nums2 + 1).
10        dp_table = [[0] * (length_nums2 + 1) for _ in range(length_nums1 + 1)]
11      
12        # Variable to hold the length of the longest common subarray.
13        max_length = 0
14      
15        # Loop through each element in nums1.
16        for i in range(1, length_nums1 + 1):
17            # Loop through each element in nums2.
18            for j in range(1, length_nums2 + 1):
19                # Check if the elements at the current indices are the same.
20                if nums1[i - 1] == nums2[j - 1]:
21                    # If they are, update the DP table by adding 1 to the value
22                    # from the previous indices in both nums1 and nums2.
23                    dp_table[i][j] = dp_table[i - 1][j - 1] + 1
24                    # Update the max_length if a longer common subarray is found.
25                    max_length = max(max_length, dp_table[i][j])
26      
27        # Return the length of the longest common subarray.
28        return max_length
29

1// Class name Solution indicates that this is a solution to a problem.
2class Solution {
3  
4    // Method findLength returns the length of the longest common subarray between two arrays.
5    public int findLength(int[] nums1, int[] nums2) {
6        // m and n store the lengths of the two input arrays nums1 and nums2 respectively.
7        int m = nums1.length;
8        int n = nums2.length;
9      
10        // Create a 2D array 'dp' to store the lengths of common subarrays.
11        int[][] dp = new int[m + 1][n + 1];
12      
13        // Variable 'maxLen' keeps track of the maximum length of common subarrays found so far.
14        int maxLen = 0;
15      
16        // Iterate over the elements of nums1 and nums2.
17        for (int i = 1; i <= m; ++i) {
18            for (int j = 1; j <= n; ++j) {
19                // Check if elements from both arrays match.
20                if (nums1[i - 1] == nums2[j - 1]) {
21                  
22                    // If they match, increment the value from the previous diagonal element by 1.
23                    dp[i][j] = dp[i - 1][j - 1] + 1;
24                  
25                    // Update 'maxLen' if the current length of the common subarray is greater.
26                    maxLen = Math.max(maxLen, dp[i][j]);
27                }
28                // If elements do not match, the length of common subarray is 0 (by default in Java).
29            }
30        }
31      
32        // Return the maximum length of common subarray found.
33        return maxLen;
34    }
35}
36

1#include <vector>
2#include <algorithm> // Include library for std::max
3
4using std::vector;
5using std::max;
6
7class Solution {
8public:
9    int findLength(vector<int>& nums1, vector<int>& nums2) {
10        // Size of the input vectors
11        int sizeNums1 = nums1.size();
12        int sizeNums2 = nums2.size();
13
14        // Create a 2D vector to store the length of longest common subarray ending at i-1 and j-1
15        vector<vector<int>> dp(sizeNums1 + 1, vector<int>(sizeNums2 + 1));
16
17        // Initialize answer to keep track of the max length of common subarray found so far
18        int maxLength = 0;
19
20        // Iterate over nums1 and nums2 vectors
21        for (int i = 1; i <= sizeNums1; ++i) {
22            for (int j = 1; j <= sizeNums2; ++j) {
23                // If elements match, extend the length of the common subarray
24                if (nums1[i - 1] == nums2[j - 1]) {
25                    dp[i][j] = dp[i - 1][j - 1] + 1;
26
27                    // Update maxLength with the largest length found
28                    maxLength = max(maxLength, dp[i][j]);
29                }
30                // No need to handle the else case explicitly, as the dp array is initialized to 0s
31            }
32        }
33
34        // Return the maximum length of common subarray found
35        return maxLength;
36    }
37};
38

1function findLength(nums1: number[], nums2: number[]): number {
2    // Get the lengths of both input arrays.
3    const lengthNums1 = nums1.length;
4    const lengthNums2 = nums2.length;
5  
6    // Initialize a 2D array 'dp' (dynamic programming table) with zeros.
7    // The table will store lengths of common subarrays.
8    const dp: number[][] = Array.from({ length: lengthNums1 + 1 }, () => new Array(lengthNums2 + 1).fill(0));
9  
10    // Variable to keep track of the maximum length of common subarray found so far.
11    let maxLength = 0;
12  
13    // Iterate over both arrays to fill the dynamic programming table.
14    for (let i = 1; i <= lengthNums1; ++i) {
15        for (let j = 1; j <= lengthNums2; ++j) {
16            // When elements at the current position in both arrays match,
17            // increment the value by 1 from the diagonally previous.
18            if (nums1[i - 1] === nums2[j - 1]) {
19                dp[i][j] = dp[i - 1][j - 1] + 1;
20                // Update maxLength if a longer common subarray is found.
21                maxLength = Math.max(maxLength, dp[i][j]);
22            }
23        }
24    }
25  
26    // Return the maximum length of the common subarray.
27    return maxLength;
28}
29

Time and Space Complexity

The given code implements a dynamic programming approach to find the length of the longest common subsequence between two arrays nums1 and nums2.

Time Complexity

The time complexity of the code is O(m * n), where m is the length of nums1 and n is the length of nums2. This is because the code uses two nested loops, each iterating up to the length of the respective arrays. For each pair of indices (i, j) the code performs a constant amount of work.

Space Complexity

The space complexity of the code is also O(m * n) because it creates a 2D list f of size (m + 1) * (n + 1) to store the lengths of common subsequences for each index pair (i, j). This 2D list is required to remember the results for all subproblems, which is a typical requirement of dynamic programming approaches.

In summary:

Time Complexity: O(m * n)
Space Complexity: O(m * n)

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8

1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12

1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

[30, 20, 10]

[100, 33, 30]

[10, 12, 20]

I don't know