Press "Enter" to skip to content

Posts tagged as “hard”

花花酱 LeetCode 1453. Maximum Number of Darts Inside of a Circular Dartboard

You have a very large square wall and a circular dartboard placed on the wall. You have been challenged to throw darts into the board blindfolded. Darts thrown at the wall are represented as an array of points on a 2D plane. 

Return the maximum number of points that are within or lie on any circular dartboard of radius r.

Example 1:

Input: points = [[-2,0],[2,0],[0,2],[0,-2]], r = 2
Output: 4
Explanation: Circle dartboard with center in (0,0) and radius = 2 contain all points.

Example 2:

Input: points = [[-3,0],[3,0],[2,6],[5,4],[0,9],[7,8]], r = 5
Output: 5
Explanation: Circle dartboard with center in (0,4) and radius = 5 contain all points except the point (7,8).

Example 3:

Input: points = [[-2,0],[2,0],[0,2],[0,-2]], r = 1
Output: 1

Example 4:

Input: points = [[1,2],[3,5],[1,-1],[2,3],[4,1],[1,3]], r = 2
Output: 4

Constraints:

  • 1 <= points.length <= 100
  • points[i].length == 2
  • -10^4 <= points[i][0], points[i][1] <= 10^4
  • 1 <= r <= 5000

Solution 1: Angular Sweep

See for more details: https://www.geeksforgeeks.org/angular-sweep-maximum-points-can-enclosed-circle-given-radius/

Time complexity: O(n^2*logn)
Space complexity: O(n^2)

C++

花花酱 LeetCode 1444. Number of Ways of Cutting a Pizza

Given a rectangular pizza represented as a rows x cols matrix containing the following characters: 'A' (an apple) and '.' (empty cell) and given the integer k. You have to cut the pizza into k pieces using k-1 cuts. 

For each cut you choose the direction: vertical or horizontal, then you choose a cut position at the cell boundary and cut the pizza into two pieces. If you cut the pizza vertically, give the left part of the pizza to a person. If you cut the pizza horizontally, give the upper part of the pizza to a person. Give the last piece of pizza to the last person.

Return the number of ways of cutting the pizza such that each piece contains at least one apple. Since the answer can be a huge number, return this modulo 10^9 + 7.

Example 1:

Input: pizza = ["A..","AAA","..."], k = 3
Output: 3 
Explanation: The figure above shows the three ways to cut the pizza. Note that pieces must contain at least one apple.

Example 2:

Input: pizza = ["A..","AA.","..."], k = 3
Output: 1

Example 3:

Input: pizza = ["A..","A..","..."], k = 1
Output: 1

Constraints:

  • 1 <= rows, cols <= 50
  • rows == pizza.length
  • cols == pizza[i].length
  • 1 <= k <= 10
  • pizza consists of characters 'A' and '.' only.

Solution: DP

dp(n, m, k) := # of ways to cut pizza[n:N][m:M] with k cuts.

dp(n, m, k) = sum(hasApples(n, m, N – 1, y) * dp(y + 1, n, k – 1) for y in range(n, M)) + sum(hasApples(n, m, x, M – 1) * dp(m, x + 1, k – 1) for x in range(n, M))

Time complexity: O(M*N*(M+N)*K) = O(N^3 * K)
Space complexity: O(M*N*K)

C++

花花酱 LeetCode 1439. Find the Kth Smallest Sum of a Matrix With Sorted Rows

You are given an m * n matrix, mat, and an integer k, which has its rows sorted in non-decreasing order.

You are allowed to choose exactly 1 element from each row to form an array. Return the Kth smallest array sum among all possible arrays.

Example 1:

Input: mat = [[1,3,11],[2,4,6]], k = 5
Output: 7
Explanation: Choosing one element from each row, the first k smallest sum are:
[1,2], [1,4], [3,2], [3,4], [1,6]. Where the 5th sum is 7.  

Example 2:

Input: mat = [[1,3,11],[2,4,6]], k = 9
Output: 17

Example 3:

