Weekly Contest 274 LeetCode Solution

Problem 1 – Check if All A’s Appears Before All B’s LeetCode Solution

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.

Example 1:

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.

Example 2:

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.

Example 3:

Input: s = "bbb"
Output: true
Explanation:
There are no 'a's, hence, every 'a' appears before every 'b' and we return true.

Constraints:

  • 1 <= s.length <= 100
  • s[i] is either 'a' or 'b'.

Check if All A’s Appears Before All B’s LeetCode Solution in Python

class Solution:
    def checkString(self, s: str) -> bool:
        return "ba" not in s

Check if All A’s Appears Before All B’s LeetCode Solution in C++

bool checkString(string s) {
        return s.find("ba")==string::npos;
    }

Check if All A’s Appears Before All B’s LeetCode Solution in Java

    public boolean checkString(String s) {
        for (int i = 1; i < s.length(); ++i) {
            if (s.charAt(i - 1) == 'b' && s.charAt(i) == 'a') {
                return false;
            }
        }
        return true;
    }

Check if All A’s Appears Before All B’s LeetCode Solution in Python 3

    def checkString(self, s: str) -> bool:
        for i, c in enumerate(s):
            if i > 0 and s[i - 1] == 'b' and c == 'a':
                return False
        return True

Check if All A’s Appears Before All B’s LeetCode Solution in JavaScript

var checkString = function(s) {
    
    // a cannot come after b
    let violation = "ba";
    
    return s.indexOf(violation, 0) == -1;
};

Check if All A’s Appears Before All B’s LeetCode Solution in Go

func checkString(s string) bool {
    
    // 'a' cannot come after 'b'
    violation := "ba"
    
    return strings.Count(s, violation) == 0
}

Problem 2 – Number of Laser Beams in a Bank LeetCode Solution

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 rowsr1 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.

Example 1:

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.

Example 2:

Input: bank = ["000","111","000"]
Output: 0
Explanation: There does not exist two devices located on two different rows.

Constraints:

  • m == bank.length
  • n == bank[i].length
  • 1 <= m, n <= 500
  • bank[i][j] is either '0' or '1'.

Number of Laser Beams in a Bank LeetCode Solution in C++

int numberOfBeams(vector<string>& bank) {
    int prev = 0, res = 0;
    for (auto &r : bank) {
        int cur = count(begin(r), end(r), '1');
        if (cur) {
            res += prev * cur;
            prev = cur;
        }
    }
    return res;
}

Number of Laser Beams in a Bank LeetCode Solution in Python 3

class Solution:
    def numberOfBeams(self, bank: List[str]) -> int:
        ans = prev = 0 
        for row in bank: 
            curr = row.count('1')
            if curr: 
                ans += prev * curr
                prev = curr 
        return ans 

Number of Laser Beams in a Bank LeetCode Solution in JavaScript

/**
 * @param {string[]} bank
 * @return {number}
 */
const numberOfBeams = (bank) =>
    bank
        .map((str) => str.split("0").join("").length)
        .filter((val) => val !== 0)
        .reduce((acc, cur, ind, arr) => acc + cur * (arr[ind + 1] || 0), 0);

Number of Laser Beams in a Bank LeetCode Solution in Python

class Solution(object):
    def numberOfBeams(self, bank):
        ans, pre = 0, 0
        for s in bank:
            n = s.count('1')
            if n == 0: continue
            ans += pre * n
            pre = n
        return ans

Number of Laser Beams in a Bank LeetCode Solution in Java

class Solution {
    public int numberOfBeams(String[] bank) {
        int ans = 0, pre = 0;
        for (int i = 0;i < bank.length; i ++) {
            int n = 0;
            for (int j = 0; j < bank[i].length(); j ++) if(bank[i].charAt(j) == '1') n ++;
            if (n == 0) continue;
            ans += pre * n;;
            pre = n;
        }
        return ans;
    }
}

