algoadvance

Leetcode 718. Maximum Length of Repeated Subarray

Problem Statement

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

Clarifying Questions

  1. What is the range of values for the elements in the arrays?
    • The elements of the arrays can be any integers.
  2. What is the length range for nums1 and nums2?
    • The lengths of nums1 and nums2 will be in the range [1, 1000].
  3. How should the solution handle cases where no common subarray exists?
    • If no common subarray exists, the function should return 0.

Strategy

We will use dynamic programming to solve this problem efficiently.

  1. Define a DP Array:
    • Let dp[i][j] represent the length of the longest common subarray that ends at index i-1 in nums1 and index j-1 in nums2.
  2. Initialize the DP Array:
    • Initialize a 2D array dp of size (len(nums1)+1) x (len(nums2)+1) with all elements set to 0.
  3. Fill the DP Array:
    • Traverse both arrays using two nested loops.
    • If nums1[i-1] == nums2[j-1], then dp[i][j] = dp[i-1][j-1] + 1.
    • If they are not equal, dp[i][j] remains 0.
  4. Track the Maximum Length:
    • Keep a variable max_len to track the maximum value in the dp array during the traversal.
  5. Return the Result
    • The value of max_len will be the length of the longest common subarray.

Code

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int findLength(vector<int>& nums1, vector<int>& nums2) {
        int n1 = nums1.size();
        int n2 = nums2.size();
        vector<vector<int>> dp(n1 + 1, vector<int>(n2 + 1, 0));
        int max_len = 0;

        for (int i = 1; i <= n1; ++i) {
            for (int j = 1; j <= n2; ++j) {
                if (nums1[i - 1] == nums2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    max_len = max(max_len, dp[i][j]);
                }
                // No need to set dp[i][j] to 0 if elements don't match because
                // it's already initialized to 0.
            }
        }

        return max_len;
    }
};

Time Complexity

With this solution, we effectively find the length of the longest common subarray between the two given arrays.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI