Press "Enter" to skip to content

Posts tagged as “DFS”

花花酱 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 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 1286. Iterator for Combination

Design an Iterator class, which has:

  • A constructor that takes a string characters of sorted distinct lowercase English letters and a number combinationLength as arguments.
  • A function next() that returns the next combination of length combinationLength in lexicographical order.
  • A function hasNext() that returns True if and only if there exists a next combination.

Example:

CombinationIterator iterator = new CombinationIterator("abc", 2); // creates the iterator.

iterator.next(); // returns "ab"
iterator.hasNext(); // returns true
iterator.next(); // returns "ac"
iterator.hasNext(); // returns true
iterator.next(); // returns "bc"
iterator.hasNext(); // returns false

Constraints:

  • 1 <= combinationLength <= characters.length <= 15
  • There will be at most 10^4 function calls per test.
  • It’s guaranteed that all calls of the function next are valid.

Solution: Bitmask

Use a bitmask to represent the chars selected.
start with (2^n – 1), decrease the mask until there are c bit set.
stop when mask reach to 0.

mask: 111 => abc
mask: 110 => ab
mask: 101 => ac
mask: 011 => bc
mask: 000 => “” Done

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

C++

花花酱 LeetCode 1655. Distribute Repeating Integers

You are given an array of n integers, nums, where there are at most 50 unique values in the array. You are also given an array of m customer order quantities, quantity, where quantity[i] is the amount of integers the ith customer ordered. Determine if it is possible to distribute nums such that:

  • The ith customer gets exactly quantity[i] integers,
  • The integers the ith customer gets are all equal, and
  • Every customer is satisfied.

Return true if it is possible to distribute nums according to the above conditions.

Example 1:

Input: nums = [1,2,3,4], quantity = [2]
Output: false
Explanation: The 0th customer cannot be given two different integers.

Example 2:

Input: nums = [1,2,3,3], quantity = [2]
Output: true
Explanation: The 0th customer is given [3,3]. The integers [1,2] are not used.

Example 3:

Input: nums = [1,1,2,2], quantity = [2,2]
Output: true
Explanation: The 0th customer is given [1,1], and the 1st customer is given [2,2].

Example 4:

Input: nums = [1,1,2,3], quantity = [2,2]
Output: false
Explanation: Although the 0th customer could be given [1,1], the 1st customer cannot be satisfied.

Example 5:

Input: nums = [1,1,1,1,1], quantity = [2,3]
Output: true
Explanation: The 0th customer is given [1,1], and the 1st customer is given [1,1,1].

Constraints:

  • n == nums.length
  • 1 <= n <= 105
  • 1 <= nums[i] <= 1000
  • m == quantity.length
  • 1 <= m <= 10
  • 1 <= quantity[i] <= 105
  • There are at most 50 unique values in nums.

Solution1: Backtracking

Time complexity: O(|vals|^m)
Space complexity: O(|vals| + m)

C++

Solution 2: Bitmask + all subsets

dp(mask, i) := whether we can distribute to a subset of customers represented as a bit mask, using the i-th to (n-1)-th numbers.

Time complexity: O(2^m * m * |vals|) = O(2^10 * 10 * 50)
Space complexity: O(2^m * |vals|)

C++

Python3

Bottom up:

C++

花花酱 LeetCode 1625. Lexicographically Smallest String After Applying Operations

You are given a string s of even length consisting of digits from 0 to 9, and two integers a and b.

You can apply either of the following two operations any number of times and in any order on s:

  • Add a to all odd indices of s (0-indexed). Digits post 9 are cycled back to 0. For example, if s = "3456" and a = 5s becomes "3951".
  • Rotate s to the right by b positions. For example, if s = "3456" and b = 1s becomes "6345".

Return the lexicographically smallest string you can obtain by applying the above operations any number of times on s.

A string a is lexicographically smaller than a string b (of the same length) if in the first position where a and b differ, string a has a letter that appears earlier in the alphabet than the corresponding letter in b. For example, "0158" is lexicographically smaller than "0190" because the first position they differ is at the third letter, and '5' comes before '9'.

Example 1:

Input: s = "5525", a = 9, b = 2
Output: "2050"
Explanation: We can apply the following operations:
Start:  "5525"
Rotate: "2555"
Add:    "2454"
Add:    "2353"
Rotate: "5323"
Add:    "5222"
​​​​​​​Add:    "5121"
​​​​​​​Rotate: "2151"
​​​​​​​Add:    "2050"​​​​​​​​​​​​
There is no way to obtain a string that is lexicographically smaller then "2050".

Example 2:

Input: s = "74", a = 5, b = 1
Output: "24"
Explanation: We can apply the following operations:
Start:  "74"
Rotate: "47"
​​​​​​​Add:    "42"
​​​​​​​Rotate: "24"​​​​​​​​​​​​
There is no way to obtain a string that is lexicographically smaller then "24".

Example 3:

Input: s = "0011", a = 4, b = 2
Output: "0011"
Explanation: There are no sequence of operations that will give us a lexicographically smaller string than "0011".

Example 4:

Input: s = "43987654", a = 7, b = 3
Output: "00553311"

Constraints:

  • 2 <= s.length <= 100
  • s.length is even.
  • s consists of digits from 0 to 9 only.
  • 1 <= a <= 9
  • 1 <= b <= s.length - 1

Solution: Search

C++