Press "Enter" to skip to content

Posts published in “Search”

花花酱 LeetCode 1849. Splitting a String Into Descending Consecutive Values

You are given a string s that consists of only digits.

Check if we can split s into two or more non-empty substrings such that the numerical values of the substrings are in descending order and the difference between numerical values of every two adjacent substrings is equal to 1.

  • For example, the string s = "0090089" can be split into ["0090", "089"] with numerical values [90,89]. The values are in descending order and adjacent values differ by 1, so this way is valid.
  • Another example, the string s = "001" can be split into ["0", "01"]["00", "1"], or ["0", "0", "1"]. However all the ways are invalid because they have numerical values [0,1][0,1], and [0,0,1] respectively, all of which are not in descending order.

Return true if it is possible to split s​​​​​​ as described above, or false otherwise.

substring is a contiguous sequence of characters in a string.

Example 1:

Input: s = "1234"
Output: false
Explanation: There is no valid way to split s.

Example 2:

Input: s = "050043"
Output: true
Explanation: s can be split into ["05", "004", "3"] with numerical values [5,4,3].
The values are in descending order with adjacent values differing by 1.

Example 3:

Input: s = "9080701"
Output: false
Explanation: There is no valid way to split s.

Example 4:

Input: s = "10009998"
Output: true
Explanation: s can be split into ["100", "099", "98"] with numerical values [100,99,98].
The values are in descending order with adjacent values differing by 1.

Constraints:

  • 1 <= s.length <= 20
  • s only consists of digits.

Solution: DFS

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

C++

花花酱 LeetCode 1766. Tree of Coprimes

There is a tree (i.e., a connected, undirected graph that has no cycles) consisting of n nodes numbered from 0 to n - 1 and exactly n - 1 edges. Each node has a value associated with it, and the root of the tree is node 0.

To represent this tree, you are given an integer array nums and a 2D array edges. Each nums[i] represents the ith node’s value, and each edges[j] = [uj, vj] represents an edge between nodes uj and vj in the tree.

Two values x and y are coprime if gcd(x, y) == 1 where gcd(x, y) is the greatest common divisor of x and y.

An ancestor of a node i is any other node on the shortest path from node i to the root. A node is not considered an ancestor of itself.

Return an array ans of size nwhere ans[i] is the closest ancestor to node i such that nums[i] and nums[ans[i]] are coprime, or -1 if there is no such ancestor.

Example 1:

Input: nums = [2,3,3,2], edges = [[0,1],[1,2],[1,3]]
Output: [-1,0,0,1]
Explanation: In the above figure, each node's value is in parentheses.
- Node 0 has no coprime ancestors.
- Node 1 has only one ancestor, node 0. Their values are coprime (gcd(2,3) == 1).
- Node 2 has two ancestors, nodes 1 and 0. Node 1's value is not coprime (gcd(3,3) == 3), but node 0's
  value is (gcd(2,3) == 1), so node 0 is the closest valid ancestor.
- Node 3 has two ancestors, nodes 1 and 0. It is coprime with node 1 (gcd(3,2) == 1), so node 1 is its
  closest valid ancestor.

Example 2:

Input: nums = [5,6,10,2,3,6,15], edges = [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6]]
Output: [-1,0,-1,0,0,0,-1]

Constraints:

  • nums.length == n
  • 1 <= nums[i] <= 50
  • 1 <= n <= 105
  • edges.length == n - 1
  • edges[j].length == 2
  • 0 <= uj, vj < n
  • uj != vj

Solution: DFS + Stack

Pre-compute for coprimes for each number.

For each node, enumerate all it’s coprime numbers, find the deepest occurrence.

Time complexity: O(n * max(nums))
Space complexity: O(n)

C++

花花酱 LeetCode 1765. Map of Highest Peak

You are given an integer matrix isWater of size m x n that represents a map of land and water cells.

  • If isWater[i][j] == 0, cell (i, j) is a land cell.
  • If isWater[i][j] == 1, cell (i, j) is a water cell.

You must assign each cell a height in a way that follows these rules:

  • The height of each cell must be non-negative.
  • If the cell is a water cell, its height must be 0.
  • Any two adjacent cells must have an absolute height difference of at most 1. A cell is adjacent to another cell if the former is directly north, east, south, or west of the latter (i.e., their sides are touching).

