Weekly Contest 275 LeetCode Solution

Problem 1 – Check if Every Row and Column Contains All Numbers Leetcode Solution

An n x n matrix is valid if every row and every column contains all the integers from 1 to n (inclusive).

Given an n x n integer matrix matrix, return true if the matrix is valid. Otherwise, return false.

Example 1:

Input: matrix = [[1,2,3],[3,1,2],[2,3,1]]
Output: true
Explanation: In this case, n = 3, and every row and column contains the numbers 1, 2, and 3.
Hence, we return true.

Example 2:

Input: matrix = [[1,1,1],[1,2,3],[1,2,3]]
Output: false
Explanation: In this case, n = 3, but the first row and the first column do not contain the numbers 2 or 3.
Hence, we return false.

Constraints:

  • n == matrix.length == matrix[i].length
  • 1 <= n <= 100
  • 1 <= matrix[i][j] <= n

Check if Every Row and Column Contains All Numbers Leetcode Solution in Java

Using Hashset

    public boolean checkValid(int[][] matrix) {
        for (int r = 0, n = matrix.length; r < n; ++r) {
            Set<Integer> row = new HashSet<>();
            Set<Integer> col = new HashSet<>();
            for (int c = 0; c < n; ++c) {
                if (!row.add(matrix[r][c]) || !col.add(matrix[c][r])) {
                    return false;
                }
            }
        }
        return true;
    }

Using BitSet

    public boolean checkValid(int[][] matrix) {
        for (int r = 0, n = matrix.length; r < n; ++r) {
            BitSet row = new BitSet(n + 1), col = new BitSet(n + 1);
            for (int c = 0; c < n; ++c) {
                if (row.get(matrix[r][c]) || col.get(matrix[c][r])) {
                    return false;
                }
                row.set(matrix[r][c]);
                col.set(matrix[c][r]);
            }
        } 
        return true;
    }

Check if Every Row and Column Contains All Numbers Leetcode Solution in Python 3

Using Hashset

    def checkValid(self, matrix: List[List[int]]) -> bool:
        n = len(matrix)
        for row, col in zip(matrix, zip(*matrix)):
            if len(set(row)) != n or len(set(col)) != n:
                return False
        return True

Using BitSet

    def checkValid(self, matrix: List[List[int]]) -> bool:
        n = len(matrix)
        for r in range(n):
            row = bytearray(n + 1) 
            col = bytearray(n + 1) 
            for c in range(n):
                ro, co = matrix[r][c], matrix[c][r]
                row[ro] += 1
                col[co] += 1
                if row[ro] > 1 or col[co] > 1:
                    return False
        return True

Check if Every Row and Column Contains All Numbers Leetcode Solution in C++

bool checkValid(vector<vector<int>>& mat){
     int n= mat.size();	

     //mark position by making negative from positive ROW-WISE
     for(int i=0;i<n;i++){
         for(int j=0;j<n;j++){
             int pos= abs(mat[i][j]) -1 ;  // Getting position by value

             if( mat[i][pos] < 0 ) return false;    //If place already marked 
             mat[i][pos] = -mat[i][pos];    //Mark Place
         }
     }

     //mark position by making negative to positive COLUMN-WISE
     for(int i=0;i<n;i++){
         for(int j=0;j<n;j++){
             int pos= abs(mat[j][i]) -1 ;   // Getting position by value

             if( mat[pos][i] > 0 ) return false;    //If place already marked 
             mat[pos][i]= abs(mat[pos][i]);        //Mark Place
         }
     }

     return true;
}

Check if Every Row and Column Contains All Numbers Leetcode Solution in Go

func checkValid(matrix [][]int) bool {
	bitset := makeBitset(len(matrix) * 2)

	for i := 0; i < len(matrix); i++ {
		bitset.Clear()

		for j := 0; j < len(matrix); j++ {
			bitset.Set(matrix[i][j] - 1)
			bitset.Set(matrix[j][i] - 1 + len(matrix))
		}

		if !bitset.IsFilledUp() {
			return false
		}
	}

	return true
}

Check if Every Row and Column Contains All Numbers Leetcode Solution in JavaScript

