Scale Engineer

Maximum Length of Repeated Subarray

Med
#0672Time: 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: O(1), as we only use a few variables to store indices and the maximum length.1 company
Patterns
Sliding WindowDynamic ProgrammingRolling HashHash Function
Algorithms
Binary Search
Data structures
Array
Companies
Citadel

Prompt

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

4 approaches with complexity analysis and trade-offs.

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.

Walkthrough

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

Time

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

O(1), as we only use a few variables to store indices and the maximum length.

Trade-offs

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.

Solutions

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 walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem