Press "Enter" to skip to content

Posts tagged as “subarray”

花花酱 LeetCode 2110. Number of Smooth Descent Periods of a Stock

You are given an integer array prices representing the daily price history of a stock, where prices[i] is the stock price on the ith day.

smooth descent period of a stock consists of one or more contiguous days such that the price on each day is lower than the price on the preceding day by exactly 1. The first day of the period is exempted from this rule.

Return the number of smooth descent periods.

Example 1:

Input: prices = [3,2,1,4]
Output: 7
Explanation: There are 7 smooth descent periods:
[3], [2], [1], [4], [3,2], [2,1], and [3,2,1]
Note that a period with one day is a smooth descent period by the definition.

Example 2:

Input: prices = [8,6,7,7]
Output: 4
Explanation: There are 4 smooth descent periods: [8], [6], [7], and [7]
Note that [8,6] is not a smooth descent period as 8 - 6 ≠ 1.

Example 3:

Input: prices = [1]
Output: 1
Explanation: There is 1 smooth descent period: [1]

Constraints:

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

Solution: DP

Same as longest decreasing subarray.

dp[i] := length of longest smoothing subarray ends with nums[i].

dp[i] = dp[i – 1] + 1 if nums[i] + 1 = nums[i – 1] else 1

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

C++

花花酱 LeetCode 2104. Sum of Subarray Ranges

Problem

Solution 0: Brute force [TLE]

Enumerate all subarrays, for each one, find min and max.

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

Solution 1: Prefix min/max

We can use prefix technique to extend the array while keep tracking the min/max of the subarray.

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

C++

Solution 2: Monotonic stack

This problem can be reduced to 花花酱 LeetCode 907. Sum of Subarray Minimums

Just need to run twice one for sum of mins and another for sum of maxs.

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

C++

花花酱 LeetCode 76. Minimum Window Substring

Given two strings s and t of lengths m and n respectively, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string "".

The testcases will be generated such that the answer is unique.

substring is a contiguous sequence of characters within the string.

Example 1:

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.

Example 2:

Input: s = "a", t = "a"
Output: "a"
Explanation: The entire string s is the minimum window.

Example 3:

Input: s = "a", t = "aa"
Output: ""
Explanation: Both 'a's from t must be included in the window.
Since the largest window of s only has one 'a', return empty string.

Constraints:

  • m == s.length
  • n == t.length
  • 1 <= m, n <= 105
  • s and t consist of uppercase and lowercase English letters.

Follow up: Could you find an algorithm that runs in O(m + n) time?

Solution: Hashtable + Two Pointers

Use a hashtable to store the freq of characters we need to match for t.

Use (i, j) to track a subarray that contains all the chars in t.

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

C++

花花酱 LeetCode 152. Maximum Product Subarray

Given an integer array nums, find a contiguous non-empty subarray within the array that has the largest product, and return the product.

It is guaranteed that the answer will fit in a 32-bit integer.

subarray is a contiguous subsequence of the array.

Example 1:

Input: nums = [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.

Example 2:

Input: nums = [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.

Constraints:

  • 1 <= nums.length <= 2 * 104
  • -10 <= nums[i] <= 10
  • The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

Solution: Track high and low

Compute the low / high of prefix product, reset if nums[i] is higher than high or lower than low.

Swap low and high if nums[i] is a negative number.

e.g. [2, 3, -1, 8, -2]
nums[i] = 2, low = 2, high = 2
nums[i] = 3, low = 3, high = 2 * 3 = 6
nums[i] = -1, low = 6 * -1 = -6, high = -1
nums[i] = 8, low = -6 * 8 = -48, high = 8
nums[i] = -2, low = 8*-2 = -16, high = -48 * -2 = 96

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

C++

花花酱 LeetCode 2009. Minimum Number of Operations to Make Array Continuous

You are given an integer array nums. In one operation, you can replace any element in nums with any integer.

nums is considered continuous if both of the following conditions are fulfilled:

  • All elements in nums are unique.
  • The difference between the maximum element and the minimum element in nums equals nums.length - 1.

For example, nums = [4, 2, 5, 3] is continuous, but nums = [1, 2, 3, 5, 6] is not continuous.

Return the minimum number of operations to make numscontinuous.

Example 1:

Input: nums = [4,2,5,3]
Output: 0
Explanation: nums is already continuous.

Example 2:

Input: nums = [1,2,3,5,6]
Output: 1
Explanation: One possible solution is to change the last element to 4.
The resulting array is [1,2,3,5,4], which is continuous.

Example 3:

Input: nums = [1,10,100,1000]
Output: 3
Explanation: One possible solution is to:
- Change the second element to 2.
- Change the third element to 3.
- Change the fourth element to 4.
The resulting array is [1,2,3,4], which is continuous.

Constraints:

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

Solution: Sliding Window

Remove duplicates and sort the numbers.
Try using nums[i] as the min number of the final array.
window [i, j), max – min < n, then change the rest of array to fit into or append after the window, which takes n – (j – i) steps.
e.g. input = [10, 3, 1, 4, 5, 6, 6, 6, 11, 15] => sorted + unique => [1, 3, 4, 5, 6, 10, 11, 15]
n = 10, window = [3, 4, 5, 6, 10, 11], max = 11, min = 3, max – min = 8 < 10
Final array = [3, 4, 5, 6, 1->7, 62->8, 63->9, 10, 11, 15->12]
Time complexity: O(n)
Space complexity: O(1)

C++