January 19, 2023

Subarray sums divisible by k

We are using the prefix sum and the remainder of the sum divided by k to solve this problem. The idea is that if the remainder of the sum of the subarray is the same, then the sum of the subarray is...

Read

January 18, 2023

Count the number of good subarray

We will use a sliding window to count the number of good subarray. Time complexity: O(n), n is the length of the array. Space complexity: O(n)

Read

January 17, 2023

Find the celebrity

First we need to find the celebraty candidate. We will take two pointers, left and right must meet at some point, this person is a potential celebrity. Next we need verify if the candidate is indeed...

Read

January 17, 2023

Flip string to monotone increasing

A string of '0's and '1's is monotone increasing if it consists of some number of '0's (possibly 0), followed by some number of '1's (also possibly...

Read

January 16, 2023

Percentage of letter in string

We will count the number of occurance of the letter in the string, and then calculate the percentage of the given letter. Time complexity: O(n), n is the length of the string. Space...

Read

January 16, 2023

Minimum moves to reach target score

We should use double action as late as possible, as many times as possible. We can use a greedy approach to solve this problem. Time complexity: O(log(n)), n is the target. Space...

Read

January 15, 2023

Find the index of the large integer

We will use binary search to find the index of the large integer. Time complexity: O(log(n)) Space complexity: O(1)

Read

January 15, 2023

Number of good paths

We will try to build the graph from nodes with the smallest value to the largest value. If we build the graph in this way, nodes in the graph will always be smaller than or equal to the value we are...

Read

January 15, 2023

Difference between element sum and digit sum of an array

We will calculate the sum of every digit in the array and subtract it from the sum of the array. Time complexity: O(n) Space complexity: O(n) We can achieve the same...

Read

January 14, 2023

Lexicographically smallest equivalent string

We will use basic union-find to find the equivalence classes. Then we will create a new string by iterating over the string A and replacing each character with the smallest character in...

Read