Algorithm: Leetcode Contest 379

Challenges

10036. Minimum Moves to Capture The Queen

There is a 1-indexed 8 x 8 chessboard containing 3 pieces.

You are given 6 integers a, b, c, d, e, and f where:

• (a, b) denotes the position of the white rook.
• (c, d) denotes the position of the white bishop.
• (e, f) denotes the position of the black queen.

Given that you can only move the white pieces, return the minimum number of moves required to capture the black queen.

Note that:

• Rooks can move any number of squares either vertically or horizontally, but cannot jump over other pieces.
• Bishops can move any number of squares diagonally, but cannot jump over other pieces.
• A rook or a bishop can capture the queen if it is located in a square that they can move to.
• The queen does not move.

public int minMovesToCaptureTheQueen(int a, int b, int c, int d, int e, int f) {
        // no more than 2 moves, in worst case, rook can move to that line, then move to that vertical
        
        // so check if there is any case to complete in one move
        
        // rook & queen on same row/col, and there is no other piece
        // bishop & queue are on same diagnoal, and there is no piece between them
        int[] row = new int[]{a, c, e};
        int[] col = new int[]{b, d, f};
        
        // on same row
        if (row[0] == row[2]) {
            if (row[0] == row[1]) {
                if ((col[1] - col[0]) * (col[2] - col[0]) < 0) {
                    return 1;
                } else {
                    return Math.abs(col[1] - col[0]) > Math.abs(col[2] - col[0]) ? 1 : 2;
                }
            } else {
                return 1;
            }
        }
        
        // on same col
        if (col[0] == col[2]) {
            if (col[0] == col[1]) {
                if ((row[1] - row[0]) * (row[2] - row[0]) < 0) {
                    return 1;
                } else {
                    return Math.abs(row[1] - row[0]) > Math.abs(row[2] - row[0]) ? 1 : 2;
                }
            } else {
                return 1;
            }
        }
        
        // on same diagnoal with bishop
        if (Math.abs(row[2] - row[1]) == Math.abs(col[2] - col[1])) {
            // rook is also on diagono
            if (Math.abs(row[2] - row[0]) == Math.abs(col[2] - col[0])) {
                // if the rook is on same diagno
                if (((row[2] - row[1]) * (row[0] - row[1])) < 0 || ((col[2] - col[1]) * (col[0] - col[1])) < 0) {
                    return 1;
                } else {
                    // if the rook is between bishop & queen
                    if (Math.abs(row[0] - row[1]) < Math.abs(row[2] - row[1])) {
                        return 2;
                    } else {
                        return 1;
                    }
                }
            } else {
                return 1;
            }
        }
        
        return 2;
        
    }

10037. Maximum Size of a Set After Removals

You are given two 0-indexed integer arrays nums1 and nums2 of even length n.

You must remove n / 2 elements from nums1 and n / 2 elements from nums2. After the removals, you insert the remaining elements of nums1 and nums2 into a set s.

Return the maximum possible size of the set s.

Example 1:

Input: nums1 = [1,2,1,2], nums2 = [1,1,1,1]
Output: 2
Explanation: We remove two occurences of 1 from nums1 and nums2. After the removals, the arrays become equal to nums1 = [2,2] and nums2 = [1,1]. Therefore, s = {1,2}.
It can be shown that 2 is the maximum possible size of the set s after the removals.

public int maximumSetSize(int[] nums1, int[] nums2) {
        // borrow the idea from discussion
        
        Set<Integer> set1 = new HashSet<>();
        for(int num: nums1) {
            set1.add(num);
        }
        
        Set<Integer> set2 = new HashSet<>();
        for(int num: nums2) {
            set2.add(num);
        }
        
        Set<Integer> intersect = new HashSet<>(set1);
        intersect.retainAll(set2);
        
        // find the elements only exists in each num
        set1.removeAll(intersect);
        
        set2.removeAll(intersect);
        
        // unique counts provided by nums1 & nums2
        int count1 = Math.min(nums1.length / 2, set1.size());
        int count2 = Math.min(nums2.length / 2, set2.size());
        
        return Math.min(nums1.length, count1 + count2 + intersect.size());
        
    }

Retrospec

• in chest games, some time manipulate the position of chest is very head-spinning, we can leverage array and use each index to represent each piece.
• get the intersect of set
  • new HashSet<>(set1.retailAll(set2))
• understand which set manipulation to use is the difficulty part…