LeetCode Biweekly Contest 174 Discussion and Solution

Problem-by-Problem Breakdown

Problem 1 - Best Reachable Tower

• Return the coordinates of the tower with the maximum quality factor.
• If there is a tie, return the tower with the lexicographically smallest coordinate. If no tower is reachable, return [-1, -1].

Approach

class Solution {
    public int[] bestTower(int[][] towers, int[] center, int radius) {
        int maxQ = Integer.MIN_VALUE;
        int[] ans = {-1, -1};
        
        for(int[] tower : towers){
            int x = tower[0];
            int y = tower[1];
            int q = tower[2];

            int cx = center[0];
            int cy = center[1];

            int dist = Math.abs(cx - x) + Math.abs(cy - y);

            if(dist <= radius){
                if(q > maxQ){
                    ans[0] = x;
                    ans[1] = y;
                    maxQ = q;
                }
                else if(q == maxQ){
                    boolean isSmaller = false;
                    
                    if(ans[0] == x) isSmaller = y < ans[1];
                    else isSmaller = x < ans[0];

                    if(isSmaller){
                        ans[0] = x;
                        ans[1] = y;
                    }
                }
            }
        }

        return ans;
    }
}

Problem 2 - Minimum Operations to Reach Target Array

• Choose an integer value x
• Find all maximal contiguous segments where nums[i] == x (a segment is maximal if it cannot be extended to the left or right while keeping all values equal to x)
• For each such segment [l, r], update simultaneously i.e. nums[l] = target[l], nums[l + 1] = target[l + 1], ..., nums[r] = target[r]

Approach

class Solution {
    public int minOperations(int[] nums, int[] target) {
        Set<Integer> set = new HashSet<>();

        int n = nums.length;

        for(int i = 0; i < n; i++){
            if(nums[i] != target[i]){
                set.add(nums[i]);
            }
        }

        return set.size();
    }
}

Problem 3 - Number of Alternating XOR Partitions

• XOR(b1) = target1
• XOR(b2) = target2 (if it exists)
• XOR(b3) = target1, and so on.

Approach

class Solution {
    public int getWays(int[] nums, int idx, boolean lastOne, int currXor, int target1, int target2, Map<Integer, Integer>[] dpOne, Map<Integer, Integer>[] dpTwo){
        int n = nums.length;

        currXor = currXor ^ nums[idx];

        if(lastOne && dpOne[idx].containsKey(currXor)) return dpOne[idx].get(currXor);
        if(!lastOne && dpTwo[idx].containsKey(currXor)) return dpTwo[idx].get(currXor);

        if(idx == n - 1){
            if(lastOne && currXor == target2) return 1;
            else if(!lastOne && currXor == target1) return 1;
            else return 0;
        }

        long ways = getWays(nums, idx + 1, lastOne, currXor, target1, target2, dpOne, dpTwo);
        
        if(lastOne && currXor == target2){
            ways += getWays(nums, idx + 1, !lastOne, 0, target1, target2, dpOne, dpTwo);
        }
        else if(!lastOne && currXor == target1){
            ways += getWays(nums, idx + 1, !lastOne, 0, target1, target2, dpOne, dpTwo);
        }

        int way = (int) (ways % 1000000007);

        if(lastOne) dpOne[idx].put(currXor, way);
        if(!lastOne) dpTwo[idx].put(currXor, way);

        return way;
    }
    public int alternatingXOR(int[] nums, int target1, int target2) {
        int n = nums.length;

        Map<Integer, Integer>[] dpOne = new HashMap[n];
        Map<Integer, Integer>[] dpTwo = new HashMap[n];

        for(int i = 0; i < n; i++){
            dpOne[i] = new HashMap<>();
            dpTwo[i] = new HashMap<>();
        }

        int totalWays = getWays(nums, 0, false, 0, target1, target2, dpOne, dpTwo);

        return totalWays;
    }
}

Problem 4 - Minimum Edge Toggles on a Tree

Approach

My Contest Experience