By Long Luo

This article is the solution Greedy: Let the Heaviest Match the Lightest, if Not Matched, Let it Alone of Problem 881. boats to save people.

Intuition

We should let the Heaviest person match the Lightest person and create the most pairs whose weight didn’t exceed the limit, and so on.

If not, let the Heavy person occupy a whole boat.

I write the Brute Force code first.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

public int numRescueBoats(int[] people, int limit) {
    int len = people.length;
    Arrays.sort(people);
    int ans = 0;
    int idx = 0;
    int right = len - 1;
    while (idx < len) {
        while (idx < len && people[idx] == 0) {
            idx++;
        }

        while (right > idx && people[right] > 0 && people[idx] + people[right] > limit) {
            right--;
        }

        if (right > idx && people[idx] + people[right] <= limit) {
            people[idx] = 0;
            people[right] = 0;
            idx++;
            right--;
            ans++;
        } else if (idx < len) {
            people[idx] = 0;
            idx++;
            ans++;
        }
    }

    return ans;
}

It was ugly, then I wrote such code below.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

 public int numRescueBoats(int[] people, int limit) {
     int len = people.length;
     Arrays.sort(people);
     int left = 0;
     int right = len - 1;
     int ans = 0;
     while (left <= right) {
         if (people[left] + people[right] <= limit) {
             left++;
	right--;
	ans++;
         } else {
	right--;
	ans++;
}
     } 

     return ans;
 }

Analysis

• Time Complexity: \(O(n \log n)\)
• Space Complexity: \(O(\log n)\)

All suggestions are welcome. If you have any query or suggestion please comment below. Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗

By Long Luo

This article is the solution Greedy: Reverse Thinking with Binary Algorithm of Problem 991. Broken Calculator.

Intuition

1. If \(\textit{startValue} \gt \textit{target}\), so return \(\textit{startValue} \gt \textit{target}\);
2. Considering such cases: \(2 \to 3\), \(2 \to 5\), \(1 \to 128\), \(1 \to 100\);
3. \(\textit{startValue} = \textit{startValue} \times 2^i\), when \(\textit{startValue}\) grows bigger, the last \(\textit{startValue}\) is closer to \(\textit{target} / 2\) that we only need double \(\textit{startValue}\) once.

So think reversly:

1. if target is even, the minimum operand is convert \(startValue\) equal to \(\textit{target} / 2 + 1\);
2. if target is odd, the minimum operand is convert \(startValue\) equal to \((\textit{target} + 1) / 2 + 2\).

Let’s coding.

By Long Luo

This article is the solution Greedy O(n) Solution with Image Explanation of Problem 1663. Smallest String With A Given Numeric Value .

Greedy

As we want to minimize the lexicographical order of the constructed string, let’s start from the beginning of the string, select the smallest letter that satisfies the requirements each time, then we get the final answer.

Suppose we are currently constructed to a certain position, as the picture below shows.

Including this position, there are still \(n_{rest}\) left to fill in, the remaining sum of these rest positions is \(k_{rest}\).

If we put a letter \(\textit{ch}\), and so the remaining \(n_{rest} - 1\) positions with the sum is \(k_{rest}\) must satisfy:

\[ 1 \times (n_{rest}-1) \leq k_{rest}-ch \leq 26 \times (n_{rest}-1) \]

can be:

\[ k_{rest}-26 \times (n_{rest}-1 ) \leq ch \leq k_{rest}-1 \times (n_{rest}-1) \]

So \(\textit{ch}\)

1. \(k_{rest} - 26 \times (n_{rest}-1) \leq 0\), we choose the character \(a\);
2. \(k_{rest} - 26 \times (n_{rest}-1) \gt 0\), we choose the character corresponding to this value.

Let’s write the code:

By Long Luo

This article is the solution Greedy Solution with Easy Detailed Explanation of Problem 763. Partition Labels .

Greedy

If we want to partition, we must maintain Two Pointers at the beginning and the end of a section. The Next Partition will start at the end of last Partition.

While scanning the string, if all the characters in the Partition only appear in the Partition, we can Partition it.

As the picture below shows, the farthest position of all the chars is no more than \(8\), so we can partition it.

and so on.

By Long Luo

This article is the solution HashMap Solution with Detailed Explanation of Problem 895. Maximum Frequency Stack.

Intuition

Let’s look at the problem description first.

1. \(\texttt{FreqStack()}\) constructs an empty frequency stack.
2. void \(\texttt{push(int val)}\) pushes an integer val onto the top of the stack.
3. int \(\texttt{pop()}\) removes and returns the most frequent element in the stack.
4. If there is a tie for the most frequent element, the element closest to the stack’s top is removed and returned.

The requirements of the problems can be listed in 3 rules:

1. Pop the stack by the max frequency;
2. Among all the elements with the same (maximum) frequency, pop the element closest to the stack’s top.

To simplify the problem, let’s just ignore rule 2 for now, it looks easier.

Step 1

We care more about the frequency of the elements. We can use \(\texttt{HashMap}\) to record the frequency of each element.

Additionally, we also care about max Frequency, the current maximum frequency of any element in the stack. we use the \(\textit{maxFreq}\) to store the maximum frequency.

The code is as follows.