Problem 3 – Destroying Asteroids LeetCode Solution

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.

Example 1:

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.

Example 2:

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.

Constraints:

  • 1 <= mass <= 105
  • 1 <= asteroids.length <= 105
  • 1 <= asteroids[i] <= 105

Destroying Asteroids LeetCode Solution in Java

    public boolean asteroidsDestroyed(int mass, int[] asteroids) {
        long m = mass;
        Arrays.sort(asteroids);
        for (int ast : asteroids) {
            if (m < ast) {
                return false;
            }
            m += ast;
        }
        return true;
    }

Destroying Asteroids LeetCode Solution in Python 3

    def asteroidsDestroyed(self, mass: int, asteroids: List[int]) -> bool:
        for a in sorted(asteroids):
            if mass < a:
                return False
            mass += a
        return True

Destroying Asteroids LeetCode Solution in C++

class Solution
{
    public:
    bool asteroidsDestroyed(int mass, vector<int>& arr)
    {
        sort(arr.begin(),arr.end());
        int n=arr.size();
        long long m=mass;
        for (int i=0;i<n;i++)
        {
            if (arr[i]<=m)
                m+=arr[i];
            else
                return false;
        }
        return true;
    }
};

Destroying Asteroids LeetCode Solution in Python

class Solution:
    def asteroidsDestroyed(self, mass: int, asteroids: List[int]) -> bool:
        
        asteroids.sort()
        
        for astMass in asteroids:
            if astMass <= mass:
                mass += astMass
            else:
                return False
        
        return True

Problem 4 – Maximum Employees to Be Invited to a Meeting LeetCode Solution

A company is organizing a meeting and has a list of n employees, waiting to be invited. They have arranged for a large circular table, capable of seating any number of employees.

The employees are numbered from 0 to n - 1. Each employee has a favorite person and they will attend the meeting only if they can sit next to their favorite person at the table. The favorite person of an employee is not themself.

Given a 0-indexed integer array favorite, where favorite[i] denotes the favorite person of the ith employee, return the maximum number of employees that can be invited to the meeting.

Example 1:

Input: favorite = [2,2,1,2]
Output: 3
Explanation:
The above figure shows how the company can invite employees 0, 1, and 2, and seat them at the round table.
All employees cannot be invited because employee 2 cannot sit beside employees 0, 1, and 3, simultaneously.
Note that the company can also invite employees 1, 2, and 3, and give them their desired seats.
The maximum number of employees that can be invited to the meeting is 3. 

Example 2:

Input: favorite = [1,2,0]
Output: 3
Explanation: 
Each employee is the favorite person of at least one other employee, and the only way the company can invite them is if they invite every employee.
The seating arrangement will be the same as that in the figure given in example 1:
- Employee 0 will sit between employees 2 and 1.
- Employee 1 will sit between employees 0 and 2.
- Employee 2 will sit between employees 1 and 0.
The maximum number of employees that can be invited to the meeting is 3.

Example 3:

Input: favorite = [3,0,1,4,1]
Output: 4
Explanation:
The above figure shows how the company will invite employees 0, 1, 3, and 4, and seat them at the round table.
Employee 2 cannot be invited because the two spots next to their favorite employee 1 are taken.
So the company leaves them out of the meeting.
The maximum number of employees that can be invited to the meeting is 4.

Constraints:

  • n == favorite.length
  • 2 <= n <= 105
  • 0 <= favorite[i] <= n - 1
  • favorite[i] != i

Maximum Employees to Be Invited to a Meeting LeetCode Solution in C++

