718. Maximum Length of Repeated Subarray

718. Maximum Length of Repeated Subarray

This question helps circumvent struggles with dynamic programming questions but after
few trials you would find it easier to draw tabulation that can help solve the question.

Initial TLE Solution

"Sets" Approach

The most ubiquitous way to find a set(subarray) is using Sets from the java "maximum length of a subarray"
libraries. How we generate sets can be a bit more recursive approach to get combinations of all subsets.

 private void findSubsets(Set<List<Integer>> subset, List<Integer> nums, ArrayList<Integer> output, int index) {
        if (index == nums.size()) {
            subset.add(output);
            return;
        }

        findSubsets(subset, nums, new ArrayList<>(output), index + 1);
         output.add(nums.get(index));
        findSubsets(subset, nums, new ArrayList<>(output), index + 1);
    }

The code above uses a recursive approach to return sets of all subarrays. Our goal is to check if these subarrays
form a continuous order in the other arrays(nums2). So our goal is to check if this subarray from(nums1) is continuous in
nums2.

  private boolean contiguous(List<Integer> num, List<Integer> n2) {
        return Collections.indexOfSubList(n2 , num)!=-1;
    }

The check for this condition is quite redundant to add the third && condition but this was to make sure we only check the
continuous order in bout nums1 and nums2.

  if(num2Set.contains(num) && contiguous(num,n2) && contiguous(num,n1)){
                ans=Math.max(ans,num.size());
            }

Final TLE Code

public int findLengthTLE(int[] nums1, int[] nums2) {
        int ans=0;
        Set<List<Integer>> num1Set= new LinkedHashSet<>();
        Set<List<Integer>> num2Set= new LinkedHashSet<>();
        List<Integer> n1=Arrays.stream(nums1).boxed().collect(Collectors.toList());
        List<Integer> n2=Arrays.stream(nums2).boxed().collect(Collectors.toList());


        findSubsets(num1Set,   Arrays.stream(nums1).boxed().collect(Collectors.toList()), new ArrayList<>(), 0);
        findSubsets(num2Set,   Arrays.stream(nums2).boxed().collect(Collectors.toList()), new ArrayList<>(), 0);

        for (List<Integer> num : num1Set) {
            if(num2Set.contains(num) && contigious(num,n2) && contigious(num,n1)){
                ans=Math.max(ans,num.size());
            }
        }
        return ans;
    }

Dynamic Approach(N*M)

A dynamic approach was to use 2d arrays and create a table of length n+1*m+1 which is the length of nums1 and nums2 respectively.
The update to this 2d array come from the condition only when a number at specific i is equal equals to a number at j.

if(nums1[i]==nums2[j]) {
                    dp[i+1][j+1] =1 + dp[i][j];
                    mx = Math.max(mx, dp[i+1][j+1]);
                }

Well if the numbers at i and j are equal we update the table corresponding to that index row, col value.
This implies we indicate that row col by 1 increment.

[[0, 0, 0, 0, 0, 0], [0, 0, 0, 1, 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, 1, 0, 0], [0, 0, 1, 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, 1, 0, 0], [0, 0, 1, 0, 0, 0], [0, 1, 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, 1, 0, 0], [0, 0, 1, 0, 0, 0], [0, 1, 0, 0, 0, 0], [0, 0, 2, 0, 0, 0], [0, 0, 0, 0, 0, 0]]
[[0, 0, 0, 0, 0, 0], [0, 0, 0, 1, 0, 0], [0, 0, 1, 0, 0, 0], [0, 1, 0, 0, 0, 0], [0, 0, 2, 0, 0, 0], [0, 0, 0, 3, 0, 0]]

An observation from the shell print indicates the changes in the update of the table we used.
with the test care

  @Test
    public void testFindLength(){
       assertEquals(3,findLengthDP(new int[]{1,2,3,2,1},new int[]{3,2,1,4,7}));
    }

This indicates when 3==3 we added 1 to that i+1 row and j+1 col of our 2d table.
This shows when 3 was equal to 3 on the first line.

[[0, 0, 0, 0, 0, 0], [0, 0, 0, 1, 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]]

and subsequently the 2 and 1. In the last table. Our goal is to obtain the maximum because if i==j it implies the number
before it was equal. So in the end we obtain the maximum of our continuous subarrays.
We could reiterate the 2d array to obtain our max but the efficient way to keep hold of the current max we had so far.

Summary

Dp problems are tricky to develop formulas.
But sometimes it is the easiest.
More practice is needed to get hold of them