Input: mat = [[1,10,10],[1,4,5],[2,3,6]], k = 7
Output: 9
Explanation: Choosing one element from each row, the first k smallest sum are:
[1,1,2], [1,1,3], [1,4,2], [1,4,3], [1,1,6], [1,5,2], [1,5,3]. Where the 7th sum is 9.  

Example 4:

Input: mat = [[1,1,10],[2,2,9]], k = 7
Output: 12

Constraints:

  • m == mat.length
  • n == mat.length[i]
  • 1 <= m, n <= 40
  • 1 <= k <= min(200, n ^ m)
  • 1 <= mat[i][j] <= 5000
  • mat[i] is a non decreasing array.

Solution 1: Priority Queue

Generate the arrays in order.

Each node is {sum, idx_0, idx_1, …, idx_m},

Start with {sum_0, 0, 0, …, 0}.

For expansion, pick one row and increase its index

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

C++

花花酱 LeetCode 1434. Number of Ways to Wear Different Hats to Each Other

There are n people and 40 types of hats labeled from 1 to 40.

Given a list of list of integers hats, where hats[i] is a list of all hats preferred by the i-th person.

Return the number of ways that the n people wear different hats to each other.

Since the answer may be too large, return it modulo 10^9 + 7.

Example 1:

Input: hats = [[3,4],[4,5],[5]]
Output: 1
Explanation: There is only one way to choose hats given the conditions. 
First person choose hat 3, Second person choose hat 4 and last one hat 5.

Example 2:

Input: hats = [[3,5,1],[3,5]]
Output: 4
Explanation: There are 4 ways to choose hats
(3,5), (5,3), (1,3) and (1,5)

Example 3:

Input: hats = [[1,2,3,4],[1,2,3,4],[1,2,3,4],[1,2,3,4]]
Output: 24
Explanation: Each person can choose hats labeled from 1 to 4.
Number of Permutations of (1,2,3,4) = 24.

Example 4:

Input: hats = [[1,2,3],[2,3,5,6],[1,3,7,9],[1,8,9],[2,5,7]]
Output: 111

Constraints:

  • n == hats.length
  • 1 <= n <= 10
  • 1 <= hats[i].length <= 40
  • 1 <= hats[i][j] <= 40
  • hats[i] contains a list of unique integers.

Solution: DP

dp[i][j] := # of ways using first i hats, j is the bit mask of people wearing hats.

e.g. dp[3][101] == # of ways using first 3 hats that people 1 and 3 are wearing hats.

init dp[0][0] = 1

dp[i][mask | (1 << p)] = dp[i-1][mask | (1 << p)] + dp[i-1][mask], where people p prefers hats i.

ans: dp[nHat][1…1]

Time complexity: O(2^n * h * n)
Space complexity: O(2^n * h) -> O(2^n)

C++

O(2^n) memory

C++

花花酱 LeetCode 1425. Constrained Subset Sum

Given an integer array nums and an integer k, return the maximum sum of a non-empty subset of that array such that for every two consecutive integers in the subset, nums[i] and nums[j], where i < j, the condition j - i <= k is satisfied.

subset of an array is obtained by deleting some number of elements (can be zero) from the array, leaving the remaining elements in their original order.

Example 1:

Input: nums = [10,2,-10,5,20], k = 2
Output: 37
Explanation: The subset is [10, 2, 5, 20].

Example 2:

Input: nums = [-1,-2,-3], k = 1
Output: -1
Explanation: The subset must be non-empty, so we choose the largest number.

Example 3:

Input: nums = [10,-2,-10,-5,20], k = 2
Output: 23
Explanation: The subset is [10, -2, -5, 20].

Constraints:

  • 1 <= k <= nums.length <= 10^5
  • -10^4 <= nums[i] <= 10^4

Solution: DP / Sliding window / monotonic queue

dp[i] := max sum of a subset that include nums[i]
dp[i] := max(dp[i-1], dp[i-2], …, dp[i-k-1], 0) + nums[i]

C++

Use a monotonic queue to track the maximum of a sliding window dp[i-k-1] ~ dp[i-1].

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

C++