class Solution {
public:
    int maximumInvitations(vector<int>& A) {
        int N = A.size();
        vector<int> m(N, -1); // m[i] is the depth of node i. -1 means unvisited
        vector<vector<int>> r(N); // The reverse graph
        for (int i = 0; i < N; ++i) r[A[i]].push_back(i);
        // handle case 1
        function<int(int)> dfs = [&](int u) {
            if (m[u] != -1) return m[u];
            int ans = 0;
            for (int v : r[u]) ans = max(ans, dfs(v));
            return m[u] = 1 + ans;
        };
        int ans = 0, free = 0;
        for (int i = 0; i < N; ++i) {
            if (m[i] != -1) continue; // skip visited nodes
            if (A[A[i]] == i) {
                m[i] = m[A[i]] = 0;
                int a = 0, b = 0; // find the length of the longest arms starting from `i` and `A[i]`
                for (int v : r[i]) {
                    if (v == A[i]) continue;
                    a = max(a, dfs(v));
                }
                for (int v : r[A[i]]) {
                    if (v == i) continue;
                    b = max(b, dfs(v));
                }
                free += a + b + 2; // this free component is of length `a+b+2`
            }
        }
        // handle case 2
        function<tuple<int, int, bool>(int)> dfs2 = [&](int u)->tuple<int, int, bool> {
            if (m[u] != -1) return {u, m[u], false}; // We visited this node the second time, so this node must be the entry point to the cycle
            m[u] = 0;
            auto [entryPoint, depth, cycleVisited] = dfs2(A[u]);
            if (cycleVisited) { // After the cycle being traversed, any other node in the backtracking process are outside of the cycle and should be ignored (by keeping m[u] as 0).
                return {entryPoint, depth, true};
            }
            m[u] = 1 + depth; // If we haven't met the entry point again, this is a node within the cycle, so we increment the depth.
            return {entryPoint, m[u], u == entryPoint}; // When we visit the entry point again, we know what we've done traversing the cycle.
        };
        for (int i = 0; i < N; ++i) {
            if(m[i] != -1) continue;
            auto [entryPoint, depth, cycleVisited] = dfs2(i);
            if (cycleVisited) ans = max(ans, depth);
        }
        return max(ans, free);
    }
};

Maximum Employees to Be Invited to a Meeting LeetCode Solution in Python

def maximumInvitations(self, A: List[int]) -> int:
		# First, we find the largest circle.
        n, maxc = len(A), 0
        seen = [0] * n
        for idx in range(n):
		
			# If a people hasn't been visited:
            if seen[idx] == 0:
                
				# start is for locating the first visited people, cur_people stands 
				#for the current people we are visiting, we use curset to store all 
				# the visited people in this iteration.
				start = idx
                cur_people = idx
                curset = set()
				
				# As long as we are visiting new people, we keep finding his/her favorite.
                while seen[cur_people] == 0:
                    seen[cur_people] = 1
                    curset.add(cur_people)
                    cur_people = A[cur_people]
					
				# Until we find the first visited people. Depends on if this 
				# visited people has been visited in eariler iteration or just this iteration.
				if cur_people in curset:       # if current people is in current set, meaning we have found a new circle
                    cursum = len(curset)
					
					# use 'start' to find the distance from the first visited people in this iteration 
					# to this current people.
                    while start != cur_people:
                        cursum -= 1
                        start = A[start]
                    maxc = max(maxc, cursum)
                                       
		# Then we try to find the sum of largest arms. Firstly, find all mutal-favorite peoples.
        pair = []
        visited = [0] * n
        for i in range(n):
		
			# If a is b's favorite and vise versa, we put them in 'pair'.
            if A[A[i]] == i and visited[i] == 0:
                pair.append([i, A[i]])
                visited[i] = 1
                visited[A[i]] = 1
		
		# for every people I, find out all the people whos favorite is I.
        res = 0
        child = collections.defaultdict(list)
        for i in range(n):
            child[A[i]].append(i)
        
        for a, b in pair:
            # max arm length start from first people a
            maxa = 0
            dq = collections.deque()
            for cand in child[a]:
                if cand != b:
                    dq.append([cand, 1])
            while dq:
                cur, n = dq.popleft()
                maxa = max(maxa, n)
                for nxt in child[cur]:
                    dq.append([nxt, n + 1])
                    
            # max arm length start from first people b
            maxb = 0
            dq = collections.deque()
            for cand in child[b]:
                if cand != a:
                    dq.append([cand, 1])
            while dq:
                cur, n = dq.popleft()
                maxb = max(maxb, n)
                for nxt in child[cur]:
                    dq.append([nxt, n + 1])
            
			# Thus the total length is the two longest arm plus 2 (a and b themselves)
            res += 2 + maxa + maxb
			
		# select the larger one as the answer.
        return max(maxc, res)  

