Posts tagged as “hard”

花花酱 LeetCode 1559. Detect Cycles in 2D Grid

By zxi on August 23, 2020

Given a 2D array of characters grid of size m x n, you need to find if there exists any cycle consisting of the same value in grid.

A cycle is a path of length 4 or more in the grid that starts and ends at the same cell. From a given cell, you can move to one of the cells adjacent to it – in one of the four directions (up, down, left, or right), if it has the same value of the current cell.

Also, you cannot move to the cell that you visited in your last move. For example, the cycle (1, 1) -> (1, 2) -> (1, 1) is invalid because from (1, 2) we visited (1, 1) which was the last visited cell.

Return true if any cycle of the same value exists in grid, otherwise, return false.

Example 1:

Input: grid = [["a","a","a","a"],["a","b","b","a"],["a","b","b","a"],["a","a","a","a"]]
Output: true
Explanation: There are two valid cycles shown in different colors in the image below:

Example 2:

Input: grid = [["c","c","c","a"],["c","d","c","c"],["c","c","e","c"],["f","c","c","c"]]
Output: true
Explanation: There is only one valid cycle highlighted in the image below:

Example 3:

Input: grid = [["a","b","b"],["b","z","b"],["b","b","a"]]
Output: false

Constraints:

m == grid.length
n == grid[i].length
1 <= m <= 500
1 <= n <= 500
grid consists only of lowercase English letters.

Solution: DFS

Finding a cycle in an undirected graph => visiting a node that has already been visited and it’s not the parent node of the current node.
b b
b b
null -> (0, 0) -> (0, 1) -> (1, 1) -> (1, 0) -> (0, 0)
The second time we visit (0, 0) which has already been visited before and it’s not the parent of the current node (1, 0) ( (1, 0)’s parent is (1, 1) ) which means we found a cycle.

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

C++

