Press "Enter" to skip to content

Posts tagged as “medium”

花花酱 LeetCode 2181. Merge Nodes in Between Zeros

By zxi on March 2, 2022

You are given the head of a linked list, which contains a series of integers separated by 0‘s. The beginning and end of the linked list will have Node.val == 0.

For every two consecutive 0‘s, merge all the nodes lying in between them into a single node whose value is the sum of all the merged nodes. The modified list should not contain any 0‘s.

Return the head of the modified linked list.

Example 1:

Input: head = [0,3,1,0,4,5,2,0]
Output: [4,11]
Explanation: 
The above figure represents the given linked list. The modified list contains
- The sum of the nodes marked in green: 3 + 1 = 4.
- The sum of the nodes marked in red: 4 + 5 + 2 = 11.

Example 2:

Input: head = [0,1,0,3,0,2,2,0]
Output: [1,3,4]
Explanation: 
The above figure represents the given linked list. The modified list contains
- The sum of the nodes marked in green: 1 = 1.
- The sum of the nodes marked in red: 3 = 3.
- The sum of the nodes marked in yellow: 2 + 2 = 4.

Constraints:

  • The number of nodes in the list is in the range [3, 2 * 105].
  • 0 <= Node.val <= 1000
  • There are no two consecutive nodes with Node.val == 0.
  • The beginning and end of the linked list have Node.val == 0.

Solution: List

Skip the first zero, replace every zero node with the sum of values of its previous nodes.

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

C++

花花酱 LeetCode 2187. Minimum Time to Complete Trips

By zxi on February 27, 2022

You are given an array time where time[i] denotes the time taken by the ith bus to complete one trip.

Each bus can make multiple trips successively; that is, the next trip can start immediately after completing the current trip. Also, each bus operates independently; that is, the trips of one bus do not influence the trips of any other bus.

You are also given an integer totalTrips, which denotes the number of trips all buses should make in total. Return the minimum time required for all buses to complete at least totalTrips trips.

Example 1:

Input: time = [1,2,3], totalTrips = 5
Output: 3
Explanation:
- At time t = 1, the number of trips completed by each bus are [1,0,0]. 
  The total number of trips completed is 1 + 0 + 0 = 1.
- At time t = 2, the number of trips completed by each bus are [2,1,0]. 
  The total number of trips completed is 2 + 1 + 0 = 3.
- At time t = 3, the number of trips completed by each bus are [3,1,1]. 
  The total number of trips completed is 3 + 1 + 1 = 5.
So the minimum time needed for all buses to complete at least 5 trips is 3.

Example 2:

Input: time = [2], totalTrips = 1
Output: 2
Explanation:
There is only one bus, and it will complete its first trip at t = 2.
So the minimum time needed to complete 1 trip is 2.

Constraints:

  • 1 <= time.length <= 105
  • 1 <= time[i], totalTrips <= 107

Solution: Binary Search

Find the smallest t s.t. trips >= totalTrips.

Time complexity: O(nlogm), where m ~= 1e15
Space complexity: O(1)

C++

花花酱 LeetCode 2170. Minimum Operations to Make the Array Alternating

By zxi on February 13, 2022

You are given a 0-indexed array nums consisting of n positive integers.

The array nums is called alternating if:

  • nums[i - 2] == nums[i], where 2 <= i <= n - 1.
  • nums[i - 1] != nums[i], where 1 <= i <= n - 1.

In one operation, you can choose an index i and change nums[i] into any positive integer.

Return the minimum number of operations required to make the array alternating.

Example 1:

Input: nums = [3,1,3,2,4,3]
Output: 3
Explanation:
One way to make the array alternating is by converting it to [3,1,3,1,3,1].
The number of operations required in this case is 3.
It can be proven that it is not possible to make the array alternating in less than 3 operations.

Example 2:

Input: nums = [1,2,2,2,2]
Output: 2
Explanation:
One way to make the array alternating is by converting it to [1,2,1,2,1].
The number of operations required in this case is 2.
Note that the array cannot be converted to [2,2,2,2,2] because in this case nums[0] == nums[1] which violates the conditions of an alternating array.

Constraints:

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 105

Solution: Greedy

Count and sort the frequency of numbers at odd and even positions.

Case 1: top frequency numbers are different, change the rest of numbers to them respectively.
Case 2: top frequency numbers are the same, compare top 1 odd + top 2 even vs top 2 even + top 1 odd.

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

C++

花花酱 LeetCode 2156. Find Substring With Given Hash Value

By zxi on February 5, 2022

