MaxCommonSubarrayInMatrix.java

package playground;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class MaxCommonSubarrayInMatrix {
    public static void main(String[] args) {
        MaxCommonSubarrayInMatrix maxCommonSubarrayInMatrix = new MaxCommonSubarrayInMatrix();
//        maxCommonSubarrayInMatrix.action(
//                new int[][]{
//                        {1,2,3}, {3,1,2},
//                }
//        );
//        maxCommonSubarrayInMatrix.action(
//                new int[][]{
//                        {1,2,3,4}, {3,4,1,2},
//                }
//        );
//        maxCommonSubarrayInMatrix.action(
//                new int[][]{
//                        {2,3,4,5,1}, {4,5,1,3,2},
//                }
//        );
        maxCommonSubarrayInMatrix.action(
                new int[][]{
                        {2,3,14,5,1,9}, {4,5,15,5,1,9},{1,2,31,5,1,9}
                }
        );

    }
    Map<String, Integer> mp;
    public void action(int[][] arr){
        mp = new HashMap<>();
        System.out.println(
                getMaxCommonSubarrayInMatrix(arr)
        );
    }
    public int getMaxCommonSubarrayInMatrix(int[][] arr){
        Map<Integer, Integer> otherMap =new HashMap<>();
//        int ans = 0;
        // O(n^2) loop to get directional pairs
        // if a directional pair exist in all of rows() then it might be part of final max subarray
         for(int i=0;i<arr.length;++i){
            for(int j=0;j<arr[0].length-1;++j){
                String key = String.format("%s|%s", arr[i][j], arr[i][j+1]);
                mp.put(key, mp.getOrDefault(key, 0)+1);
                if(mp.get(key) == arr.length){
//                    System.out.println(mp.get(key));
//                    ans = mp.get(key);
                    otherMap.put(arr[i][j], arr[i][j+1]);
                }
            }
        }
        System.out.println(otherMap);
        // here we need to merge all intervals
        // merging logic is just O(N) operation
        // going as deep as can while following trail on hashmap
        int maxcount =0;
        for(Map.Entry<Integer, Integer> entry : otherMap.entrySet()){
            int count = 0;
            Integer startKey = entry.getKey();
            while(
                            otherMap.containsKey(startKey)){
                count++;
                startKey = otherMap.get(startKey);
            }
            maxcount = Math.max(maxcount, count);
        }

        return maxcount;
    }
}