Weekly Contest 299 LeetCode Solution

Problem 1 – Check if Matrix Is X-Matrix LeetCode Solution

A square matrix is said to be an X-Matrix if both of the following conditions hold:

  1. All the elements in the diagonals of the matrix are non-zero.
  2. All other elements are 0.

Given a 2D integer array grid of size n x n representing a square matrix, return true if grid is an X-Matrix. Otherwise, return false.

Example 1:

Input: grid = [[2,0,0,1],[0,3,1,0],[0,5,2,0],[4,0,0,2]]
Output: true
Explanation: Refer to the diagram above. 
An X-Matrix should have the green elements (diagonals) be non-zero and the red elements be 0.
Thus, grid is an X-Matrix.

Example 2:

Input: grid = [[5,7,0],[0,3,1],[0,5,0]]
Output: false
Explanation: Refer to the diagram above.
An X-Matrix should have the green elements (diagonals) be non-zero and the red elements be 0.
Thus, grid is not an X-Matrix.

Constraints:

  • n == grid.length == grid[i].length
  • 3 <= n <= 100
  • 0 <= grid[i][j] <= 105

Check if Matrix Is X-Matrix LeetCode Solution is Python

class Solution:
    def checkXMatrix(self, grid: List[List[int]]) -> bool:
        n = len(grid)
        for i in range(n):
            for j in range(n):
                if i==j or (i+j) ==n-1:
                    if grid[i][j] == 0:
                        return False
                elif grid[i][j] != 0: 
                    return False
        return True;

Check if Matrix Is X-Matrix LeetCode Solution is Java

class Solution {
    public boolean checkXMatrix(int[][] grid) {
        
        int n = grid.length;
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++ ){
                if ( i == j  || i + j == n - 1 ) {
                    if ( grid[i][j] == 0 ) return false;                    
                }
				else if ( grid[i][j] != 0 ) return false;                                    
            }
        }       
       return true;
    }
}

Check if Matrix Is X-Matrix LeetCode Solution is C++

class Solution {
public:
    bool checkXMatrix(vector<vector<int>>& v1) {
        int n = v1.size();
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(i==j || (i+j) == n-1){
                    if(v1[i][j]==0)     return false;
                }
				else if(v1[i][j]!=0)     return false;
            }
        }
        return true;
    }
};

Problem 2 – Count Number of Ways to Place Houses LeetCode Solution

There is a street with n * 2 plots, where there are n plots on each side of the street. The plots on each side are numbered from 1 to n. On each plot, a house can be placed.

Return the number of ways houses can be placed such that no two houses are adjacent to each other on the same side of the street. Since the answer may be very large, return it modulo 109 + 7.

Note that if a house is placed on the ith plot on one side of the street, a house can also be placed on the ith plot on the other side of the street.

Example 1:

Input: n = 1
Output: 4
Explanation: 
Possible arrangements:
1. All plots are empty.
2. A house is placed on one side of the street.
3. A house is placed on the other side of the street.
4. Two houses are placed, one on each side of the street.

Example 2:

Input: n = 2
Output: 9
Explanation: The 9 possible arrangements are shown in the diagram above.

Constraints:

  • 1 <= n <= 104

Count Number of Ways to Place Houses LeetCode Solution in Java

    public int countHousePlacements(int n) {
        int a = 1, b = 1, c = 2, mod = (int)1e9 + 7;
        for (int i = 0; i < n; ++i) {
            c = (a + b) % mod;
            a = b;
            b = c;
        }
        return (int)(1L * b * b % mod);
    }

Count Number of Ways to Place Houses LeetCode Solution in C++

    int countHousePlacements(int n) {
        int a = 1, b = 1, c = 2, mod = 1e9 + 7;
        for (int i = 0; i < n; ++i) {
            c = (a + b) % mod;
            a = b;
            b = c;
        }
        return 1L * b * b % mod;
    }

Count Number of Ways to Place Houses LeetCode Solution in Python

    def countHousePlacements(self, n):
        a, b, mod = 1, 1, 10**9 + 7
        for i in range(n):
            a, b = b, (a + b) % mod
        return b * b % mod

Problem 3 – Maximum Score Of Spliced Array LeetCode Solution

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

You can choose two integers left and right where 0 <= left <= right < n and swap the subarray nums1[left...right] with the subarray nums2[left...right].

  • For example, if nums1 = [1,2,3,4,5] and nums2 = [11,12,13,14,15] and you choose left = 1 and right = 2nums1 becomes [1,12,13,4,5] and nums2 becomes [11,2,3,14,15].