Find an assignment of heights such that the maximum height in the matrix is maximized.

Return an integer matrix height of size m x n where height[i][j] is cell (i, j)‘s height. If there are multiple solutions, return any of them.

Example 1:

Input: isWater = [[0,1],[0,0]]
Output: [[1,0],[2,1]]
Explanation: The image shows the assigned heights of each cell.
The blue cell is the water cell, and the green cells are the land cells.

Example 2:

Input: isWater = [[0,0,1],[1,0,0],[0,0,0]]
Output: [[1,1,0],[0,1,1],[1,2,2]]
Explanation: A height of 2 is the maximum possible height of any assignment.
Any height assignment that has a maximum height of 2 while still meeting the rules will also be accepted.

Constraints:

  • m == isWater.length
  • n == isWater[i].length
  • 1 <= m, n <= 1000
  • isWater[i][j] is 0 or 1.
  • There is at least one water cell.

Solution: BFS

h[y][x] = min distance of (x, y) to any water cell.

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

C++

花花酱 LeetCode 1718. Construct the Lexicographically Largest Valid Sequence

Given an integer n, find a sequence that satisfies all of the following:

  • The integer 1 occurs once in the sequence.
  • Each integer between 2 and n occurs twice in the sequence.
  • For every integer i between 2 and n, the distance between the two occurrences of i is exactly i.

The distance between two numbers on the sequence, a[i] and a[j], is the absolute difference of their indices, |j - i|.

Return the lexicographically largest sequence. It is guaranteed that under the given constraints, there is always a solution.

A sequence a is lexicographically larger than a sequence b (of the same length) if in the first position where a and b differ, sequence a has a number greater than the corresponding number in b. For example, [0,1,9,0] is lexicographically larger than [0,1,5,6] because the first position they differ is at the third number, and 9 is greater than 5.

Example 1:

Input: n = 3
Output: [3,1,2,3,2]
Explanation: [2,3,2,1,3] is also a valid sequence, but [3,1,2,3,2] is the lexicographically largest valid sequence.

Example 2:

Input: n = 5
Output: [5,3,1,4,3,5,2,4,2]

Constraints:

  • 1 <= n <= 20

Solution: Search

Search from left to right, largest to smallest.

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

C++

Java

Python3

花花酱 LeetCode 1654. Minimum Jumps to Reach Home

A certain bug’s home is on the x-axis at position x. Help them get there from position 0.

The bug jumps according to the following rules:

  • It can jump exactly a positions forward (to the right).
  • It can jump exactly b positions backward (to the left).
  • It cannot jump backward twice in a row.
  • It cannot jump to any forbidden positions.

The bug may jump forward beyond its home, but it cannot jump to positions numbered with negative integers.

Given an array of integers forbidden, where forbidden[i] means that the bug cannot jump to the position forbidden[i], and integers ab, and x, return the minimum number of jumps needed for the bug to reach its home. If there is no possible sequence of jumps that lands the bug on position x, return -1.

Example 1:

Input: forbidden = [14,4,18,1,15], a = 3, b = 15, x = 9
Output: 3
Explanation: 3 jumps forward (0 -> 3 -> 6 -> 9) will get the bug home.

Example 2:

Input: forbidden = [8,3,16,6,12,20], a = 15, b = 13, x = 11
Output: -1

Example 3:

Input: forbidden = [1,6,2,14,5,17,4], a = 16, b = 9, x = 7
Output: 2
Explanation: One jump forward (0 -> 16) then one jump backward (16 -> 7) will get the bug home.

Constraints:

  • 1 <= forbidden.length <= 1000
  • 1 <= a, b, forbidden[i] <= 2000
  • 0 <= x <= 2000
  • All the elements in forbidden are distinct.
  • Position x is not forbidden.

Solution: BFS

Normal BFS with two tricks:
1. For each position, we need to track whether it’s reached via a forward jump or backward jump
2. How far should we go? If we don’t limit, it can go forever which leads to TLE/MLE. We can limit the distance to 2*max_jump, e.g. 4000, that’s maximum distance we can jump back to home in one shot.

Time complexity: O(max_distance * 2)
Space complexity: O(max_distance * 2)

C++