Problems
October 27, 2022
Count good numbers
There are 5 possibilities for even positions(0, 2, 4, 6, 8) and 4 for odd positions(2, 3, 5, 7). Therefore the answer for every n is 5^number of even places * 4^number of odd places. Time...
ReadOctober 27, 2022
XOR queries of a subarray
We will in-place calculate the prefix XOR of input array. For each query [i, j], if i == 0, query result = array[j], if i != 0, query result = array[i-1] ^ array[j]. Time complexity:...
ReadOctober 27, 2022
Predict the winner
We will take the maximum of the two possible choices for the current player. If the current player chooses the leftmost element, the next player will choose the maximum of the two possible choices...
ReadOctober 27, 2022
Image overlap
We will convert the two images into a list of coordinates. Then we will iterate over all possible shifts and count the number of overlapping coordinates. The maximum number of overlapping coordinates...
ReadOctober 26, 2022
Shortest bridge
We will first scan the grid to find the first island and mark it with 2 after exploring it with DFS. Then we will start a BFS from the first island and explore the grid to find the second island. We...
ReadOctober 26, 2022
Maximum number of pairs in array
We will count the frequency of each number in the array. Then we iterate the frequency map and count the number of pairs.
Time Complexity: O(n)
Space Complexity: O(n)
October 26, 2022
Groups of special equivalent strings
We will take each word, separate the even and odd characters, and sort them. Then we add them to a set. The size of the set is the number of groups.
Time Complexity: O(n*klog(k)), n...
October 26, 2022
Longest uploaded prefix
We will use a longest flag and a list to store all the videos. Since the prefix cannot decrease, it is enough for us to increase it until we reach the number that has not yet been added. We will...
ReadOctober 26, 2022
Minesweeper
We will run a DFS on the grid and return the number of mines adjacent to the cell if the cell is not a mine. Otherwise, we will return 'X' and mark the cell as visited. Time complexity: O(n^2)...
ReadOctober 26, 2022
Kth missing positive number
The first idea we can think of when we look at this problem is just to traverse elements 1, 2, 3, ... and find missing element with index k. To make it efficient, we create arr_set: set of all...
Read