Simple Java solution using HashMap


  • 3
    A
    class Solution {
        public int findLength(int[] A, int[] B) {
            int l1 = A.length, l2 = B.length, ans = 0;
            if (l1 == 0 || l2 == 0)
                return 0;        
            HashMap < Integer, List < Integer >> map = new HashMap < > ();
            List < Integer > list;
            for (int i = 0; i < l1; i++) {
                int n = A[i];
                list = map.getOrDefault(n, new ArrayList<Integer>());
                list.add(i);
                map.put(n, list);
            }
            
            for (int i = 0; i < l2 && l2-i > ans; i++) {
                int n = B[i];
                if (map.containsKey(n)){
                    list = map.get(n);
                    for (int m: list) {
                        if (l1 - m < ans)
                            break;                
                        int count = 1, k = m + 1;
                        for (int j = i + 1; j < l2 && k < l1; j++, k++) {
                            if (B[j] == A[k]) {
                                count++;
                            } else {
                                break;
                            }
                        }
                        ans = Math.max(ans, count);                
                    }
                }
            }
    
            return ans;
        }
    }
    

    Update: I have updated my code. Thanks for suggestions.


  • 0
    F

    Can you tell us your thinking in detail? thanks!


  • 1
    A

    I solved this problem using the hashtable and very similar approach. Here was my thinking:

    • First fill a hashtable with one of the arrays. The key is the number in the array, and the value[s] are the locations in the array that contain that number. This will be used to look up the starting index for any number.
    • Next iterate over the second array, for each value, if it doesn't existing in the hashtable (which is the first array), then continue.
      • If it does exist, iterate of each of the values, which are the starting index for that number in the second array.
      • Check the values in each array as the indexes is incremented. If the values match then increase the sequence count. If they don't match, then break of out that loop and continue to the next starting index for the first array.
    • Finally update the answer if a larger sequence is found
    • There's also an optimization which is for repeated numbers (maybe others) which is, if we've found a sequence larger than the length - index of the 2nd array, then we cannot find a larger one, so break out and return the max sequence right away. This prevents checking for a larger sequence that cannot exist.

    Hope that helps a bit.


  • 3
    A

    It is pretty simple logic.
    A: [1,2,3,2,1]
    B: [3,2,1,4,7]
    I am taking a hashmap, in which I am mapping the indexes of each element of 1st array, let's say A, in a list.

    In the first for loop,
    we will go through each element of A and check if it exists in the map.

    • if it does not exist...then create a list, add current element's index in the list and map current element to this list.
    • if it exists, then get the list associated with the current element, add current element's index in the list and map current element to this list.

    So, after 1st for loop, map will contain
    1 -> [0,4]....1's indexes in A are 0,4
    2 -> [1,3]...2's indexes in A are 1,3
    3 -> [2]....so on

    In the second loop, we will go through each element in B array

    for each n in B

    check if n exists in A

    • if it does not..then check next element of B because n does not exist in A, we don't get a repeated array
    • else it exists..then we got one common element, update ans to 1 if it is 0

    as n is present in A array, get its list which contains all the indexes of n in A.

    B[0] = 3;

    3 exists in map..so we go further in the loop.

    list = map.get(3) = [2];

    Now we go through each element of this list......
    the reason why I am doing this is....we need to find A:[a.....ab....abc...] B:[.......abc]
    We already found a..now we need to check for its next elements i.e. b and c.
    We will get the indexes of 'a' of first array A, by using list stored in the map...suppose it is j..then we will check if A[j+1] == B[i+1], A[j+2] == B[i+2]..so on until we find mismatch or the loop ends...we will increase count simultaneously. The count is the number of elements which are same.
    When the loop ends we will update final ans if it less than current count.

    so current list contains only 2..[2]...means A[2] = 3 and B[0] = 3
    we matched 3 with 3..we set count to 1.
    now match for 3,4,5... index of array A with i+1,i+2,i+3....index of array B and increase count..

    so...A[3] = B[1]..count = 2
    A[4] = B[2] count = 3
    loop ends..we get 3 as current max...

    try to go through rest of the elements, you will get it.

    I used one optimization, if(l1 - m < ans) break;
    l1 is the length of A, m is the index of current matched (first element of subarray in A). l1 - m gives us a maximum number of elements we can get starting from m in A. if it less than out current answer, then we do not need to go further, because we will not find greater length of repeated array starting from m. So we break.

    I hope this helps...


  • 0
    F

    Thank you very much! Very clear and readily expression。I have understood your thinking completely.


  • 0
    F

    Moreover, I think that your code should be written more concise. Many if......else code blocks are too lengthy.


  • 0
    C

    @ashish53v thank you l get a splendid way now


  • 0
    M

    @ashish53v I agree with @FuZhihong
    The idea might be a good one, but the coding style makes it hard to read and follow, especially with inconsistency of keywords continue and break in the nested for loop.
    Some code can also be shortened as well. But I think it's not gonna be a problem as you practice more (:

    
                if (map.containsKey(n)) {
                    list = map.get(n);
                    list.add(i);
                    map.put(n, list);
                } else {
                    list = new ArrayList < > ();
                    list.add(i);
                    map.put(n, list);
                }
    

    same as

    
                ArrayList<Integer> list = map.getOrDefault(n, new ArrayList<Integer>());
                list.add(i);
                map.put(n, list);
    
    
    

  • 0
    A

    @milkshakeplz @FuZhihong Yes, you are correct. The code could have been more concise.

    This code could have been avoided

              if (ans == 0) {
                    if (map.containsKey(n)) {
                        ans = 1;
                    } else {
                        continue;
                    }
                }
    

    Also, there are some blank lines, which had commented code. I forgot to remove those blank space.

    @milkshakeplz I am familiar with this style of code

                ArrayList<Integer> list = map.getOrDefault(n, new ArrayList<Integer>());
                list.add(i);
                map.put(n, list);
    

    But, it is not always the first thing which comes to my mind. Yes, you are right, it will come with more practice.

    Can you please elaborate more on inconsistency regarding continue and break statements in nested for loops and how can I avoid that?


  • 0

    @ashish53v

    I feel we can make it a bit faster by adding an additional check of max_cnt when looping through 2nd array,i.e, to check whether B_len-i > max_cnt. If max_cnt is greater than rest of the length of the array, then we just return the max_cnt right away.

    class Solution {
        public int findLength(int[] A, int[] B) {
            int cnt=0,max_cnt=0;
            int k = 0;
            int A_len = A.length;
            int B_len = B.length;
            
            Map<Integer,List<Integer>> m = new HashMap<>();
            for(int i=0;i<A_len;++i){
                if(m.containsKey(A[i])) m.get(A[i]).add(i);
                else{
                    List<Integer> l = new ArrayList<Integer>();
                    l.add(i);
                    m.put(A[i],l);
                }
            }
            
            for(int i=0;i<B_len && (B_len-i) > max_cnt;++i){
                if(m.containsKey(B[i])){
                    List<Integer> l = m.get(B[i]);
                    for(int idx:l){
                        if(A_len-idx < max_cnt) break;                    
                        k = 0;cnt = 0;
                        for(int j=idx;j<A_len && (i+k) < B_len;++j){
                            if(A[j] == B[i+k++]) cnt++;
                            else break;
                        }                    
                        max_cnt = max_cnt < cnt ? cnt : max_cnt;
                    }
                }
            }
           
            return max_cnt;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.