Skip to content

Latest commit

 

History

History
96 lines (87 loc) · 6.2 KB

maximum_length_of_repeated_subarray.md

File metadata and controls

96 lines (87 loc) · 6.2 KB

🔥 Dart 🔥 || 3 solutions || line by line explanation

Solution - 1 DP Method O(n) space - working

class Solution {
// Runtime: 546 ms, faster than 100.00% of Dart online submissions for Maximum Length of Repeated SubArray.
// Memory Usage: 143.5 MB, less than 100.00% of Dart online submissions for Maximum Length of Repeated SubArray.

  int findLength(List<int> nums1, List<int> nums2) {
    // checking if the list is empty of zero
    if (nums1.isEmpty || nums2.isEmpty || nums1 == 0 || nums2 == 0) return 0;
    // length of the first list
    int row = nums1.length;
    // length of the second list
    int column = nums2.length;
    // growable list
    List<int> dp = List.filled(column + 1, 0);
    // max length that will hold our answer based om both list
    int maxLength = 0;
    // loop to iterate all the value inside first list to get each and every element
    for (var i = 1; i <= row; i++) {
      // loop to iterate the all the values in second list
      for (int j = column; j > 0; j--) {
        // if the both means each single element same as the other list
        if (nums1[i - 1] == nums2[j - 1]) {
          dp[j] = 1 + dp[j - 1];
          // than our max length will be based on the larger two numbers
          maxLength = max(maxLength, dp[j]);
        } else {
          // if not than dp is zero the element of the second list
          dp[j] = 0;
        }
      }
    }
    return maxLength;
  }
}

Solution - 2 Iterative

class C {
// 52 / 57 test cases passed.
// Status: Time Limit Exceeded
// Submitted: 0 minutes ago
// Last executed input:
// [91,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,92,35,35,35]
// [35,35,93,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,3

  int findLength(List<int> nums1, List<int> nums2) {
    int m = nums1.length, n = nums2.length, ans = 0;
    for (int i = 0; i < m; i++) {
      for (int j = 0; j < n; j++) {
        int len = 0;
        while (i + len < m && j + len < n && nums1[i + len] == nums2[j + len])
          len++; // get length of longest common sub-array starting at A[i] & B[j]
        ans = max(ans, len); // update ans to hold max length found till now
      }
    }
    return ans;
  }
}

Solution - 3 O(n^2) Time, O(1) Space solution

class E {
// 25 / 57 test cases passed.
// Status: Time Limit Exceeded
// Submitted: 0 minutes ago
// Last executed input:
// [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
// [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
  int findLength(List<int> nums1, List<int> nums2) {
    int n1 = nums1.length, n2 = nums2.length;
    int res = 0;
    for (int offset = -n1; offset < n2; offset++) {
      int count = 0;
      for (int i = max(offset, 0); i - offset < n1 && i < n2; i++) {
        if (nums1[i - offset] == nums2[i]) {
          count++;
          res = max(res, count);
        } else {
          count = 0;
        }
      }
    }
    return res;
  }
}

Some Solutions are not working ending up with Time exceed error But in Terminal It's work. Different approaches to show how to achieve one result by different way of thinking