304 North Cardinal St.
Dorchester Center, MA 02124

# 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) {
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;
}

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 = "tack", we use startWords = "act", append 'k' to it, and rearrange "actk" to "tack".
- There is no string in startWords that can be used to obtain targetWords = "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 = "acti", we use startWords = "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 = "abc", we use startWords = "ab", add 'c' to it, and rearrange it to "abc".
- There is no string in startWords that can be used to obtain targetWords = "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

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 = {};
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;
}
``````

``````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)
int res = 0;
for (auto &w : targetWords) {
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);
}
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:

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 = , growTime = 
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;
}
}
};
``````

### 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 =  + 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) {
}
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