Posts tagged as “DFS”

花花酱 LeetCode 1286. Iterator for Combination

By zxi on November 30, 2020

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

class CombinationIterator {

public:

CombinationIterator(string characters, int combinationLength):

chars_(rbegin(characters), rend(characters)),

length_(combinationLength),

mask_((1 << characters.size()) - 1) {}

string next() {

hasNext();

string ans;

for (int i = chars_.size() - 1; i >= 0 ; --i)

if ((mask_ >> i) & 1)

ans.push_back(chars_[i]);

--mask_;

return ans;

}

bool hasNext() {

while (mask_ >= 0 && __builtin_popcount(mask_) != length_) --mask_;

return mask_ > 0;

}

private:

int mask_ = 0;

const int length_;

const string chars_;

};

花花酱 LeetCode 1655. Distribute Repeating Integers

By zxi on November 14, 2020

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 i^th customer ordered. Determine if it is possible to distribute nums such that:

The i^th customer gets exactly quantity[i] integers,
The integers the i^th 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 <= 10⁵
1 <= nums[i] <= 1000
m == quantity.length
1 <= m <= 10
1 <= quantity[i] <= 10⁵
There are at most 50 unique values in nums.

Solution1: Backtracking

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

C++

// Author: Huahua

class Solution {

public:

bool canDistribute(vector<int>& nums, vector<int>& quantity) {

unordered_map<int, int> m;

for (int x : nums) ++m[x];

vector<int> cnt;

for (const auto& [x, c] : m) cnt.push_back(c);

const int q = quantity.size();

const int n = cnt.size();

function<bool(int)> dfs = [&](int d) {

if (d == q) return true;

for (int i = 0; i < n; ++i)

if (cnt[i] >= quantity[d]) {

cnt[i] -= quantity[d];

if (dfs(d + 1)) return true;

cnt[i] += quantity[d];

}

return false;

};

sort(rbegin(cnt), rend(cnt));

sort(rbegin(quantity), rend(quantity));

return dfs(0);

}

};

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

class Solution {

public:

bool canDistribute(vector<int>& nums, vector<int>& quantity) {

vector<int> cnt;

unordered_map<int, int> freq;

for (int x : nums) ++freq[x];

for (const auto& [x, f] : freq) cnt.push_back(f);

const int n = cnt.size();

const int m = quantity.size();

vector<vector<optional<bool>>> cache(1 << m, vector<optional<bool>>(n));

vector<int> sums(1 << m);

for (int mask = 0; mask < 1 << m; ++mask)

for (int i = 0; i < m; ++i)

if (mask & (1 << i))

sums[mask] += quantity[i];

function<bool(int, int)> dp = [&](int mask, int i) -> bool {

if (mask == 0) return true;

if (i == n) return false;

auto& ans = cache[mask][i];

if (ans.has_value()) return ans.value();

int cur = mask;

while (cur) {

if (sums[cur] <= cnt[i] && dp(mask ^ cur, i + 1)) {

ans = true;

return true;

}

cur = (cur - 1) & mask;

}

ans = dp(mask, i + 1);

return ans.value();

};

return dp((1 << m) - 1, 0);

}

};

Python3

# Author: Huahua

class Solution:

def canDistribute(self, nums: List[int],

quantity: List[int]) -> bool:

cnts = list(Counter(nums).values())

m = len(quantity)

n = len(cnts)

sums = [0] * (1 << m)

for mask in range(1 << m):

for i in range(m):

if mask & (1 << i): sums[mask] += quantity[i]

@lru_cache(None)

def dp(mask: int, i: int) -> bool:

if not mask: return True

if i < 0: return False

cur = mask

while cur:

if sums[cur] <= cnts[i] and dp(mask ^ cur, i - 1):

return True

cur = (cur - 1) & mask

return dp(mask, i - 1)

return dp((1 << m) - 1, n - 1)

Bottom up:

C++

class Solution {

public:

bool canDistribute(vector<int>& nums, vector<int>& quantity) {

vector<int> cnt;

unordered_map<int, int> freq;

for (int x : nums) ++freq[x];

for (const auto& [x, f] : freq) cnt.push_back(f);

const int n = cnt.size();

const int m = quantity.size();

vector<int> sums(1 << m);

for (int mask = 0; mask < 1 << m; ++mask)

for (int i = 0; i < m; ++i)

if (mask & (1 << i))

sums[mask] += quantity[i];

// dp[mask][i] := use first i types to satisfy mask customers.

vector<vector<int>> dp(1 << m, vector<int>(n + 1));

dp[0][0] = 1;

for (int mask = 0; mask < 1 << m; ++mask)

for (int i = 0; i < n; ++i) {

dp[mask][i + 1] |= dp[mask][i];

for (int cur = mask; cur; cur = (cur - 1) & mask)

if (sums[cur] <= cnt[i] && dp[mask ^ cur][i])

dp[mask][i + 1] = 1;

}

return dp[(1 << m) - 1][n];

}

};

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

