Press "Enter" to skip to content

Huahua's Tech Road

花花酱 LeetCode 1894. Find the Student that Will Replace the Chalk

By zxi on August 9, 2021

There are n students in a class numbered from 0 to n - 1. The teacher will give each student a problem starting with the student number 0, then the student number 1, and so on until the teacher reaches the student number n - 1. After that, the teacher will restart the process, starting with the student number 0 again.

You are given a 0-indexed integer array chalk and an integer k. There are initially k pieces of chalk. When the student number i is given a problem to solve, they will use chalk[i] pieces of chalk to solve that problem. However, if the current number of chalk pieces is strictly less than chalk[i], then the student number i will be asked to replace the chalk.

Return the index of the student that will replace the chalk.

Example 1:

Input: chalk = [5,1,5], k = 22
Output: 0
Explanation: The students go in turns as follows:
- Student number 0 uses 5 chalk, so k = 17.
- Student number 1 uses 1 chalk, so k = 16.
- Student number 2 uses 5 chalk, so k = 11.
- Student number 0 uses 5 chalk, so k = 6.
- Student number 1 uses 1 chalk, so k = 5.
- Student number 2 uses 5 chalk, so k = 0.
Student number 0 does not have enough chalk, so they will have to replace it.

Example 2:

Input: chalk = [3,4,1,2], k = 25
Output: 1
Explanation: The students go in turns as follows:
- Student number 0 uses 3 chalk so k = 22.
- Student number 1 uses 4 chalk so k = 18.
- Student number 2 uses 1 chalk so k = 17.
- Student number 3 uses 2 chalk so k = 15.
- Student number 0 uses 3 chalk so k = 12.
- Student number 1 uses 4 chalk so k = 8.
- Student number 2 uses 1 chalk so k = 7.
- Student number 3 uses 2 chalk so k = 5.
- Student number 0 uses 3 chalk so k = 2.
Student number 1 does not have enough chalk, so they will have to replace it.

Constraints:

  • chalk.length == n
  • 1 <= n <= 105
  • 1 <= chalk[i] <= 105
  • 1 <= k <= 109

Solution: Math

Sum up all the students. k %= sum to skip all the middle rounds.

Time complexity: O(n)
Space complexity: O(1)

C++

花花酱 LeetCode 1893. Check if All the Integers in a Range Are Covered

By zxi on August 9, 2021

You are given a 2D integer array ranges and two integers left and right. Each ranges[i] = [starti, endi] represents an inclusive interval between starti and endi.

Return true if each integer in the inclusive range [left, right] is covered by at least one interval in ranges. Return false otherwise.

An integer x is covered by an interval ranges[i] = [starti, endi] if starti <= x <= endi.

Example 1:

Input: ranges = [[1,2],[3,4],[5,6]], left = 2, right = 5
Output: true
Explanation: Every integer between 2 and 5 is covered:
- 2 is covered by the first range.
- 3 and 4 are covered by the second range.
- 5 is covered by the third range.

Example 2:

Input: ranges = [[1,10],[10,20]], left = 21, right = 21
Output: false
Explanation: 21 is not covered by any range.

Constraints:

  • 1 <= ranges.length <= 50
  • 1 <= starti <= endi <= 50
  • 1 <= left <= right <= 50

Solution 1: Hashtable

Time complexity: O(n * (right – left))
Space complexity: O(right – left)

C++

花花酱 LeetCode 1889. Minimum Space Wasted From Packaging

By zxi on August 9, 2021

You have n packages that you are trying to place in boxes, one package in each box. There are m suppliers that each produce boxes of different sizes (with infinite supply). A package can be placed in a box if the size of the package is less than or equal to the size of the box.

The package sizes are given as an integer array packages, where packages[i] is the size of the ith package. The suppliers are given as a 2D integer array boxes, where boxes[j] is an array of box sizes that the jth supplier produces.

You want to choose a single supplier and use boxes from them such that the total wasted space is minimized. For each package in a box, we define the space wasted to be size of the box - size of the package. The total wasted space is the sum of the space wasted in all the boxes.

  • For example, if you have to fit packages with sizes [2,3,5] and the supplier offers boxes of sizes [4,8], you can fit the packages of size-2 and size-3 into two boxes of size-4 and the package with size-5 into a box of size-8. This would result in a waste of (4-2) + (4-3) + (8-5) = 6.

Return the minimum total wasted space by choosing the box supplier optimally, or -1 if it is impossible to fit all the packages inside boxes. Since the answer may be large, return it modulo 109 + 7.

Example 1:

Input: packages = [2,3,5], boxes = [[4,8],[2,8]]
Output: 6
Explanation: It is optimal to choose the first supplier, using two size-4 boxes and one size-8 box.
The total waste is (4-2) + (4-3) + (8-5) = 6.

Example 2:

Input: packages = [2,3,5], boxes = [[1,4],[2,3],[3,4]]
Output: -1
Explanation: There is no box that the package of size 5 can fit in.

Example 3:

Input: packages = [3,5,8,10,11,12], boxes = [[12],[11,9],[10,5,14]]
Output: 9
Explanation: It is optimal to choose the third supplier, using two size-5 boxes, two size-10 boxes, and two size-14 boxes.
The total waste is (5-3) + (5-5) + (10-8) + (10-10) + (14-11) + (14-12) = 9.