You may choose to apply the mentioned operation once or not do anything.

The score of the arrays is the maximum of sum(nums1) and sum(nums2), where sum(arr) is the sum of all the elements in the array arr.

Return the maximum possible score.

subarray is a contiguous sequence of elements within an array. arr[left...right] denotes the subarray that contains the elements of nums between indices left and right (inclusive).

Example 1:

Input: nums1 = [60,60,60], nums2 = [10,90,10]
Output: 210
Explanation: Choosing left = 1 and right = 1, we have nums1 = [60,90,60] and nums2 = [10,60,10].
The score is max(sum(nums1), sum(nums2)) = max(210, 80) = 210.

Example 2:

Input: nums1 = [20,40,20,70,30], nums2 = [50,20,50,40,20]
Output: 220
Explanation: Choosing left = 3, right = 4, we have nums1 = [20,40,20,40,20] and nums2 = [50,20,50,70,30].
The score is max(sum(nums1), sum(nums2)) = max(140, 220) = 220.

Example 3:

Input: nums1 = [7,11,13], nums2 = [1,1,1]
Output: 31
Explanation: We choose not to swap any subarray.
The score is max(sum(nums1), sum(nums2)) = max(31, 3) = 31.

Constraints:

  • n == nums1.length == nums2.length
  • 1 <= n <= 105
  • 1 <= nums1[i], nums2[i] <= 104

Maximum Score Of Spliced Array LeetCode Solution in C++

int kadane(vector<int>& n1, vector<int>& n2) {
    int sz = n1.size(), sum = 0, res = 0;
    for (int i = 0; i < sz; ++i) {
        sum = max(n2[i] - n1[i], sum + n2[i] - n1[i]);
        res = max(res, sum);
    }
    return res;
}
int maximumsSplicedArray(vector<int>& n1, vector<int>& n2) {
    return max(accumulate(begin(n1), end(n1), 0) + kadane(n1, n2),
               accumulate(begin(n2), end(n2), 0) + kadane(n2, n1));
}

Maximum Score Of Spliced Array LeetCode Solution in Python

    def maximumsSplicedArray(self, A, B):
        def kadane(A, B):
            res = cur = 0
            for i in range(len(A)):
                cur = max(0, cur + A[i] - B[i])
                res = max(res, cur)
            return res + sum(B)
        return max(kadane(A, B), kadane(B, A))

Maximum Score Of Spliced Array LeetCode Solution in Java

class Solution {
    public int maximumsSplicedArray(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int sum1=0,sum2=0;
        int[] arr = new int[n];
/* --------------- to maximize nums1 -------------------*/
        for(int i=0;i<n;i++){
            sum1+=nums1[i];
            sum2+=nums2[i];
            arr[i] = nums2[i]-nums1[i];
        }
        int max=0, cur=0;
        for (int i:arr){
            cur = Math.max(cur+i,i);
            max = Math.max(max, cur);	
        }
        sum1 += max;
/* --------------- to maximize nums2 -------------------*/
        for(int i=0;i<n;i++){
            arr[i] = nums1[i]-nums2[i];
        }
        max=0; cur=0;
        for (int i:arr){
            cur= Math.max(cur+i,i);
            max=Math.max(max, cur);	
        }
        sum2 += max;
        return Math.max(sum1,sum2);
    }
}

Problem 4 – Minimum Score After Removals on a Tree LeetCode Solution

There is an undirected connected tree with n nodes labeled from 0 to n - 1 and n - 1 edges.

You are given a 0-indexed integer array nums of length n where nums[i] represents the value of the ith node. You are also given a 2D integer array edges of length n - 1 where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi in the tree.

Remove two distinct edges of the tree to form three connected components. For a pair of removed edges, the following steps are defined:

  1. Get the XOR of all the values of the nodes for each of the three components respectively.
  2. The difference between the largest XOR value and the smallest XOR value is the score of the pair.
  • For example, say the three components have the node values: [4,5,7][1,9], and [3,3,3]. The three XOR values are 4 ^ 5 ^ 7 = 61 ^ 9 = 8, and 3 ^ 3 ^ 3 = 3. The largest XOR value is 8 and the smallest XOR value is 3. The score is then 8 - 3 = 5.

Return the minimum score of any possible pair of edge removals on the given tree.

Example 1:

Input: nums = [1,5,5,4,11], edges = [[0,1],[1,2],[1,3],[3,4]]
Output: 9
Explanation: The diagram above shows a way to make a pair of removals.
- The 1st component has nodes [1,3,4] with values [5,4,11]. Its XOR value is 5 ^ 4 ^ 11 = 10.
- The 2nd component has node [0] with value [1]. Its XOR value is 1 = 1.
- The 3rd component has node [2] with value [5]. Its XOR value is 5 = 5.
The score is the difference between the largest and smallest XOR value which is 10 - 1 = 9.
It can be shown that no other pair of removals will obtain a smaller score than 9.

Example 2:

Input: nums = [5,5,2,4,4,2], edges = [[0,1],[1,2],[5,2],[4,3],[1,3]]
Output: 0
Explanation: The diagram above shows a way to make a pair of removals.
- The 1st component has nodes [3,4] with values [4,4]. Its XOR value is 4 ^ 4 = 0.
- The 2nd component has nodes [1,0] with values [5,5]. Its XOR value is 5 ^ 5 = 0.
- The 3rd component has nodes [2,5] with values [2,2]. Its XOR value is 2 ^ 2 = 0.
The score is the difference between the largest and smallest XOR value which is 0 - 0 = 0.
We cannot obtain a smaller score than 0.

Constraints:

  • n == nums.length
  • 3 <= n <= 1000
  • 1 <= nums[i] <= 108
  • edges.length == n - 1
  • edges[i].length == 2
  • 0 <= ai, bi < n
  • ai != bi
  • edges represents a valid tree.

Minimum Score After Removals on a Tree LeetCode Solution in C++

class Solution {
    vector<bool> visited;
    vector<vector<int>> pc, adj; // pc is the parent child edge in our dfs
    vector<vector<bool>> childs; // 2D array to store that i is a parent of j
    vector<int> child_xor, nums, par; // child_xor to store result of xors of a child node and par is a gloable array to track the parents of a node in dfs
    
    int dfs(int i) {
        int ans = nums[i];
        visited[i] = true;
		
		for (int p: par) childs[p][i] = true; // Defining this node as the child of all its parents
		
        par.push_back(i);
        
        for (int child: adj[i])
            if (!visited[child]) {
                pc.push_back({i, child});
                ans ^= dfs(child); // Recurcively calculating xors
            }
        
        par.pop_back();
        
        return child_xor[i] = ans;
    }
public:
    int minimumScore(vector<int>& nums, vector<vector<int>>& edges) {
		// Initialising gloable variables
        int n = nums.size(), ans = INT_MAX;
        visited = vector<bool>(n);
        pc = vector<vector<int>>();
        adj = vector<vector<int>>(n);
        child_xor = vector<int>(n, 0);
        childs = vector<vector<bool>>(n, vector<bool>(n, false));
        this->nums = nums;
		par = vector<int>();
		
		// Creating an adjacency matrix
        for (vector<int> &edge: edges) adj[edge[0]].push_back(edge[1]), adj[edge[1]].push_back(edge[0]);
		
        dfs(0);
        
        for (int i = 0; i < pc.size(); i++)
            for (int j = i + 1; j < pc.size(); j++) { // removing an edge i and j
                int a = pc[i][1], b = pc[j][1]; // node that will come below when you delete an edge i and j
                int xa = child_xor[a], xb = child_xor[b], xc = child_xor[0];
                
                if (childs[a][b])
                    xc ^= xa, xa ^= xb;
                else
                    xc ^= xa, xc ^= xb;
                
                ans = min(max(xa, max(xb, xc)) - min(xa, min(xb, xc)), ans);
            }
        
        return ans;
    }
};

Minimum Score After Removals on a Tree LeetCode Solution in Python

class Solution:
    def minimumScore(self, nums: List[int], edges: List[List[int]]) -> int:
        n = len(nums)
        visited = [False for _ in range(n)]
        pc = [] # Store the parent child edge node in our dfs
        adj = [[] for _ in range(n)]
        
        for edge in edges:
            adj[edge[0]].append(edge[1])
            adj[edge[1]].append(edge[0])
        
        childs = [[False for _ in range(n)] for _ in range(n)] # To store if node a contains b as on of its child tree
        child_xor = [0 for _ in range(n)] # To store the xor of node a and all its child tree
        par = [] to store parents of a node a while doing DFS
        
        def dfs(i: int) -> int:
            ans = nums[i]
            visited[i] = True
            
            for p in par: childs[p][i] = True
                
            par.append(i)
            
            for child in adj[i]:
                if (not visited[child]):
                    pc.append([i, child])
                    ans ^= dfs(child)
            
            par.pop()
            child_xor[i] = ans
            
            return ans
        
        dfs(0)
        
        ans = 1000000000
        
        for i in range(len(pc)):
            for j in range(i + 1, len(pc)):
                (a, b) = (pc[i][1], pc[j][1])
				(xa, xb, xc) = (child_xor[a], child_xor[b], child_xor[0])
                
                if childs[a][b]: # here a is an ancestor of b or a has b in its child tree
                    xc ^= xa
                    xa ^= xb
                else:
                    xc ^= xa
                    xc ^= xb
                
                ans = min(max(xa, xb, xc) - min(xa, xb, xc), ans)
        
        return ans

