LeetCode Weekly Contest 274 Problems Solved
Table of contents
No headings in the article.
Last Year Was pretty Hectic, so i have decided to focus on Steady and consistent practise of Problem Solving, so i have kick started my new year, with a new LC Contest.
For the first time i was able to solve 3 out of 4 problems which i feel that as an accomplishment. So i propose my solutions to the above problems.
Firstly the three problems, which i encountered in the contest was pretty good. without any ambiguity so i really appreciate the problem setters for their clarity in the questions and now lets discuss the nitty gritty details of how i solved the 3 problems.
Problem 1 : 5967. Check if All A's Appears Before All B's
Given a string s consisting of only the characters 'a' and 'b', return true if every 'a' appears before every 'b' in the string. Otherwise, return false.
Sample Test Cases :
Input: s = "aaabbb"
Output: true
Explanation:
The 'a's are at indices 0, 1, and 2, while the 'b's are at indices 3, 4, and 5.
Hence, every 'a' appears before every 'b' and we return true.
Input: s = "abab"
Output: false
Explanation:
There is an 'a' at index 2 and a 'b' at index 1.
Hence, not every 'a' appears before every 'b' and we return false.
Input: s = "bbb"
Output: true
Explanation:
There are no 'a's, hence, every 'a' appears before every 'b' and we return true.
Solution --> My Approach:
Inorder to verify if A's arrives before B, it can be done by sorting the string and verifying it again with the original object. This was my approach in the contest may be could even try it in another optimized way , but i havent got any idea though.
Code snippet:
Code Author @Naveen Kumar Vadlamudi
def checkString(self, s: str) -> bool:
if s == ''.join(sorted(s)):
return True
else:
return False
The time Complexity of the above solution is O(N Log N) which is the worst case time for any sorting algorithm to sort the data in it and the compare operation takes O(1) time to do it.
So overall the time Complexity of the above algorithm is O(N Log N).
Problem 2 : 5968. Number of Laser Beams in a Bank
Anti-theft security devices are activated inside a bank. You are given a 0-indexed binary string array bank representing the floor plan of the bank, which is an m x n 2D matrix. bank[i] represents the ith row, consisting of '0's and '1's. '0' means the cell is empty, while'1' means the cell has a security device.
There is one laser beam between any two security devices if both conditions are met:
The two devices are located on two different rows: r1 and r2, where r1 < r2. For each row i where r1 < i < r2, there are no security devices in the ith row. Laser beams are independent, i.e., one beam does not interfere nor join with another.
Return the total number of laser beams in the bank.
Sample Test Cases:
Input: bank = ["011001","000000","010100","001000"]
Output: 8
Explanation: Between each of the following device pairs, there is one beam. In total, there are 8 beams:
* bank[0][1] -- bank[2][1]
* bank[0][1] -- bank[2][3]
* bank[0][2] -- bank[2][1]
* bank[0][2] -- bank[2][3]
* bank[0][5] -- bank[2][1]
* bank[0][5] -- bank[2][3]
* bank[2][1] -- bank[3][2]
* bank[2][3] -- bank[3][2]
Note that there is no beam between any device on the 0th row with any on the 3rd row.
This is because the 2nd row contains security devices, which breaks the second condition.
Test Case 2:
Input: bank = ["000","111","000"]
Output: 0
Explanation: There does not exist two devices located on two different rows.
Solution Proposed:
Code Author @Naveen Kumar Vadlamudi
def numberOfBeams(self, bank: List[str]) -> int:
lasers = []
for i in range(len(bank)):
cnt = 0
for char in bank[i]:
if char == '1':
cnt+=1
lasers.append(cnt)
while 0 in lasers:
lasers.remove(0)
if len(lasers) == 1 or not len(lasers) :
return 0
else:
initial = lasers[0]
cal_sum = 0
for i in range(1, len(lasers)):
cal_sum += initial * lasers[i]
initial = lasers[i]
return cal_sum
Problem 3 : 2126. Destroying Asteroids
You are given an integer mass, which represents the original mass of a planet. You are further given an integer array asteroids, where asteroids[i] is the mass of the ith asteroid.
You can arrange for the planet to collide with the asteroids in any arbitrary order. If the mass of the planet is greater than or equal to the mass of the asteroid, the asteroid is destroyed and the planet gains the mass of the asteroid. Otherwise, the planet is destroyed.
Return true if all asteroids can be destroyed. Otherwise, return false.
Sample Test Cases:
Input: mass = 10, asteroids = [3,9,19,5,21]
Output: true
Explanation: One way to order the asteroids is [9,19,5,3,21]:
- The planet collides with the asteroid with a mass of 9. New planet mass: 10 + 9 = 19
- The planet collides with the asteroid with a mass of 19. New planet mass: 19 + 19 = 38
- The planet collides with the asteroid with a mass of 5. New planet mass: 38 + 5 = 43
- The planet collides with the asteroid with a mass of 3. New planet mass: 43 + 3 = 46
- The planet collides with the asteroid with a mass of 21. New planet mass: 46 + 21 = 67
All asteroids are destroyed.
Input: mass = 5, asteroids = [4,9,23,4]
Output: false
Explanation:
The planet cannot ever gain enough mass to destroy the asteroid with a mass of 23.
After the planet destroys the other asteroids, it will have a mass of 5 + 4 + 9 + 4 = 22.
This is less than 23, so a collision would not destroy the last asteroid.
Proposed Solution:
Code Author @Naveen Kumar Vadlamudi
def asteroidsDestroyed(self, mass: int, asteroids: List[int]) -> bool:
asteroids.sort()
total_mass = mass
for i in asteroids:
if total_mass >= i:
total_mass += i
else:
return False
return True
I will continuously add more details and the approach of how i solved the problems, iteratively. Until then, please be engaged.
Finally, all the credits goes to LeetCode Company as the Questions and description provided in this blog are completely, proprietary to the Leet Code but the Solutions written here are my original thoughts and ideas, without copying from any source code.