Press "Enter" to skip to content

Posts tagged as “counting”

花花酱 LeetCode 1550. Three Consecutive Odds

Given an integer array arr, return true if there are three consecutive odd numbers in the array. Otherwise, return false.

Example 1:

Input: arr = [2,6,4,1]
Output: false
Explanation: There are no three consecutive odds.

Example 2:

Input: arr = [1,2,34,3,4,5,7,23,12]
Output: true
Explanation: [5,7,23] are three consecutive odds.

Constraints:

  • 1 <= arr.length <= 1000
  • 1 <= arr[i] <= 1000

Solution: Counting

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

C++

花花酱 LeetCode 1541. Minimum Insertions to Balance a Parentheses String

Given a parentheses string s containing only the characters '(' and ')'. A parentheses string is balanced if:

  • Any left parenthesis '(' must have a corresponding two consecutive right parenthesis '))'.
  • Left parenthesis '(' must go before the corresponding two consecutive right parenthesis '))'.

For example, "())""())(())))" and "(())())))" are balanced, ")()""()))" and "(()))" are not balanced.

You can insert the characters ‘(‘ and ‘)’ at any position of the string to balance it if needed.

Return the minimum number of insertions needed to make s balanced.

Example 1:

Input: s = "(()))"
Output: 1
Explanation: The second '(' has two matching '))', but the first '(' has only ')' matching. We need to to add one more ')' at the end of the string to be "(())))" which is balanced.

Example 2:

Input: s = "())"
Output: 0
Explanation: The string is already balanced.

Example 3:

Input: s = "))())("
Output: 3
Explanation: Add '(' to match the first '))', Add '))' to match the last '('.

Example 4:

Input: s = "(((((("
Output: 12
Explanation: Add 12 ')' to balance the string.

Example 5:

Input: s = ")))))))"
Output: 5
Explanation: Add 4 '(' at the beginning of the string and one ')' at the end. The string becomes "(((())))))))".

Constraints:

  • 1 <= s.length <= 10^5
  • s consists of '(' and ')' only.

Solution: Counting

Count how many close parentheses we need.

  1. if s[i] is ‘)’, we decrease the counter.
    1. if counter becomes negative, means we need to insert ‘(‘
      1. increase ans by 1, increase the counter by 2, we need one more ‘)’
      2. ‘)’ -> ‘()’
  2. if s[i] is ‘(‘
    1. if we have an odd counter, means there is a unbalanced ‘)’ e.g. ‘(()(‘, counter is 3
      1. need to insert ‘)’, decrease counter, increase ans
      2. ‘(()(‘ -> ‘(())(‘, counter = 2
    2. increase counter by 2, each ‘(‘ needs two ‘)’s. ‘(())(‘ -> counter = 4
  3. Once done, if counter is greater than zero, we need insert that much ‘)s’
    1. counter = 5, ‘((()’ -> ‘((())))))’

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

C++

花花酱 LeetCode 1420. Build Array Where You Can Find The Maximum Exactly K Comparisons

Given three integers nm and k. Consider the following algorithm to find the maximum element of an array of positive integers:

You should build the array arr which has the following properties:

  • arr has exactly n integers.
  • 1 <= arr[i] <= m where (0 <= i < n).
  • After applying the mentioned algorithm to arr, the value search_cost is equal to k.

Return the number of ways to build the array arr under the mentioned conditions. As the answer may grow large, the answer must be computed modulo 10^9 + 7.

Example 1:

Input: n = 2, m = 3, k = 1
Output: 6
Explanation: The possible arrays are [1, 1], [2, 1], [2, 2], [3, 1], [3, 2] [3, 3]

Example 2:

Input: n = 5, m = 2, k = 3
Output: 0
Explanation: There are no possible arrays that satisify the mentioned conditions.

Example 3:

Input: n = 9, m = 1, k = 1
Output: 1
Explanation: The only possible array is [1, 1, 1, 1, 1, 1, 1, 1, 1]

Example 4:

Input: n = 50, m = 100, k = 25
Output: 34549172
Explanation: Don't forget to compute the answer modulo 1000000007

Example 5:

Input: n = 37, m = 17, k = 7
Output: 418930126

Constraints:

  • 1 <= n <= 50
  • 1 <= m <= 100
  • 0 <= k <= n

Solution: DP

dp[n][m][k] := ways to build given n,m,k.

dp[n][m][k] = sum(dp[n-1][m][k] + dp[n-1][i-1][k-1] – dp[n-1][i-1][k]), 1 <= i <= m
dp[1][m][1] = m
dp[n][m][k] = 0 if k < 1 or k > m or k > n

Time complexity: O(n*m^2*k)
Space complexity: O(n*m*k)

C++

花花酱 LeetCode 1370. Increasing Decreasing String

Given a string s. You should re-order the string using the following algorithm:

  1. Pick the smallest character from s and append it to the result.
  2. Pick the smallest character from s which is greater than the last appended character to the result and append it.
  3. Repeat step 2 until you cannot pick more characters.
  4. Pick the largest character from s and append it to the result.
  5. Pick the largest character from s which is smaller than the last appended character to the result and append it.
  6. Repeat step 5 until you cannot pick more characters.
  7. Repeat the steps from 1 to 6 until you pick all characters from s.

In each step, If the smallest or the largest character appears more than once you can choose any occurrence and append it to the result.

Return the result string after sorting s with this algorithm.

Example 1:

Input: s = "aaaabbbbcccc"
Output: "abccbaabccba"
Explanation: After steps 1, 2 and 3 of the first iteration, result = "abc"
After steps 4, 5 and 6 of the first iteration, result = "abccba"
First iteration is done. Now s = "aabbcc" and we go back to step 1
After steps 1, 2 and 3 of the second iteration, result = "abccbaabc"
After steps 4, 5 and 6 of the second iteration, result = "abccbaabccba"

Example 2:

Input: s = "rat"
Output: "art"
Explanation: The word "rat" becomes "art" after re-ordering it with the mentioned algorithm.

Example 3:

Input: s = "leetcode"
Output: "cdelotee"

Example 4:

Input: s = "ggggggg"
Output: "ggggggg"

Example 5:

Input: s = "spo"
Output: "ops"

Constraints:

  • 1 <= s.length <= 500
  • s contains only lower-case English letters.

Solution: Counting frequency of each character

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

C++

Python3

花花酱 LeetCode 1365. How Many Numbers Are Smaller Than the Current Number

Given the array nums, for each nums[i] find out how many numbers in the array are smaller than it. That is, for each nums[i] you have to count the number of valid j's such that j != i and nums[j] < nums[i].

Return the answer in an array.

Example 1:

Input: nums = [8,1,2,2,3]
Output: [4,0,1,1,3]
Explanation: 
For nums[0]=8 there exist four smaller numbers than it (1, 2, 2 and 3). 
For nums[1]=1 does not exist any smaller number than it.
For nums[2]=2 there exist one smaller number than it (1). 
For nums[3]=2 there exist one smaller number than it (1). 
For nums[4]=3 there exist three smaller numbers than it (1, 2 and 2).

Example 2:

Input: nums = [6,5,4,8]
Output: [2,1,0,3]

Example 3:

Input: nums = [7,7,7,7]
Output: [0,0,0,0]

Constraints:

  • 2 <= nums.length <= 500
  • 0 <= nums[i] <= 100

Solution 1: Brute Force

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

C++

Solution 2: Sort + Binary Search

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

C++

Solution 3: Cumulative frequency

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

C++