class Solution {

public:

bool containsCycle(vector<vector<char>>& grid) {

const int m = grid.size();

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

vector<vector<int>> seen(m, vector<int>(n));

vector<int> dirs{0, 1, 0, -1, 0};

function<bool(int, int, int, int)> dfs = [&](int i, int j, int pi, int pj) {

++seen[i][j];

for (int d = 0; d < 4; ++d) {

int ni = i + dirs[d];

int nj = j + dirs[d + 1];

if (ni < 0 || nj < 0 || ni >= m || nj >= n) continue;

if (grid[ni][nj] != grid[i][j]) continue;

if (!seen[ni][nj]) {

if (dfs(ni, nj, i, j)) return true;

} else if (ni != pi || nj != pj) {

return true;

}

return false;

};

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

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

if (!seen[i][j]++ && dfs(i, j, -1, -1))

return true;

return false;

}

};

花花酱 LeetCode 1553. Minimum Number of Days to Eat N Oranges

By zxi on August 16, 2020

There are n oranges in the kitchen and you decided to eat some of these oranges every day as follows:

Eat one orange.
If the number of remaining oranges (n) is divisible by 2 then you can eat n/2 oranges.
If the number of remaining oranges (n) is divisible by 3 then you can eat 2*(n/3) oranges.

You can only choose one of the actions per day.

Return the minimum number of days to eat n oranges.

Example 1:

Input: n = 10
Output: 4
Explanation: You have 10 oranges.
Day 1: Eat 1 orange,  10 - 1 = 9.  
Day 2: Eat 6 oranges, 9 - 2*(9/3) = 9 - 6 = 3. (Since 9 is divisible by 3)
Day 3: Eat 2 oranges, 3 - 2*(3/3) = 3 - 2 = 1. 
Day 4: Eat the last orange  1 - 1  = 0.
You need at least 4 days to eat the 10 oranges.

Example 2:

Input: n = 6
Output: 3
Explanation: You have 6 oranges.
Day 1: Eat 3 oranges, 6 - 6/2 = 6 - 3 = 3. (Since 6 is divisible by 2).
Day 2: Eat 2 oranges, 3 - 2*(3/3) = 3 - 2 = 1. (Since 3 is divisible by 3)
Day 3: Eat the last orange  1 - 1  = 0.
You need at least 3 days to eat the 6 oranges.

Example 3:

Input: n = 1
Output: 1

Example 4:

Input: n = 56
Output: 6

Constraints:

1 <= n <= 2*10^9

Solution: Greedy + DP

Eat oranges one by one to make it a multiply of 2 or 3 such that we can eat 50% or 66.66…% of the oranges in one step.
dp(n) := min steps to finish n oranges.
base case n <= 1, dp(n) = n
transition: dp(n) = 1 + min(n%2 + dp(n/2), n % 3 + dp(n / 3))
e.g. n = 11,
we eat 11%2 = 1 in one step, left = 10 and then eat 10 / 2 = 5 in another step. 5 left for the subproblem.
we eat 11%3 = 2 in two steps, left = 9 and then eat 9 * 2 / 3 = 6 in another step, 3 left for the subproblem.
dp(11) = 1 + min(1 + dp(5), 2 + dp(3))

T(n) = 2*T(n/2) + O(1) = O(n)
Time complexity: O(n) // w/o memoization, close to O(logn) in practice.
Space complexity: O(logn)

C++

class Solution {

public:

int minDays(int n) {

unordered_map<int, int> cache;

function<int(int)> dp = [&](int n) {

if (n <= 1) return n;

auto it = cache.find(n);

if (it != cache.end()) return it->second;

return cache[n] = 1 + min(n % 2 + dp(n / 2), n % 3 + dp(n / 3));

};

return dp(n);

}

};

Java

class Solution {

private static Map<Integer, Integer> cache = new HashMap<>();

public int minDays(int n) {

return dp(n);

}

private int dp(int n) {

if (n <= 1) return n;

if (cache.containsKey(n)) return cache.get(n);

int ans = 1 + Math.min(n % 2 + dp(n / 2), n % 3 + dp(n / 3));

cache.put(n, ans);

return ans;

}

Python3

class Solution:

def minDays(self, n: int) -> int:

@lru_cache(None)

def dp(n):

if n <= 1: return n

return 1 + min(n % 2 + dp(n // 2), n % 3 + dp(n // 3))

return dp(n)

Solution 2: BFS

if x % 2 == 0, push x/2 onto the queue
if x % 3 == 0, push x/3 onto the queue
always push x – 1 onto the queue

C++

class Solution {

public:

int minDays(int n) {

queue<int> q{{n}};

unordered_set<int> seen;

int steps = 0;

while (!q.empty()) {

int size = q.size();

while (size--) {

int x = q.front(); q.pop();

if (x == 0) return steps;

if (x % 2 == 0 && seen.insert(x / 2).second)

q.push(x / 2);

if (x % 3 == 0 && seen.insert(x / 3).second)

q.push(x / 3);

if (seen.insert(x - 1).second)

q.push(x - 1);

}

++steps;

}

return -1;

}

};

花花酱 LeetCode 1537. Get the Maximum Score

By zxi on August 2, 2020

You are given two sorted arrays of distinct integers nums1 and nums2.

A validpath is defined as follows:

Choose array nums1 or nums2 to traverse (from index-0).
Traverse the current array from left to right.
If you are reading any value that is present in nums1 and nums2 you are allowed to change your path to the other array. (Only one repeated value is considered in the valid path).

Score is defined as the sum of uniques values in a valid path.

Return the maximum score you can obtain of all possible valid paths.

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

Example 1:

Input: nums1 = [2,4,5,8,10], nums2 = [4,6,8,9]
Output: 30
Explanation: Valid paths:
[2,4,5,8,10], [2,4,5,8,9], [2,4,6,8,9], [2,4,6,8,10],  (starting from nums1)
[4,6,8,9], [4,5,8,10], [4,5,8,9], [4,6,8,10]    (starting from nums2)
The maximum is obtained with the path in green [2,4,6,8,10].

Example 2:

Input: nums1 = [1,3,5,7,9], nums2 = [3,5,100]
Output: 109
Explanation: Maximum sum is obtained with the path [1,3,5,100].

Example 3:

Input: nums1 = [1,2,3,4,5], nums2 = [6,7,8,9,10]
Output: 40
Explanation: There are no common elements between nums1 and nums2.
Maximum sum is obtained with the path [6,7,8,9,10].

Example 4:

Input: nums1 = [1,4,5,8,9,11,19], nums2 = [2,3,4,11,12]
Output: 61

Constraints:

1 <= nums1.length <= 10^5
1 <= nums2.length <= 10^5
1 <= nums1[i], nums2[i] <= 10^7
nums1 and nums2 are strictly increasing.

Solution: Two Pointers + DP

Since numbers are strictly increasing, we can always traverse the smaller one using two pointers.
Traversing ([2,4,5,8,10], [4,6,8,10])
will be like [2, 4/4, 5, 6, 8, 10/10]
It two nodes have the same value, we have two choices and pick the larger one, then both move nodes one step forward. Otherwise, the smaller node moves one step forward.
dp1[i] := max path sum ends with nums1[i-1]
dp2[j] := max path sum ends with nums2[j-1]
if nums[i -1] == nums[j – 1]:
dp1[i] = dp2[j] = max(dp[i-1], dp[j-1]) + nums[i -1]
i += 1, j += 1
else if nums[i – 1] < nums[j – 1]:
dp[i] = dp[i-1] + nums[i -1]
i += 1
else if nums[j – 1] < nums[i – 1]:
dp[j] = dp[j-1] + nums[j -1]
j += 1
return max(dp1[-1], dp2[-1])

Time complexity: O(n)
Space complexity: O(n) -> O(1)

C++

class Solution {

public:

int maxSum(vector<int>& nums1, vector<int>& nums2) {

constexpr int kMod = 1e9 + 7;

const int n1 = nums1.size();

const int n2 = nums2.size();

vector<long> dp1(n1 + 1); // max path sum ends with nums1[i-1]

vector<long> dp2(n2 + 1); // max path sum ends with nums2[j-1]

int i = 0;

int j = 0;

while (i < n1 || j < n2) {

if (i < n1 && j < n2 && nums1[i] == nums2[j]) {

// Same, two choices, pick the larger one.

dp2[j + 1] = dp1[i + 1] = max(dp1[i], dp2[j]) + nums1[i];

++i; ++j;

} else if (i < n1 && (j == n2 || nums1[i] < nums2[j])) {

dp1[i + 1] = dp1[i] + nums1[i];

++i;

} else if (j < n2 && (i == n1 || nums2[j] < nums1[i])) {

dp2[j + 1] = dp2[j] + nums2[j];

++j;

}

return max(dp1.back(), dp2.back()) % kMod;

}

};

Java

class Solution {

public int maxSum(int[] nums1, int[] nums2) {

final int kMod = 1_000_000_007;

int n1 = nums1.length;

int n2 = nums2.length;

int i = 0;

int j = 0;

long a = 0;

long b = 0;

while (i < n1 || j < n2) {

if (i < n1 && j < n2 && nums1[i] == nums2[j]) {

a = b = Math.max(a, b) + nums1[i];

++i;

++j;

} else if (i < n1 && (j == n2 || nums1[i] < nums2[j])) {

a += nums1[i++];

} else {

b += nums2[j++];

}

return (int)(Math.max(a, b) % kMod);

}

python3

class Solution:

def maxSum(self, nums1: List[int], nums2: List[int]) -> int:

n1, n2 = len(nums1), len(nums2)

i, j = 0, 0

a, b = 0, 0

while i < n1 or j < n2:

if i < n1 and j < n2 and nums1[i] == nums2[j]:

a = b = max(a, b) + nums1[i]

i += 1

j += 1

elif i < n1 and (j == n2 or nums1[i] < nums2[j]):

a += nums1[i]

i += 1

else:

b += nums2[j]

j += 1

return max(a, b) % (10**9 + 7)

花花酱 LeetCode 1531. String Compression II

By zxi on July 26, 2020

Run-length encoding is a string compression method that works by replacing consecutive identical characters (repeated 2 or more times) with the concatenation of the character and the number marking the count of the characters (length of the run). For example, to compress the string "aabccc" we replace "aa" by "a2" and replace "ccc" by "c3". Thus the compressed string becomes "a2bc3".

Notice that in this problem, we are not adding '1' after single characters.

Given a string s and an integer k. You need to delete at most k characters from s such that the run-length encoded version of s has minimum length.

Find the minimum length of the run-length encoded version of s after deleting at most k characters.

Example 1:

Input: s = "aaabcccd", k = 2
Output: 4
Explanation: Compressing s without deleting anything will give us "a3bc3d" of length 6. Deleting any of the characters 'a' or 'c' would at most decrease the length of the compressed string to 5, for instance delete 2 'a' then we will have s = "abcccd" which compressed is abc3d. Therefore, the optimal way is to delete 'b' and 'd', then the compressed version of s will be "a3c3" of length 4.

Example 2:

Input: s = "aabbaa", k = 2
Output: 2
Explanation: If we delete both 'b' characters, the resulting compressed string would be "a4" of length 2.

Example 3:

Input: s = "aaaaaaaaaaa", k = 0
Output: 3
Explanation: Since k is zero, we cannot delete anything. The compressed string is "a11" of length 3.

Constraints:

1 <= s.length <= 100
0 <= k <= s.length
s contains only lowercase English letters.

Solution 0: Brute Force DFS (TLE)

Time complexity: O(C(n,k))
Space complexity: O(k)

C++

class Solution {

public:

int getLengthOfOptimalCompression(string s, int k) {

const int n = s.length();

auto encode = [&]() -> int {

char p = '$';

int count = 0;

int len = 0;

for (char c : s) {

if (c == '.') continue;

if (c != p) {

p = c;

count = 0;

}

++count;

if (count <= 2 || count == 10 || count == 100)

++len;

}

return len;

};

function<int(int, int)> dfs = [&](int start, int k) -> int {

if (start == n || k == 0) return encode();

int ans = n;

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

char c = s[i];

s[i] = '.'; // delete

ans = min(ans, dfs(i + 1, k - 1));

s[i] = c;

}

return ans;

};

return dfs(0, k);

}

};

Solution1: DP

State:
i: the start index of the substring
last: last char
len: run-length
k: # of chars that can be deleted.

base case:
1. k < 0: return inf # invalid
2. i >= s.length(): return 0 # done

Transition:
1. if s[i] == last: return carry + dp(i + 1, last, len + 1, k)

2. if s[i] != last:
return min(1 + dp(i + 1, s[i], 1, k, # start a new group with s[i]
dp(i + 1, last, len, k -1) # delete / skip s[i], keep it as is.

Time complexity: O(n^3*26)
Space complexity: O(n^3*26)

C++

int cache[101][27][101][101];

class Solution {

public:

int getLengthOfOptimalCompression(string s, int k) {

memset(cache, -1, sizeof(cache));

// Min length of compressioned string of s[i:]

// 1. last char is |last|

// 2. current run-length is len

// 3. we can delete k chars.

function<int(int, int, int, int)> dp =

[&](int i, int last, int len, int k) {

if (k < 0) return INT_MAX / 2;

if (i >= s.length()) return 0;

int& ans = cache[i][last][len][k];

if (ans != -1) return ans;

if (s[i] - 'a' == last) {

// same as the previous char, no need to delete.

int carry = (len == 1 || len == 9 || len == 99);

ans = carry + dp(i + 1, last, len + 1, k);

} else {

ans = min(1 + dp(i + 1, s[i] - 'a', 1, k), // keep s[i]

dp(i + 1, last, len, k - 1)); // delete s[i]

}

return ans;

};

return dp(0, 26, 0, k);

}

};

State compression

dp[i][k] := min len of s[i:] encoded by deleting at most k charchters.

dp[i][k] = min(dp[i+1][k-1] # delete s[i]
encode_len(s[i~j] == s[i]) + dp(j+1, k – sum(s[i~j])) for j in range(i, n)) # keep

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

C++

// Author: Huahua

class Solution {

public:

int getLengthOfOptimalCompression(string s, int k) {

const int n = s.length();

vector<vector<int>> cache(n, vector<int>(k + 1, -1));

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

if (k < 0) return n;

if (i + k >= n) return 0;

int& ans = cache[i][k];

if (ans != -1) return ans;

ans = dp(i + 1, k - 1); // delete

int len = 0;

int same = 0;

int diff = 0;

for (int j = i; j < n && diff <= k; ++j) {

if (s[j] == s[i] && ++same) {

if (same <= 2 || same == 10 || same == 100) ++len;

} else {

++diff;

}

ans = min(ans, len + dp(j + 1, k - diff));

}

return ans;

};

return dp(0, k);

}

};

Java

// Author: Huahua

class Solution {

private int[][] dp;

private char[] s;

private int n;

public int getLengthOfOptimalCompression(

String s, int k) {

this.s = s.toCharArray();

this.n = s.length();

this.dp = new int[n][k + 1];

for (int[] row : dp)

Arrays.fill(row, -1);

return dp(0, k);

}

private int dp(int i, int k) {

if (k < 0) return this.n;

if (i + k >= n) return 0; // done or delete all.

int ans = dp[i][k];

if (ans != -1) return ans;

ans = dp(i + 1, k - 1); // delete s[i]

int len = 0;

int same = 0;

int diff = 0;

for (int j = i; j < n && diff <= k; ++j) {

if (s[j] == s[i]) {

++same;

if (same <= 2 || same == 10 || same == 100) ++len;

} else {

++diff;

}

ans = Math.min(ans, len + dp(j + 1, k - diff));

}

dp[i][k] = ans;

return ans;

}

Python3

# Author: Huahua

class Solution:

def getLengthOfOptimalCompression(self, s: str, k: int) -> int:

n = len(s)

@functools.lru_cache(maxsize=None)

def dp(i, k):

if k < 0: return n

if i + k >= n: return 0

ans = dp(i + 1, k - 1)

l = 0

same = 0

for j in range(i, n):

if s[j] == s[i]:

same += 1

if same <= 2 or same == 10 or same == 100:

l += 1

diff = j - i + 1 - same

if diff < 0: break

ans = min(ans, l + dp(j + 1, k - diff))

return ans

return dp(0, k)

花花酱 LeetCode 1521. Find a Value of a Mysterious Function Closest to Target

By zxi on July 19, 2020

Winston was given the above mysterious function func. He has an integer array arr and an integer target and he wants to find the values l and r that make the value |func(arr, l, r) - target| minimum possible.

Return the minimum possible value of |func(arr, l, r) - target|.

Notice that func should be called with the values l and r where 0 <= l, r < arr.length.

Example 1:

Input: arr = [9,12,3,7,15], target = 5
Output: 2
Explanation: Calling func with all the pairs of [l,r] = [[0,0],[1,1],[2,2],[3,3],[4,4],[0,1],[1,2],[2,3],[3,4],[0,2],[1,3],[2,4],[0,3],[1,4],[0,4]], Winston got the following results [9,12,3,7,15,8,0,3,7,0,0,3,0,0,0]. The value closest to 5 is 7 and 3, thus the minimum difference is 2.

Example 2:

Input: arr = [1000000,1000000,1000000], target = 1
Output: 999999
Explanation: Winston called the func with all possible values of [l,r] and he always got 1000000, thus the min difference is 999999.

Example 3:

Input: arr = [1,2,4,8,16], target = 0
Output: 0

Constraints:

1 <= arr.length <= 10^5
1 <= arr[i] <= 10^6
0 <= target <= 10^7

Solution: Brute Force w/ Optimization

Try all possible [l, r] range with pruning.
1. for a given l, we extend r, since s & x <= s, if s becomes less than target, we can stop the inner loop.
2. Case 1, s = arr[l] & … & arr[n-1], s > target,
Let s’ = arr[l+1] & … & arr[n-1], s’ >= s,
if s > target, then s’ > target, we can stop outer loop as well.
Case 2, inner loop stops at r, s = arr[l] & … & arr[r], s <= target, we continue with l+1.

Time complexity: O(n)? on average, O(n^2) in worst case.
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int closestToTarget(vector<int>& arr, int target) {

const int n = arr.size();

int ans = INT_MAX;

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

int s = arr[i];

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

s &= arr[j];

ans = min(ans, abs(s - target));

if (ans == 0) return 0;

if (s <= target) break; // s is decreasing.

}

if (s > target) break; // s is increasing.

}

return ans;

}

};