By zxi on October 18, 2020

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 = 5, s becomes "3951".
Rotate s to the right by b positions. For example, if s = "3456" and b = 1, s 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++

// Author: Huahua

class Solution {

public:

string findLexSmallestString(string s, int a, int b) {

unordered_set<string> seen;

string ans(s);

function<void(string)> dfs = [&](const string& s) {

if (!seen.insert(s).second) return;

ans = min(ans, s);

string t(s);

for (int i = 1; i < s.length(); i += 2)

t[i] = (t[i] - '0' + a) % 10 + '0';

dfs(t);

dfs(s.substr(b) + s.substr(0, b));

};

dfs(s);

return ans;

}

};

花花酱 LeetCode 1600. Throne Inheritance

By zxi on September 27, 2020

A kingdom consists of a king, his children, his grandchildren, and so on. Every once in a while, someone in the family dies or a child is born.

The kingdom has a well-defined order of inheritance that consists of the king as the first member. Let’s define the recursive function Successor(x, curOrder), which given a person x and the inheritance order so far, returns who should be the next person after x in the order of inheritance.

Successor(x, curOrder):

if x has no children or all of x's children are in curOrder:

if x is the king return null

else return Successor(x's parent, curOrder)

else return x's oldest child who's not in curOrder

For example, assume we have a kingdom that consists of the king, his children Alice and Bob (Alice is older than Bob), and finally Alice’s son Jack.

In the beginning, curOrder will be ["king"].
Calling Successor(king, curOrder) will return Alice, so we append to curOrder to get ["king", "Alice"].
Calling Successor(Alice, curOrder) will return Jack, so we append to curOrder to get ["king", "Alice", "Jack"].
Calling Successor(Jack, curOrder) will return Bob, so we append to curOrder to get ["king", "Alice", "Jack", "Bob"].
Calling Successor(Bob, curOrder) will return null. Thus the order of inheritance will be ["king", "Alice", "Jack", "Bob"].

Using the above function, we can always obtain a unique order of inheritance.

Implement the ThroneInheritance class:

ThroneInheritance(string kingName) Initializes an object of the ThroneInheritance class. The name of the king is given as part of the constructor.
void birth(string parentName, string childName) Indicates that parentName gave birth to childName.
void death(string name) Indicates the death of name. The death of the person doesn’t affect the Successor function nor the current inheritance order. You can treat it as just marking the person as dead.
string[] getInheritanceOrder() Returns a list representing the current order of inheritance excluding dead people.

Example 1:

Input
["ThroneInheritance", "birth", "birth", "birth", "birth", "birth", "birth", "getInheritanceOrder", "death", "getInheritanceOrder"]
[["king"], ["king", "andy"], ["king", "bob"], ["king", "catherine"], ["andy", "matthew"], ["bob", "alex"], ["bob", "asha"], [null], ["bob"], [null]]
Output
[null, null, null, null, null, null, null, ["king", "andy", "matthew", "bob", "alex", "asha", "catherine"], null, ["king", "andy", "matthew", "alex", "asha", "catherine"]]
Explanation
ThroneInheritance t= new ThroneInheritance("king"); // order: king
t.birth("king", "andy"); // order: king > andy
t.birth("king", "bob"); // order: king > andy > bob
t.birth("king", "catherine"); // order: king > andy > bob > catherine
t.birth("andy", "matthew"); // order: king > andy > matthew > bob > catherine
t.birth("bob", "alex"); // order: king > andy > matthew > bob > alex > catherine
t.birth("bob", "asha"); // order: king > andy > matthew > bob > alex > asha > catherine
t.getInheritanceOrder(); // return ["king", "andy", "matthew", "bob", "alex", "asha", "catherine"]
t.death("bob"); // order: king > andy > matthew > bob > alex > asha > catherine
t.getInheritanceOrder(); // return ["king", "andy", "matthew", "alex", "asha", "catherine"]

Constraints:

1 <= kingName.length, parentName.length, childName.length, name.length <= 15
kingName, parentName, childName, and name consist of lowercase English letters only.
All arguments childName and kingName are distinct.
All name arguments of death will be passed to either the constructor or as childName to birth first.
For each call to birth(parentName, childName), it is guaranteed that parentName is alive.
At most 10⁵ calls will be made to birth and death.
At most 10 calls will be made to getInheritanceOrder.

Solution: HashTable + DFS

Record :
1. mapping from parent to children (ordered)
2. who has dead

Time complexity: getInheritanceOrder O(n), other O(1)
Space complexity: O(n)

C++

// Author: Huahua

class ThroneInheritance {

public:

ThroneInheritance(string kingName): king_(kingName) {

m_[kingName] = {};

}

void birth(string parentName, string childName) {

m_[parentName].push_back(childName);

}

void death(string name) {

dead_.insert(name);

}

vector<string> getInheritanceOrder() {

vector<string> ans;

function<void(const string&)> dfs = [&](const string& name) {

if (!dead_.count(name)) ans.push_back(name);

for (const string& child: m_[name]) dfs(child);

};

dfs(king_);

return ans;

}

private:

string king_;

unordered_map<string, vector<string>> m_; // parent -> list[children]

unordered_set<string> dead_;

};

Python3

# Author: Huahua

class ThroneInheritance:

def __init__(self, kingName: str):

self.kingName = kingName

self.family = defaultdict(list)

self.dead = set()

def birth(self, parentName: str, childName: str) -> None:

self.family[parentName].append(childName)

def death(self, name: str) -> None:

self.dead.add(name)

def getInheritanceOrder(self) -> List[str]:

order = []

def dfs(name: str):

if name not in self.dead: order.append(name)

for child in self.family[name]: dfs(child)

dfs(self.kingName)

return order

花花酱 LeetCode 1591. Strange Printer II

By zxi on September 20, 2020

There is a strange printer with the following two special requirements:

On each turn, the printer will print a solid rectangular pattern of a single color on the grid. This will cover up the existing colors in the rectangle.
Once the printer has used a color for the above operation, the same color cannot be used again.

You are given a m x n matrix targetGrid, where targetGrid[row][col] is the color in the position (row, col) of the grid.

Return true if it is possible to print the matrix targetGrid, otherwise, return false.

Example 1:

Input: targetGrid = [[1,1,1,1],[1,2,2,1],[1,2,2,1],[1,1,1,1]]
Output: true

Example 2:

Input: targetGrid = [[1,1,1,1],[1,1,3,3],[1,1,3,4],[5,5,1,4]]
Output: true

Example 3:

Input: targetGrid = [[1,2,1],[2,1,2],[1,2,1]]
Output: false
Explanation: It is impossible to form targetGrid because it is not allowed to print the same color in different turns.

Example 4:

Input: targetGrid = [[1,1,1],[3,1,3]]
Output: false

Constraints:

m == targetGrid.length
n == targetGrid[i].length
1 <= m, n <= 60
1 <= targetGrid[row][col] <= 60

Solution: Dependency graph

For each color C find the maximum rectangle to cover it. Any other color C’ in this rectangle is a dependency of C, e.g. C’ must be print first in order to print C.

Then this problem reduced to check if there is any cycle in the dependency graph.

e.g.
1 2 1
2 1 2
1 2 1
The maximum rectangle for 1 and 2 are both [0, 0] ~ [2, 2]. 1 depends on 2, and 2 depends on 1. This is a circular reference and no way to print.

Time complexity: O(C*M*N)
Space complexity: O(C*C)

C++

class Solution {

public:

bool isPrintable(vector<vector<int>>& targetGrid) {

constexpr int kMaxC = 60;

const int m = targetGrid.size();

const int n = targetGrid[0].size();

vector<unordered_set<int>> deps(kMaxC + 1);

for (int c = 1; c <= kMaxC; ++c) {

int l = n, r = -1, t = m, b = -1;

for (int i = 0; i < m; ++i)

for (int j = 0; j < n; ++j)

if (targetGrid[i][j] == c)

l = min(l, j), r = max(r, j), t = min(t, i), b = max(b, i);

if (l == -1) continue;

for (int i = t; i <= b; ++i)

for (int j = l; j <= r; ++j)

if (targetGrid[i][j] != c)

deps[c].insert(targetGrid[i][j]);

}

vector<int> seen(kMaxC + 1);

function<bool(int)> hasCycle = [&](int c) {

if (seen[c] == 1) return true;

if (seen[c] == 2) return false;

seen[c] = 1;

for (int t : deps[c])

if (hasCycle(t)) return true;

seen[c] = 2;

return false;

};

for (int c = 1; c <= kMaxC; ++c)

if (hasCycle(c)) return false;

return true;

}

};