Maximum Employees to Be Invited to a Meeting LeetCode Solution in Java

class Solution {
    public int maximumInvitations(int[] favorite) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < favorite.length; i++) {
            graph.add(new ArrayList<>());
        }

        int answer = 0;

        List<List<Integer>> pairs = new ArrayList<>();
        for (int i = 0; i < favorite.length; i++) {
            if (i == favorite[favorite[i]]) {
                if (i < favorite[i]) {
                    List<Integer> pair = new ArrayList<>();
                    pair.add(i);
                    pair.add(favorite[i]);
                    pairs.add(pair);
                }
            } else {
                graph.get(favorite[i]).add(i);
            }
        }

        boolean[] visited = new boolean[favorite.length];
        for (List<Integer> pair: pairs) {
            answer += dfs(graph, pair.get(0), visited) + dfs(graph, pair.get(1), visited);
        }
        
        int[] counter = new int[favorite.length];
        int[] round = new int[favorite.length];

        int rnd = 1;

        int circleMax = 0;

        for (int i = 0; i < favorite.length; i++) {
            if (visited[i]) {
                continue;
            }
            if (round[i] != 0) {
                continue;
            }

            int cnt = 1;
            int j = i;
            while (counter[j] == 0) {
                counter[j] = cnt;
                round[j] = rnd;
                j = favorite[j];
                cnt++;
            }
            if (round[j] == rnd) {
                circleMax = Math.max(circleMax, cnt - counter[j]);
            }
            rnd++;
        }
        return Math.max(circleMax, answer);
    }

    private int dfs(List<List<Integer>> graph, int node, boolean[] visited) {
        visited[node] = true;
        int max = 0;
        for (int neighbor: graph.get(node)) {
            max = Math.max(max, dfs(graph, neighbor, visited));
        }
        return max + 1;
    }
}

Maximum Employees to Be Invited to a Meeting LeetCode Solution in Python 3

class Solution:
    def maximumInvitations(self, favorite: List[int]) -> int:
        n = len(favorite)
        graph = [[] for _ in range(n)]
        for i, x in enumerate(favorite): graph[x].append(i)
        
        def bfs(x, seen): 
            """Return longest arm of x."""
            ans = 0 
            queue = deque([x])
            while queue: 
                for _ in range(len(queue)): 
                    u = queue.popleft()
                    for v in graph[u]: 
                        if v not in seen: 
                            seen.add(v)
                            queue.append(v)
                ans += 1
            return ans 
        
        ans = 0 
        seen = [False]*n
        for i, x in enumerate(favorite): 
            if favorite[x] == i and not seen[i]: 
                seen[i] = seen[x] = True 
                ans += bfs(i, {i, x}) + bfs(x, {i, x})
                
        dp = [0]*n
        for i, x in enumerate(favorite): 
            if dp[i] == 0: 
                ii, val = i, 0
                memo = {}
                while ii not in memo: 
                    if dp[ii]: 
                        cycle = dp[ii]
                        break
                    memo[ii] = val
                    val += 1
                    ii = favorite[ii]
                else: cycle = val - memo[ii]
                for k in memo: dp[k] = cycle
        return max(ans, max(dp))
Weekly Contest 274 LeetCode Solution Review:

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

Find on LeetCode

Conclusion:

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