Press "Enter" to skip to content

Posts tagged as “counting”

花花酱 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++

花花酱 LeetCode 1351. Count Negative Numbers in a Sorted Matrix

Given a m * n matrix grid which is sorted in non-increasing order both row-wise and column-wise. 

Return the number of negative numbers in grid.

Example 1:

Input: grid = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]
Output: 8
Explanation: There are 8 negatives number in the matrix.

Example 2:

Input: grid = [[3,2],[1,0]]
Output: 0

Example 3:

Input: grid = [[1,-1],[-1,-1]]
Output: 3

Example 4:

Input: grid = [[-1]]
Output: 1

Constraints:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 100
  • -100 <= grid[i][j] <= 100

Solution 1: Brute Force

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

C++

Solution 2: Find the frontier

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

C++

花花酱 LeetCode 1267. Count Servers that Communicate

You are given a map of a server center, represented as a m * n integer matrix grid, where 1 means that on that cell there is a server and 0 means that it is no server. Two servers are said to communicate if they are on the same row or on the same column.

Return the number of servers that communicate with any other server.

Example 1:

Input: grid = [[1,0],[0,1]]
Output: 0
Explanation: No servers can communicate with others.

Example 2:

Input: grid = [[1,0],[1,1]]
Output: 3
Explanation: All three servers can communicate with at least one other server.

Example 3:

Input: grid = [[1,1,0,0],[0,0,1,0],[0,0,1,0],[0,0,0,1]]
Output: 4
Explanation: The two servers in the first row can communicate with each other. The two servers in the third column can communicate with each other. The server at right bottom corner can't communicate with any other server.

Constraints:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m <= 250
  • 1 <= n <= 250
  • grid[i][j] == 0 or 1

Solution: Counting

Two passes:
First pass, count number of computers for each row and each column.
Second pass, count grid[i][j] if rows[i] or cols[j] has more than 1 computer.

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

C++