LeetCode Biweekly Contest 49

Detailed explanations for fast and clean solutions!

This has been my first online contest in LeetCode — and it was a blast!

LeetCode #1812 ; Determine Color of a Chessboard Square

We are given coordinates, a string that represents the coordinates of a square of the chessboard, and asked to returntrue if the square is white, and false if the square is black.

Solution

Let’s first convert the rows and columns to 0-based indexes so we can better refer to them.

White squares are alternating their position between two adjacent rows and columns.

If we pick an even column (e.g. column ‘a’, which is 0 in our 0-based indexing system), we see that its white squares are in even 0-based rows; a similar pattern arises for the odd columns (in which white squares appear in odd rows).

We, therefore, understand that when taking a white square row index and col index, the sum of their reminders from division in 2 — must be zero.

LeetCode #1813; Sentence Similarity III

A sentence is a list of words that are separated by a single space with no leading or trailing spaces. For example, "Hello World", "HELLO", "hello world hello world" are all sentences. Words consist of only uppercase and lowercase English letters.

Two sentences sentence1 and sentence2 are similar if it is possible to insert an arbitrary sentence (possibly empty) inside one of these sentences such that the two sentences become equal. For example, sentence1 = "Hello my name is Jane" and sentence2 = "Hello Jane" can be made equal by inserting "my name is" between "Hello" and "Jane" in sentence2.

Given two sentences sentence1 and sentence2, return true if sentence1 and sentence2 are similar. Otherwise, return false.

Example 1:

Input: sentence1 = "My name is Haley", sentence2 = "My Haley"
Output: true
Explanation: sentence2 can be turned to sentence1 by inserting "name is" between "My" and "Haley".

Example 2:

Input: sentence1 = "of", sentence2 = "A lot of words"
Output: false
Explanation: No single sentence can be inserted inside one of the sentences to make it equal to the other.

Example 3:

Input: sentence1 = "Eating right now", sentence2 = "Eating"
Output: true
Explanation: sentence2 can be turned to sentence1 by inserting "right now" at the end of the sentence.

Example 4:

Input: sentence1 = "Luky", sentence2 = "Lucccky"
Output: false

Solution

Let’s break it down:

1. If sentences are the same — they are similar
2. If sentences don't have a common prefix or don't have a common suffix — they are not similar
3. If either common prefix or common suffix equals one of the lengths of the sentences — then they are similar!
4. If they have common prefix and common suffix, and one of the sentances can be build by the common_prefix+common_suffix — then they are similiar!

LeetCode #1814; Count Nice Pairs in an Array

We are given an array nums that consists of non-negative integers. Let us define rev(x) as the reverse of the non-negative integer x. For example, rev(123) = 321, and rev(120) = 21. A pair of indices (i, j) is nice if it satisfies all of the following conditions:

• 0 <= i < j < nums.length
• nums[i] + rev(nums[j]) == nums[j] + rev(nums[i])

Return the number of nice pairs of indices. Since that number can be too large, return it modulo 109 + 7.

Example 1:

Input: nums = [42,11,1,97]
Output: 2
Explanation: The two pairs are:
 - (0,3) : 42 + rev(97) = 42 + 79 = 121, 97 + rev(42) = 97 + 24 = 121.
 - (1,2) : 11 + rev(1) = 11 + 1 = 12, 1 + rev(11) = 1 + 11 = 12.

Solution

Let’s have another look at what we are asked to do!

We are asked to find pairs of numbers n and m such as:

n+rev(m)==m+rev(n)

That’s can be phrased as:

m-rev(m)==n-rev(n)

That is, we can pair each number n with each number m that has the same m-rev(m) value.

The problem reduces to:

1. Count the number of occurrences of different values for m-rev(m).
2. Find the number of options to pair them (x choose 2)

LeetCode #1815; Maximum Number of Groups Getting Fresh Donuts

We are given two parameter

1. groups (int array) ; size of friends groups
2. batch_size (int); the amount of fresh donuts our machine is capable to make

The requirement;
When a group of friends arrives, they want that all of them will get fresh donuts that are made at the same day.
Our objective is to choose how to arrange the groups so that a maximal amount of them will be happy (and served with fresh donuts).

e.g.
groups = [1,2,3,4,5,6]
batch_size = 3
If we re-orgenized the groups as: [6,2,4,5,1,3].
That is:
(6),(2,4),(5,1),(3)

• The 1st group of 6 are served with fresh donuts because our machine can make batches of 3 — so we make two batches
• The second group will be happy two, as we make a batch of 3, which is more than the size of the group so they are all served with fresh donuts
• The third group will get 1 remaining donut so they won't be happy; when they arrive we make 3 donuts so we have a total of 4 donuts to serve them, and we get rid of the old donuts supply
• When the fourth group come we make fresh donuts for all of them, yet some donuts will remain
• When the fifth group comes we serve some of them old donuts and make the remaining amount of donuts to serve them and get rid of the old supply
• When the sixth group comes, of size 3, we make them all fresh donuts
  The happy groups are; 1st, 2nd, 4th, and 6th
  Total: 4 happy groups

Solution

This is indeed a hard problem, but it can be mitigated from a brute force solution.
The brute force approach will suffice, but the problem beauty is its mitigations.

Case 1:
If we have a group of batch_size multiplication size — they are the easiest for us — we can make them all fresh donuts (just like we have seen in the example above when we had batch_size=3 and a group of size 3 or 6).

Case 2:
This time let’s assume we have two groups;
One group eats donuts but leaves us with k donuts that must be consumed by the next group.
The first group is happy - they were all served with fresh donuts
The second group will not be happy because they will be served with the old donuts leftover from the previous group.
The best thing we can do is to have a second group with group_size%k == batch_size - k reminder.
The second group will not be happy, but they will consume all the leftovers of the first group.
When the next group arrives - we will make fresh new donuts for them, thanks to the second group that consumed all the previous leftovers.

Case 3; Brute-Force (Backtracking + Memoization)
We have now all the other groups not caught by cases 1 & 2, and we are asked to arrange them.
Let’s utilize a backtracking algorithm altogether with memization to prevent reoccurring computations;

• Base case: The sum of the leftovers (reminders) of the groups is zero — that means we can put all the groups on the same day and make the multiplication of batch_size for all of them.
• Let’s pick a single group and make donuts for them, and see how the amount of remining donuts changes. We, therefore, loop over all the options for group sizes reminders.
• The answer is:
  The best arrangement excluding the group we made donuts for, plus 1 if when we made them donuts and did not have old donuts to serve them.

If you reached till here — you really deserve a donut! :)

Enjoyed this article? Feel free to long-press the 👏 button below 😀