Physical Address
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].length1 <= n <= 1001 <= 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
A swap is defined as taking two distinct positions in an array and swapping the values in them.
A 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 <= 105nums[i]is either0or1.
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:
- 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".
- For example, if the string is
- 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.
- For example,
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 * 1041 <= startWords[i].length, targetWords[j].length <= 26- Each string of
startWordsandtargetWordsconsists of lowercase English letters only. - No letter occurs more than once in any string of
startWordsortargetWords.
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 theithseed. 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 workedplantTime[i]days on planting it in total.growTime[i]is the number of full days it takes theithseed 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.length1 <= n <= 1051 <= 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
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 >>