var checkValid = function(matrix) {    
    for(let i =0; i<matrix.length;i++){
        const cols = new Set(), rows = new Set(matrix[i]);
		
        for(let j =0; j<matrix.length;j++){
            if(matrix[j][i] > matrix.length) return false;
            cols.add(matrix[j][i])
        }
		
        if(cols.size < matrix.length || rows.size < matrix.length) return false;
    }
    return true;
};

Check if Every Row and Column Contains All Numbers Leetcode Solution in Python

class Solution(object):
    def checkValid(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: bool
        """
        valid = set([i+1 for i in range(len(matrix))])
        
        # check row
        for i in range(len(matrix)):
            if set(matrix[i]) != valid:
                return False
        # check col
        for j in range(len(matrix)):
            if set([matrix[i][j] for i in range(len(matrix))]) != valid:
                return False
        return True

Problem 2 – Minimum Swaps to Group All 1’s Together II Leetcode Solution

swap is defined as taking two distinct positions in an array and swapping the values in them.

circular array is defined as an array where we consider the first element and the last element to be adjacent.

Given a binary circular array nums, return the minimum number of swaps required to group all 1‘s present in the array together at any location.

Example 1:

Input: nums = [0,1,0,1,1,0,0]
Output: 1
Explanation: Here are a few of the ways to group all the 1's together:
[0,0,1,1,1,0,0] using 1 swap.
[0,1,1,1,0,0,0] using 1 swap.
[1,1,0,0,0,0,1] using 2 swaps (using the circular property of the array).
There is no way to group all 1's together with 0 swaps.
Thus, the minimum number of swaps required is 1.

Example 2:

Input: nums = [0,1,1,1,0,0,1,1,0]
Output: 2
Explanation: Here are a few of the ways to group all the 1's together:
[1,1,1,0,0,0,0,1,1] using 2 swaps (using the circular property of the array).
[1,1,1,1,1,0,0,0,0] using 2 swaps.
There is no way to group all 1's together with 0 or 1 swaps.
Thus, the minimum number of swaps required is 2.

Example 3:

Input: nums = [1,1,0,0,1]
Output: 0
Explanation: All the 1's are already grouped together due to the circular property of the array.
Thus, the minimum number of swaps required is 0.

Constraints:

  • 1 <= nums.length <= 105
  • nums[i] is either 0 or 1.

Minimum Swaps to Group All 1’s Together II Leetcode Solution in Java

public int minSwaps(int[] nums) {
    int ones = Arrays.stream(nums).sum(), n = nums.length, res = nums.length;
    for (int i = 0, j = 0, cnt = 0; i < n; ++i) {
        while (j - i < ones)
            cnt += nums[j++ % n];
        res = Math.min(res, ones - cnt);
        cnt -= nums[i];
    }
    return res;
}

Minimum Swaps to Group All 1’s Together II Leetcode Solution in C++

int minSwaps(vector<int>& nums) {
    int ones = count(begin(nums), end(nums), 1), n = nums.size(), res = n;
    for (int i = 0, j = 0, cnt = 0; i < n; ++i) {
        while (j - i < ones)
            cnt += nums[j++ % n];
        res = min(res, ones - cnt);
        cnt -= nums[i];
    }
    return res;
}

Minimum Swaps to Group All 1’s Together II Leetcode Solution in Python

class Solution:
    def minSwaps(self, nums: List[int]) -> int:
        width = sum(num == 1 for num in nums) #width of the window
        nums += nums
        res = width
        curr_zeros = sum(num == 0 for num in nums[:width]) #the first window is nums[:width]
        
        for i in range(width, len(nums)):
            curr_zeros -= (nums[i - width] == 0) #remove the leftmost 0 if exists
            curr_zeros += (nums[i] == 0) #add the rightmost 0 if exists
            res = min(res, curr_zeros) #update if needed
        
        return res

Minimum Swaps to Group All 1’s Together II Leetcode Solution in Python 3

    def minSwaps(self, nums: List[int]) -> int:
        win_width = sum(nums)
        lo, mx, ones_in_win = -1, 0, 0
        n = len(nums)
        for hi in range(2 * n):
            ones_in_win += nums[hi % n]
            if hi - lo > win_width:
                lo += 1
                ones_in_win -= nums[lo % n]
            mx = max(mx, ones_in_win)    
        return win_width - mx

Problem 3 – Count Words Obtained After Adding a Letter Leetcode Solution

You are given two 0-indexed arrays of strings startWords and targetWords. Each string consists of lowercase English letters only.

For each string in targetWords, check if it is possible to choose a string from startWords and perform a conversion operation on it to be equal to that from targetWords.

The conversion operation is described in the following two steps:

  1. Append any lowercase letter that is not present in the string to its end.
    • For example, if the string is "abc", the letters 'd''e', or 'y' can be added to it, but not 'a'. If 'd' is added, the resulting string will be "abcd".
  2. Rearrange the letters of the new string in any arbitrary order.
    • For example, "abcd" can be rearranged to "acbd""bacd""cbda", and so on. Note that it can also be rearranged to "abcd" itself.

Return the number of strings in targetWords that can be obtained by performing the operations on any string of startWords.

Note that you will only be verifying if the string in targetWords can be obtained from a string in startWords by performing the operations. The strings in startWords do not actually change during this process.

Example 1:

Input: startWords = ["ant","act","tack"], targetWords = ["tack","act","acti"]
Output: 2
Explanation:
- In order to form targetWords[0] = "tack", we use startWords[1] = "act", append 'k' to it, and rearrange "actk" to "tack".
- There is no string in startWords that can be used to obtain targetWords[1] = "act".
  Note that "act" does exist in startWords, but we must append one letter to the string before rearranging it.
- In order to form targetWords[2] = "acti", we use startWords[1] = "act", append 'i' to it, and rearrange "acti" to "acti" itself.

Example 2:

Input: startWords = ["ab","a"], targetWords = ["abc","abcd"]
Output: 1
Explanation:
- In order to form targetWords[0] = "abc", we use startWords[0] = "ab", add 'c' to it, and rearrange it to "abc".
- There is no string in startWords that can be used to obtain targetWords[1] = "abcd".

Constraints:

  • 1 <= startWords.length, targetWords.length <= 5 * 104
  • 1 <= startWords[i].length, targetWords[j].length <= 26
  • Each string of startWords and targetWords consists of lowercase English letters only.
  • No letter occurs more than once in any string of startWords or targetWords.

Count Words Obtained After Adding a Letter Leetcode Solution in Python 3

class Solution:
    def wordCount(self, startWords: List[str], targetWords: List[str]) -> int:
        seen = set()
        for word in startWords: 
            m = 0
            for ch in word: m ^= 1 << ord(ch)-97
            seen.add(m)
            
        ans = 0 
        for word in targetWords: 
            m = 0 
            for ch in word: m ^= 1 << ord(ch)-97
            for ch in word: 
                if m ^ (1 << ord(ch)-97) in seen: 
                    ans += 1
                    break 
        return ans 

Count Words Obtained After Adding a Letter Leetcode Solution in C++

Using Trie

struct Trie {
    Trie* ch[26] = {};
    bool end = false;
    void insert(string &s, int p = 0) {
        if (p < s.size()) {
            int idx = s[p] - 'a';
            if (ch[idx] == nullptr)
                ch[idx] = new Trie();
            ch[idx]->insert(s, p + 1);
        }
        else
            end = true;
    }
    bool find(string &s, int p = 0, bool skipped = false) {
        if (p == s.size())
            return skipped && end;
        int idx = s[p] - 'a';
        return(ch[idx] != nullptr ? ch[idx]->find(s, p + 1, skipped) : false) || (skipped ? false : find(s, p + 1, true));
    }
};
int wordCount(vector<string>& startWords, vector<string>& targetWords) {
    Trie t;
    for (auto &w : startWords) {
        sort(begin(w), end(w));
        t.insert(w);
    }
    int res = 0;
    for (auto &w : targetWords) {
        sort(begin(w), end(w));
        res += t.find(w);
    }
    return res;    
}

Using BitMask

int wordCount(vector<string>& startWords, vector<string>& targetWords) {
    auto get_mask = [](string &w){
        return accumulate(begin(w), end(w), 0, [](int mask, char ch){ return mask + (1 << (ch - 'a')); });  
    };
    unordered_set<int> s;
    for (auto &w : startWords)
        s.insert(get_mask(w));
    int res = 0;
    for (auto &w : targetWords) {
        int mask = get_mask(w);
        res += any_of(begin(w), end(w), [&](char ch){ return s.count(mask - (1 << (ch - 'a'))); });
    }
    return res;
}

Count Words Obtained After Adding a Letter Leetcode Solution in Java

class Solution {
    public int wordCount(String[] startWords, String[] targetWords) {
        int n = startWords.length;
        int count = 0;
        Set<String> set = new HashSet<>();
        
        //1. store lexicographically sorted letters of startword in set
        for(String start: startWords){
            char[] sAr = start.toCharArray();
            Arrays.sort(sAr);
            set.add(new String(sAr));
        }
        int m = targetWords.length;
        boolean ans = false;
        for(int i = 0; i < m; i++){
            //2. sort lexicographically letters of targetword and store in new string s
            char[] tAr = targetWords[i].toCharArray();
            Arrays.sort(tAr);
            int k = tAr.length;
            String s = String.valueOf(tAr);
            
            ans = false;
            for(int j = 0; j < k; j++){
                //3. make a new string by omitting one letter from word and check if it is present in set than increase count value
                String str = s.substring(0,j) + s.substring(j+1);
                if(set.contains(str)){
                    count++;
                    break;
                }
            }
        }
        return count;    
    }
    
}

Count Words Obtained After Adding a Letter Leetcode Solution in Kotlin

class Solution {
    fun wordCount(startWords: Array<String>, targetWords: Array<String>): Int {
        val set = startWords.asSequence().map{it.hashify()}.toSet()        // start word set prime hash set: Compute "prime hash" from string in startWords by mapping every letter to a prime number and taking the product 
        fun filterCond(str: String) = str.hashify().let{hash -> str.asSequence().filter{set.contains(hash/primeMap[it]!!.toBigInteger())}.any()}  // Filter condition - take target word hash, divide by every prime of the corresponding char in the target word, check if result is in start word set
        return targetWords.asSequence().filter{filterCond(it)}.count() // just count how many match the filter condition
    }
    
    private fun String.hashify() = this.fold(1.toBigInteger()) { prod, it -> prod*primeMap[it]!!.toBigInteger()}  // Go through every char of the string, multiply it up after passing it through the hashmap
      
    val primeMap = mapOf(
        'a' to 2,
        'b' to 3,
        'c' to 5,
        'd' to 7,
        'e' to 11,
        'f' to 13,
        'g' to 17,
        'h' to 19,
        'i' to 23,
        'j' to 29,
        'k' to 31,
        'l' to 37,
        'm' to 41,
        'n' to 43,
        'o' to 47,
        'p' to 53,
        'q' to 59,
        'r' to 61,
        's' to 67,
        't' to 71,
        'u' to 73,
        'v' to 79,
        'w' to 83,
        'x' to 89,
        'y' to 97,
        'z' to 101
    )
}

Count Words Obtained After Adding a Letter Leetcode Solution in Python

class Solution:
    def wordCount(self, startWords: List[str], targetWords: List[str]) -> int:
        lookup = set()
        for word in startWords:
            lookup.add(frozenset(word))
        
        res = 0
        for word in targetWords:
            for i in range(len(word)):
                new_word = word[:i] + word[i+1:]
                if set(new_word) in lookup:
                    res += 1
                    break
        return res

Problem 4 – Earliest Possible Day of Full Bloom Leetcode Solution

You have n flower seeds. Every seed must be planted first before it can begin to grow, then bloom. Planting a seed takes time and so does the growth of a seed. You are given two 0-indexed integer arrays plantTime and growTime, of length n each:

  • plantTime[i] is the number of full days it takes you to plant the ith seed. Every day, you can work on planting exactly one seed. You do not have to work on planting the same seed on consecutive days, but the planting of a seed is not complete until you have worked plantTime[i] days on planting it in total.
  • growTime[i] is the number of full days it takes the ith seed to grow after being completely planted. After the last day of its growth, the flower blooms and stays bloomed forever.

From the beginning of day 0, you can plant the seeds in any order.

Return the earliest possible day where all seeds are blooming.

Example 1:

Input: plantTime = [1,4,3], growTime = [2,3,1]
Output: 9
Explanation: The grayed out pots represent planting days, colored pots represent growing days, and the flower represents the day it blooms.
One optimal way is:
On day 0, plant the 0th seed. The seed grows for 2 full days and blooms on day 3.
On days 1, 2, 3, and 4, plant the 1st seed. The seed grows for 3 full days and blooms on day 8.
On days 5, 6, and 7, plant the 2nd seed. The seed grows for 1 full day and blooms on day 9.
Thus, on day 9, all the seeds are blooming.

Example 2:

Input: plantTime = [1,2,3,2], growTime = [2,1,2,1]
Output: 9
Explanation: The grayed out pots represent planting days, colored pots represent growing days, and the flower represents the day it blooms.
One optimal way is:
On day 1, plant the 0th seed. The seed grows for 2 full days and blooms on day 4.
On days 0 and 3, plant the 1st seed. The seed grows for 1 full day and blooms on day 5.
On days 2, 4, and 5, plant the 2nd seed. The seed grows for 2 full days and blooms on day 8.
On days 6 and 7, plant the 3rd seed. The seed grows for 1 full day and blooms on day 9.
Thus, on day 9, all the seeds are blooming.

Example 3:

Input: plantTime = [1], growTime = [1]
Output: 2
Explanation: On day 0, plant the 0th seed. The seed grows for 1 full day and blooms on day 2.
Thus, on day 2, all the seeds are blooming.

Constraints:

  • n == plantTime.length == growTime.length
  • 1 <= n <= 105
  • 1 <= plantTime[i], growTime[i] <= 104

Earliest Possible Day of Full Bloom Leetcode Solution in C++

class Solution {
public:
    int earliestFullBloom(vector<int>& plantTime, vector<int>& growTime) {
        int n = plantTime.size();
        // growTime larger first
        vector<pair<int, int>> times(n);
        for (int i = 0; i < n; i++) {
            times[i].first = -growTime[i];
            times[i].second = plantTime[i];
        }
        sort(times.begin(), times.end());
        int tot = 0;
        int cur = 0;
        for (int i = 0; i < n; i++) {
            tot = max(tot, cur + times[i].second - times[i].first);
            cur += times[i].second;
        }
        return tot;
    }
};

Earliest Possible Day of Full Bloom Leetcode Solution in Python 3

class Solution:
    def earliestFullBloom(self, plantTime: List[int], growTime: List[int]) -> int:
        res = 0
        for grow, plant in sorted(zip(growTime, plantTime)):
            res = max(res, grow) + plant
        return res

Earliest Possible Day of Full Bloom Leetcode Solution in Python

class Solution:
    def earliestFullBloom(self, P, G):
        pairs = sorted((g, p) for g, p in zip(G, P))
        P = [p for _, p in pairs]
        G = [g for g, _ in pairs]
        ans, Q = sum(P), sum(P)
        p_acc = [0] + list(accumulate(P))
        for i in range(len(pairs)):
            ans = max(ans, Q - p_acc[i] + G[i])
        return ans

Earliest Possible Day of Full Bloom Leetcode Solution in Java

    public int earliestFullBloom(int[] plantTime, int[] growTime) {
        int n = growTime.length;
        List<Integer> indices = new ArrayList<>();
        for (int i = 0; i < n; ++i) {
            indices.add(i);
        }
        Collections.sort(indices, Comparator.comparingInt(i -> -growTime[i]));
        int max = 0;
        for (int i = 0, plantSum = 0; i < n; ++i) {
            int idx = indices.get(i);
            int time = plantSum + plantTime[idx] + growTime[idx];
            max = Math.max(max, time);
            plantSum += plantTime[idx];
        }
        return max;
    }
Weekly Contest 275 LeetCode Solution Review:

In our experience, we suggest you solve this Weekly Contest 275 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 275 LeetCode Solution

Find on LeetCode

Conclusion:

I hope this Weekly Contest 275 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.