952. Largest Component Size by Common Factor

Union Find is a natural way to combine different sets with connection into one set. So the basic idea is:

• If two numbers have common factor, union them
• During the union process, maintain a set size as the final answer is asking for…

2081. Sum of k-Mirror Numbers

This week’s (weekly 268)last question can be solved by checking all the possible numbers in a brute force way. In order to construct all the possible candidates, we can use backtracking based on standard approaches. If you are using python, luckily, we can use itertools.porduct…

2076. Process Restricted Friend Requests

Are you sure you really master the UF data structure/algorithm? If you are, you can use this question to verify your skills of using UF. This is the 4th question of the LC weekly 267 contest. It is pretty fun.

Basic ideas

• basic UF
• + maintain members…

Solution 1: brute force by organizing the words in 26 categories (run time 1016 ms).

• Naively change words into integers by using bit minupulation.
• Organize the words in 26 categories. (has “a”, has “b”, …)
• For each puzzle, check the words in the category of puzzle[0]

The complexity for this one is hard to analysis. I though it may get TLE, actually, it can get…

LC 2056. Number of Valid Move Combinations On Chessboard

This is a 4th hard problem of the LC biweekly 64 contest problem. As 1 <= n <= 4, we can solve it by brute force and process those four cases one by one.

Key ideas:

• n = 1: return all possible moves
• …

About using Bit mask as visited or seen in BFS/DFS

For BFS/DFS problems, we usually need to maintain a seen or visited variable to make sure that we do not visit the visited node again (to get rid of TLE). Usually, we can use a set(unorder set in c++ and set in python) or array to maintain the visited status…

We know that for Single Source Shortest Path(SSSP) problem, we can

• solve it by using BFS if no weights or equal weights or equal weights during each exploration.
• solve by using Dijkstra if the graph has positive unequal weights.

For the problem in this article, we can use modified BFS…

Blabla before diving into the question

Less is more. One of the very simple, however, very elegant idea in CS is two pointers. We can tread two layer for loop as two pointer problem. We can think the binary search as three pointers. The in place quick sort and quick select is using the two pointers…