Maximum Length of Repeated Subarray

MEDIUM

Description

Given two integer arrays nums1 and nums2, return the maximum length of a subarray that appears in both arrays.

Example 1:

Input: nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
Output: 3
Explanation: The repeated subarray with maximum length is [3,2,1].

Example 2:

Input: nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0]
Output: 5
Explanation: The repeated subarray with maximum length is [0,0,0,0,0].

Constraints:

1 <= nums1.length, nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 100

Approaches

Checkout 4 different approaches to solve Maximum Length of Repeated Subarray. Click on different approaches to view the approach and algorithm in detail.

Brute Force

This approach exhaustively checks every possible subarray from the first array (nums1) and sees if it exists in the second array (nums2). While simple to understand, it's highly inefficient.

Algorithm

Initialize maxLength = 0.
Iterate through nums1 with index i from 0 to nums1.length - 1.
Inside this loop, iterate through nums2 with index j from 0 to nums2.length - 1.
If nums1[i] == nums2[j], it marks a potential start of a common subarray.
Start a third loop with index k to find the length of this common subarray.
While i + k < nums1.length, j + k < nums2.length, and nums1[i + k] == nums2[j + k], increment k.
After the inner loop, k is the length of the common subarray starting at (i, j). Update maxLength = max(maxLength, k).
After all loops complete, return maxLength.

We use three nested loops. The first two loops define all possible starting points i in nums1 and j in nums2. The third loop (or a while loop) then checks for the length of the common subarray starting at these points. We iterate through all pairs of starting indices (i, j) from nums1 and nums2. For each pair, we count how many consecutive elements are identical (nums1[i+k] == nums2[j+k]). We keep track of the maximum count found across all pairs.

class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        int maxLength = 0;
        for (int i = 0; i < nums1.length; i++) {
            for (int j = 0; j < nums2.length; j++) {
                int k = 0;
                while (i + k < nums1.length && j + k < nums2.length && nums1[i + k] == nums2[j + k]) {
                    k++;
                }
                maxLength = Math.max(maxLength, k);
            }
        }
        return maxLength;
    }
}

Complexity Analysis

Time Complexity: O(N * M * min(N, M)), where N and M are the lengths of `nums1` and `nums2`. The three nested loops lead to this complexity. For each pair of starting points (i, j), we might iterate up to `min(N, M)` times.Space Complexity: O(1), as we only use a few variables to store indices and the maximum length.

Pros and Cons

Pros:

Simple to conceive and implement.
Very low memory usage.

Cons:

Extremely slow for large inputs, likely to result in a 'Time Limit Exceeded' error on most platforms.

Code Solutions

Checking out 4 solutions in different languages for Maximum Length of Repeated Subarray. Click on different languages to view the code.

class Solution {
public
  int findLength(int[] nums1, int[] nums2) {
    int m = nums1.length;
    int n = nums2.length;
    int[][] f = new int[m + 1][n + 1];
    int ans = 0;
    for (int i = 1; i <= m; ++i) {
      for (int j = 1; j <= n; ++j) {
        if (nums1[i - 1] == nums2[j - 1]) {
          f[i][j] = f[i - 1][j - 1] + 1;
          ans = Math.max(ans, f[i][j]);
        }
      }
    }
    return ans;
  }
}

Video Solution

Watch the video walkthrough for Maximum Length of Repeated Subarray

Algorithms:

Binary Search

Patterns:

Sliding WindowDynamic ProgrammingRolling HashHash Function

Data Structures:

Array

Companies:

Citadel |