Maximum Length of Repeated Subarray

LeetCode 718 | Difficulty: Medium

Medium

Problem 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`

Topics: Array, Binary Search, Dynamic Programming, Sliding Window, Rolling Hash, Hash Function

---

Approach

Sliding Window

Maintain a window [left, right] over the array/string. Expand right to include new elements, and shrink left when the window violates constraints. Track the optimal answer as the window slides.

When to use

Finding subarrays/substrings with a property (max length, min length, exact count).

Binary Search

Binary search reduces the search space by half at each step. The key insight is identifying the monotonic property — what condition lets you decide to go left or right?

When to use

Sorted array, or searching for a value in a monotonic function/space.

Dynamic Programming

Break the problem into overlapping subproblems. Define a state (what information do you need?), a recurrence (how does state[i] depend on smaller states?), and a base case. Consider both top-down (memoization) and bottom-up (tabulation) approaches.

When to use

Optimal substructure + overlapping subproblems (counting ways, min/max cost, feasibility).

---

Solutions

Solution 1: C# (Best: 304 ms)

Metric	Value
Runtime	304 ms
Memory	41.8 MB
Date	2022-01-16

Solution

public class Solution {
    public int FindLength(int[] nums1, int[] nums2) {
       int m = nums1.Length;
    int n = nums2.Length;
    int max = 0;
    int[,] dp = new int[m+1, n+1];
    for (int i = 1; i <= m; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if(nums1[i-1] == nums2[j-1])
            {
                dp[i,j] = 1 + dp[i-1,j-1];
                max = Math.Max(max, dp[i,j]);
            }
        }
    }
    
    return max;
    }
}

---

Complexity Analysis

Approach	Time	Space
Binary Search	$O(log n)$	$O(1)$
Sliding Window	$O(n)$	$O(k)$
DP (2D)	$O(n × m)$	$O(n × m)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Clarify what makes a window "valid" and what triggers expansion vs shrinking.
• Define the DP state clearly. Ask: "What is the minimum information I need to make a decision at each step?"
• Consider if you can reduce space by only keeping the last row/few values.
• Precisely define what the left and right boundaries represent, and the loop invariant.
• LeetCode provides 2 hint(s) for this problem — try solving without them first.

💡 Hints

Hint 1: Use dynamic programming. dp[i][j] will be the longest common prefix of A[i:] and B[j:].

Hint 2: The answer is max(dp[i][j]) over all i, j.