The hash of a 0-indexed string s of length k, given integers p and m, is computed using the following function:

  • hash(s, p, m) = (val(s[0]) * p0 + val(s[1]) * p1 + ... + val(s[k-1]) * pk-1) mod m.

Where val(s[i]) represents the index of s[i] in the alphabet from val('a') = 1 to val('z') = 26.

You are given a string s and the integers power, modulo, k, and hashValue. Return sub, the first substring of s of length k such that hash(sub, power, modulo) == hashValue.

The test cases will be generated such that an answer always exists.

A substring is a contiguous non-empty sequence of characters within a string.

Example 1:

Input: s = "leetcode", power = 7, modulo = 20, k = 2, hashValue = 0
Output: "ee"
Explanation: The hash of "ee" can be computed to be hash("ee", 7, 20) = (5 * 1 + 5 * 7) mod 20 = 40 mod 20 = 0. 
"ee" is the first substring of length 2 with hashValue 0. Hence, we return "ee".

Example 2:

Input: s = "fbxzaad", power = 31, modulo = 100, k = 3, hashValue = 32
Output: "fbx"
Explanation: The hash of "fbx" can be computed to be hash("fbx", 31, 100) = (6 * 1 + 2 * 31 + 24 * 312) mod 100 = 23132 mod 100 = 32. 
The hash of "bxz" can be computed to be hash("bxz", 31, 100) = (2 * 1 + 24 * 31 + 26 * 312) mod 100 = 25732 mod 100 = 32. 
"fbx" is the first substring of length 3 with hashValue 32. Hence, we return "fbx".
Note that "bxz" also has a hash of 32 but it appears later than "fbx".

Constraints:

  • 1 <= k <= s.length <= 2 * 104
  • 1 <= power, modulo <= 109
  • 0 <= hashValue < modulo
  • s consists of lowercase English letters only.
  • The test cases are generated such that an answer always exists.

Solution: Sliding window

hash = (((hash – (s[i+k] * pk-1) % mod + mod) * p) + (s[i] * p0)) % mod

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

C++

花花酱 LeetCode 2155. All Divisions With the Highest Score of a Binary Array

By zxi on February 4, 2022

You are given a 0-indexed binary array nums of length n. nums can be divided at index i (where 0 <= i <= n) into two arrays (possibly empty) numsleft and numsright:

  • numsleft has all the elements of nums between index 0 and i - 1 (inclusive), while numsright has all the elements of nums between index i and n - 1 (inclusive).
  • If i == 0, numsleft is empty, while numsright has all the elements of nums.
  • If i == n, numsleft has all the elements of nums, while numsright is empty.

The division score of an index i is the sum of the number of 0‘s in numsleft and the number of 1‘s in numsright.

Return all distinct indices that have the highest possible division score. You may return the answer in any order.

Example 1:

Input: nums = [0,0,1,0]
Output: [2,4]
Explanation: Division at index
- 0: numsleft is []. numsright is [0,0,1,0]. The score is 0 + 1 = 1.
- 1: numsleft is [0]. numsright is [0,1,0]. The score is 1 + 1 = 2.
- 2: numsleft is [0,0]. numsright is [1,0]. The score is 2 + 1 = 3.
- 3: numsleft is [0,0,1]. numsright is [0]. The score is 2 + 0 = 2.
- 4: numsleft is [0,0,1,0]. numsright is []. The score is 3 + 0 = 3.
Indices 2 and 4 both have the highest possible division score 3.
Note the answer [4,2] would also be accepted.

Example 2:

Input: nums = [0,0,0]
Output: [3]
Explanation: Division at index
- 0: numsleft is []. numsright is [0,0,0]. The score is 0 + 0 = 0.
- 1: numsleft is [0]. numsright is [0,0]. The score is 1 + 0 = 1.
- 2: numsleft is [0,0]. numsright is [0]. The score is 2 + 0 = 2.
- 3: numsleft is [0,0,0]. numsright is []. The score is 3 + 0 = 3.
Only index 3 has the highest possible division score 3.

Example 3:

Input: nums = [1,1]
Output: [0]
Explanation: Division at index
- 0: numsleft is []. numsright is [1,1]. The score is 0 + 2 = 2.
- 1: numsleft is [1]. numsright is [1]. The score is 0 + 1 = 1.
- 2: numsleft is [1,1]. numsright is []. The score is 0 + 0 = 0.
Only index 0 has the highest possible division score 2.

Constraints:

  • n == nums.length
  • 1 <= n <= 105
  • nums[i] is either 0 or 1.

Solution: Precompute + Prefix Sum

Count how many ones in the array, track the prefix sum to compute score for each index in O(1).

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

C++