Minimum Score After Removals on a Tree LeetCode Solution in Java

class Solution {
    
    private int ans = Integer.MAX_VALUE;

    private int helper(int src, ArrayList<Integer>[] graph, int[] arr, int par, int block, int xor1, int tot) { // function to travel 2nd time on the tree and find the second edge to be removed
	
        int myXOR = arr[src];   // Setting the value for the current subtree's XOR value
        
        for (int nbr : graph[src]) {
            if (nbr != par && nbr != block) { // If the current nbr is niether the parent of this node nor the blocked node  , then only we'll proceed
			
                int nbrXOR = helper(nbr, graph, arr, src, block, xor1, tot);
				// 'src <----> nbr' is the second edge to be removed
				
				int xor2 = nbrXOR; // Getting the XOR value of the current neighbor
            
				int xor3 = (tot ^ xor1) ^ xor2;  // The XOR of the remaining component
                
                int max = Math.max(xor1, Math.max(xor2, xor3));   // Getting the minimum of the three values
                int min = Math.min(xor1, Math.min(xor2, xor3));    // Getting the maximum of the three value
                 
                this.ans = Math.min(ans, max - min);
				
                myXOR ^= nbrXOR;  // Including the neighbour subtree's XOR value in the XOR value of the subtree rooted at src node

            }
        }
        
        return myXOR;  // Returing the XOR value of the current subtree rooted at the src node
    }
    
    private int dfs(int src, ArrayList<Integer>[] graph, int[] arr, int par, int tot) { // function to travel 1st time on the tree and find the first edge to be removed and then block the node at which the edge ends to avoid selecting the same node again
        int myXOR = arr[src]; // Setting the value for the current subtree's XOR value
        for (int nbr : graph[src]) {
            if (nbr != par) { // If the current nbr is not the parent of this node, then only we'll proceed
                
                int nbrXOR = dfs(nbr, graph, arr, src, tot);  // After selecting 'src <----> nbr' as the first edge, we block 'nbr' node and then make a call to try all the second edges
            
				// Calling the helper to find the try all the second edges after blocking the current node
                helper(0, graph, arr, -1, nbr, nbrXOR, tot); 
				
				myXOR ^= nbrXOR; // Including the neighbour subtree's XOR value in the XOR value of the subtree rooted at src node
            }
        }
        
        return myXOR; // Returing the XOR value of the current subtree rooted at the src node
        
    }
    
    public int minimumScore(int[] arr, int[][] edges) {
        int n = arr.length;
        ArrayList<Integer>[] graph = new ArrayList[n];
        int tot = 0;
        
        for (int i = 0; i < n; i++) {
			// Initializing the graph and finding the total XOR
            graph[i] = new ArrayList<>();
            tot ^= arr[i];
        }
        
        
        for (int[] edge : edges) {
			// adding the edges 
            int u = edge[0], v = edge[1];
            graph[u].add(v);
            graph[v].add(u);
        }
        
       
        this.ans = Integer.MAX_VALUE;
   
        dfs(0, graph, arr, -1, tot);
        
        return this.ans;
    }
}
Weekly Contest 299 LeetCode Solution Review:

In our experience, we suggest you solve this Weekly Contest 299 LeetCode Solution and gain some new skills from Professionals completely free and we assure you will be worth it.

If you are stuck anywhere between any coding problem, just visit Queslers to get the Weekly Contest 299 LeetCode Solution

Find on LeetCode

Conclusion:

I hope this Weekly Contest 299 LeetCode Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.

This Problem is intended for audiences of all experiences who are interested in learning about Data Science in a business context; there are no prerequisites.

Keep Learning!

More Coding Solutions >>

LeetCode Solutions

Hacker Rank Solutions

CodeChef Solutions

Leave a Reply

Your email address will not be published.