Constraints:

  • n == packages.length
  • m == boxes.length
  • 1 <= n <= 105
  • 1 <= m <= 105
  • 1 <= packages[i] <= 105
  • 1 <= boxes[j].length <= 105
  • 1 <= boxes[j][k] <= 105
  • sum(boxes[j].length) <= 105
  • The elements in boxes[j] are distinct.

Solution: Greedy + Binary Search

  1. sort packages and boxes
  2. for each box find all (unpacked) packages that are smaller or equal to itself.

Time complexity: O(nlogn) + O(mlogm) + O(mlogn)
Space complexity: O(1)

C++

花花酱 LeetCode 1888. Minimum Number of Flips to Make the Binary String Alternating

By zxi on August 9, 2021

You are given a binary string s. You are allowed to perform two types of operations on the string in any sequence:

  • Type-1: Remove the character at the start of the string s and append it to the end of the string.
  • Type-2: Pick any character in s and flip its value, i.e., if its value is '0' it becomes '1' and vice-versa.

Return the minimum number of type-2 operations you need to perform such that s becomes alternating.

The string is called alternating if no two adjacent characters are equal.

  • For example, the strings "010" and "1010" are alternating, while the string "0100" is not.

Example 1:

Input: s = "111000"
Output: 2
Explanation: Use the first operation two times to make s = "100011".
Then, use the second operation on the third and sixth elements to make s = "101010".

Example 2:

Input: s = "010"
Output: 0
Explanation: The string is already alternating.

Example 3:

Input: s = "1110"
Output: 1
Explanation: Use the second operation on the second element to make s = "1010".

Constraints:

  • 1 <= s.length <= 105
  • s[i] is either '0' or '1'.

Solution: Sliding Window

Trying all possible rotations will take O(n2) that leads to TLE, we have to do better.

concatenate the s to itself, then using a sliding window length of n to check how many count needed to make the string in the window alternating which will cover all possible rotations. We can update the count in O(1) when moving to the next window.

Time complexity: O(n)
Space complexity: O(1)

C++

// Author: Huahua
class Solution {
public:
  int minFlips(string s) {
    const int n = s.length();    
    int ans = INT_MAX;
    for (int i = 0, c0 = 0, c1 = 1, a0 = 0, a1 = 0; i < 2 * n; ++i, c0 ^= 1, c1 ^= 1) {
      if (s[i % n] - '0' != c0) ++a0;
      if (s[i % n] - '0' != c1) ++a1;
      if (i < n - 1) continue;
      if (i >= n) {
        if (s[i - n] - '0' != c0 ^ (n & 1)) --a0;
        if (s[i - n] - '0' != c1 ^ (n & 1)) --a1;
      }
      ans = min({ans, a0, a1});      
    }    
    return ans;
  }
};

花花酱 LeetCode 1887. Reduction Operations to Make the Array Elements Equal

By zxi on August 8, 2021

Given an integer array nums, your goal is to make all elements in nums equal. To complete one operation, follow these steps:

  1. Find the largest value in nums. Let its index be i (0-indexed) and its value be largest. If there are multiple elements with the largest value, pick the smallest i.
  2. Find the next largest value in nums strictly smaller than largest. Let its value be nextLargest.
  3. Reduce nums[i] to nextLargest.

Return the number of operations to make all elements in nums equal.

Example 1:

Input: nums = [5,1,3]
Output: 3
Explanation: It takes 3 operations to make all elements in nums equal:
1. largest = 5 at index 0. nextLargest = 3. Reduce nums[0] to 3. nums = [3,1,3].
2. largest = 3 at index 0. nextLargest = 1. Reduce nums[0] to 1. nums = [1,1,3].
3. largest = 3 at index 2. nextLargest = 1. Reduce nums[2] to 1. nums = [1,1,1].

Example 2:

Input: nums = [1,1,1]
Output: 0
Explanation: All elements in nums are already equal.

Example 3:

Input: nums = [1,1,2,2,3]
Output: 4
Explanation: It takes 4 operations to make all elements in nums equal:
1. largest = 3 at index 4. nextLargest = 2. Reduce nums[4] to 2. nums = [1,1,2,2,2].
2. largest = 2 at index 2. nextLargest = 1. Reduce nums[2] to 1. nums = [1,1,1,2,2].
3. largest = 2 at index 3. nextLargest = 1. Reduce nums[3] to 1. nums = [1,1,1,1,2].
4. largest = 2 at index 4. nextLargest = 1. Reduce nums[4] to 1. nums = [1,1,1,1,1].

Constraints:

  • 1 <= nums.length <= 5 * 104
  • 1 <= nums[i] <= 5 * 104

Solution: Math

Input: [5,4,3,2,1]
[5,4,3,2,1] -> [4,4,3,2,1] 5->4, 1 op
[4,4,3,2,1] -> [3,3,3,2,1] 4->3, 2 ops
[3,3,3,2,1] -> [2,2,2,2,1] 3->2, 3 ops
[2,2,2,2,1] -> [1,1,1,1,1] 2->1, 4 ops
total = 1 + 2 + 3 + 4 = 10

Sort the array in reverse order, if we find a number at index i that is is smaller than the previous number, we need i ops to make all the numbers before it to become itself.

Time complexity: O(nlogn)
Space complexity: O(1)

C++