source: https://leetcode.com/problems/uncrossed-lines/description/
Uncrossed Lines
You are given two integer arrays nums1 and nums2. We write the integers of nums1 and nums2 (in the order they are given) on two separate horizontal lines.
We may draw connecting lines: a straight line connecting two numbers nums1[i] and nums2[j] such that:
- nums1[i] == nums2[j], and
- the line we draw does not intersect any other connecting (non-horizontal) line.
Note that a connecting line cannot intersect even at the endpoints (i.e., each number can only belong to one connecting line).
Return the maximum number of connecting lines we can draw in this way.
Example 1:
Input: nums1 = [1,4,2], nums2 = [1,2,4]
Output: 2
Explanation: We can draw 2 uncrossed lines as in the diagram.
We cannot draw 3 uncrossed lines, because the line from nums1[1] = 4 to nums2[2] = 4 will intersect the line from nums1[2]=2 to nums2[1]=2.
Example 2:
Input: nums1 = [2,5,1,2,5], nums2 = [10,5,2,1,5,2]
Output: 3
Example 3:
Input: nums1 = [1,3,7,1,7,5], nums2 = [1,9,2,5,1]
Output: 2
Constraints:
- 1 <= nums1.length, nums2.length <= 500
- 1 <= nums1[i], nums2[j] <= 2000
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
class Solution { public int maxUncrossedLines(int[] nums1, int[] nums2) { //create a map with key as a number in nums2 and value as a list of indices it appear in //nums2 Map<Integer, List<Integer>> indexMap = new HashMap<>(); for(int i=0;i<nums2.length;i++){ indexMap.computeIfAbsent(nums2[i], k->new ArrayList<>()).add(i); } Integer[][] memo = new Integer[nums1.length+1][nums2.length+1]; return dfs(nums1, indexMap, 0, 0, memo); } private int dfs(int[] nums1, Map<Integer, List<Integer>> indexMap, int i1, int i2, Integer[][] memo){ if(i1 >= nums1.length) return 0; if(memo[i1][i2]!=null) return memo[i1][i2]; int max = 0; //search for a number nums1[i1] in the indexMap if(indexMap.containsKey(nums1[i1])) { List<Integer> l = indexMap.get(nums1[i1]); //check the index of nums1[i1] in the indexMap int newIndex = exists(l, i2); if(newIndex >=i2){ max = Math.max(max, 1+dfs(nums1, indexMap, i1+1, newIndex+1, memo)); } } max = Math.max(max, dfs(nums1, indexMap, i1+1, i2, memo)); memo[i1][i2] = max; return max; } private int exists(List<Integer> l, int target){ int lo=0; int hi=l.size()-1; while(lo<hi){ int mid = lo + (hi-lo)/2; if(l.get(mid) < target){ lo = mid+1; } else { hi = mid; } } return l.get(lo); } } |