Posts published in “Uncategorized”

花花酱 LeetCode 2120. Execution of All Suffix Instructions Staying in a Grid

By zxi on December 26, 2021

There is an n x n grid, with the top-left cell at (0, 0) and the bottom-right cell at (n - 1, n - 1). You are given the integer n and an integer array startPos where startPos = [start_row, start_col] indicates that a robot is initially at cell (start_row, start_col).

You are also given a 0-indexed string s of length m where s[i] is the i^th instruction for the robot: 'L' (move left), 'R' (move right), 'U' (move up), and 'D' (move down).

The robot can begin executing from any i^th instruction in s. It executes the instructions one by one towards the end of s but it stops if either of these conditions is met:

The next instruction will move the robot off the grid.
There are no more instructions left to execute.

Return an array answer of length m where answer[i] is the number of instructions the robot can execute if the robot begins executing from the i^th instruction in s.

Example 1:

Input: n = 3, startPos = [0,1], s = "RRDDLU"
Output: [1,5,4,3,1,0]
Explanation: Starting from startPos and beginning execution from the i^th instruction:
- 0^th: "RRDDLU". Only one instruction "R" can be executed before it moves off the grid.
- 1^st:  "RDDLU". All five instructions can be executed while it stays in the grid and ends at (1, 1).
- 2^nd:   "DDLU". All four instructions can be executed while it stays in the grid and ends at (1, 0).
- 3^rd:    "DLU". All three instructions can be executed while it stays in the grid and ends at (0, 0).
- 4^th:     "LU". Only one instruction "L" can be executed before it moves off the grid.
- 5^th:      "U". If moving up, it would move off the grid.

Example 2:

Input: n = 2, startPos = [1,1], s = "LURD"
Output: [4,1,0,0]
Explanation:
- 0^th: "LURD".
- 1^st:  "URD".
- 2^nd:   "RD".
- 3^rd:    "D".

Example 3:

Input: n = 1, startPos = [0,0], s = "LRUD"
Output: [0,0,0,0]
Explanation: No matter which instruction the robot begins execution from, it would move off the grid.

Constraints:

m == s.length
1 <= n, m <= 500
startPos.length == 2
0 <= start_row, start_col < n
s consists of 'L', 'R', 'U', and 'D'.

Solution: Simulation

Time complexity: O(m²)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

vector<int> executeInstructions(int n, vector<int>& startPos, string s) {

const int m = s.length();

auto moves = [&](int k) -> int {

int x = startPos[1];

int y = startPos[0];

for (int i = k; i < m; ++i) {

switch (s[i]) {

case 'R': x += 1; break;

case 'D': y += 1; break;

case 'L': x -= 1; break;

case 'U': y -= 1; break;

}

if (x < 0 || x == n || y < 0 || y == n)

return i - k;

}

return m - k;

};

vector<int> ans(m);

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

ans[i] = moves(i);

return ans;

}

};

花花酱 LeetCode 1768. Merge Strings Alternately

By zxi on February 20, 2021

You are given two strings word1 and word2. Merge the strings by adding letters in alternating order, starting with word1. If a string is longer than the other, append the additional letters onto the end of the merged string.

Return the merged string.

Example 1:

Input: word1 = "abc", word2 = "pqr"
Output: "apbqcr"
Explanation: The merged string will be merged as so:
word1:  a   b   c
word2:    p   q   r
merged: a p b q c r

Example 2:

Input: word1 = "ab", word2 = "pqrs"
Output: "apbqrs"
Explanation: Notice that as word2 is longer, "rs" is appended to the end.
word1:  a   b 
word2:    p   q   r   s
merged: a p b q   r   s

Example 3:

Input: word1 = "abcd", word2 = "pq"
Output: "apbqcd"
Explanation: Notice that as word1 is longer, "cd" is appended to the end.
word1:  a   b   c   d
word2:    p   q 
merged: a p b q c   d

Constraints:

1 <= word1.length, word2.length <= 100
word1 and word2 consist of lowercase English letters.

Solution: Find the shorter one

Time complexity: O(m+n)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

string mergeAlternately(string word1, string word2) {

const int l1 = word1.size(), l2 = word2.size();

string ans;

for (int i = 0; i < min(l1, l2); ++i) {

ans += word1[i];

ans += word2[i];

}

ans += l1 > l2 ? word1.substr(l2) : word2.substr(l1);

return ans;

}

};

花花酱 LeetCode 1722. Minimize Hamming Distance After Swap Operations

By zxi on January 10, 2021

You are given two integer arrays, source and target, both of length n. You are also given an array allowedSwaps where each allowedSwaps[i] = [a_i, b_i] indicates that you are allowed to swap the elements at index a_i and index b_i (0-indexed) of array source. Note that you can swap elements at a specific pair of indices multiple times and in any order.

The Hamming distance of two arrays of the same length, source and target, is the number of positions where the elements are different. Formally, it is the number of indices i for 0 <= i <= n-1 where source[i] != target[i] (0-indexed).

Return the minimum Hamming distance of source and target after performing any amount of swap operations on array source.

Example 1:

Input: source = [1,2,3,4], target = [2,1,4,5], allowedSwaps = [[0,1],[2,3]]
Output: 1
Explanation: source can be transformed the following way:
- Swap indices 0 and 1: source = [2,1,3,4]
- Swap indices 2 and 3: source = [2,1,4,3]
The Hamming distance of source and target is 1 as they differ in 1 position: index 3.

Example 2:

Input: source = [1,2,3,4], target = [1,3,2,4], allowedSwaps = []
Output: 2
Explanation: There are no allowed swaps.
The Hamming distance of source and target is 2 as they differ in 2 positions: index 1 and index 2.

Example 3:

Input: source = [5,1,2,4,3], target = [1,5,4,2,3], allowedSwaps = [[0,4],[4,2],[1,3],[1,4]]
Output: 0

Constraints:

n == source.length == target.length
1 <= n <= 10⁵
1 <= source[i], target[i] <= 10⁵
0 <= allowedSwaps.length <= 10⁵
allowedSwaps[i].length == 2
0 <= a_i, b_i <= n - 1
a_i != b_i

Solution: Union Find

Think each pair as an edge in a graph. Since we can swap as many time as we want, which means we can arrange the elements whose indices are in a connected component (CC) in any order.

For each index i, we increase the counter of CC(i) for key source[i] and decrease the counter of the same CC for key target[i]. If two keys are the same (can from different indices), one from source and one from target, it will cancel out, no distance. Otherwise, the counter will be off by two. Finally we sum up the counter for all the keys and divide it by two to get the hamming distance.

Time complexity: O(V+E)
Space complexity: O(V)

C++

// Author: huahua

class Solution {

public:

int minimumHammingDistance(vector<int>& source, vector<int>& target, vector<vector<int>>& allowedSwaps) {

const int n = source.size();

vector<int> p(n);

iota(begin(p), end(p), 0);

function<int(int)> find = [&](int x) {

return x == p[x] ? x : p[x] = find(p[x]);

};

for (const auto& s : allowedSwaps)

p[find(s[0])] = find(s[1]);

unordered_map<int, unordered_map<int, int>> m;

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

++m[find(i)][source[i]];

--m[find(i)][target[i]];

}

int ans = 0;

for (const auto& g : m)

for (const auto& kv : g.second)

ans += abs(kv.second);

return ans / 2;

}

};

花花酱 LeetCode 1673. Find the Most Competitive Subsequence

By zxi on November 29, 2020

Given an integer array nums and a positive integer k, return the most competitive subsequence of nums of size k.

An array’s subsequence is a resulting sequence obtained by erasing some (possibly zero) elements from the array.

We define that a subsequence a is more competitive than a subsequence b (of the same length) if in the first position where a and b differ, subsequence a has a number less than the corresponding number in b. For example, [1,3,4] is more competitive than [1,3,5] because the first position they differ is at the final number, and 4 is less than 5.

Example 1:

Input: nums = [3,5,2,6], k = 2
Output: [2,6]
Explanation: Among the set of every possible subsequence: {[3,5], [3,2], [3,6], [5,2], [5,6], [2,6]}, [2,6] is the most competitive.

Example 2:

Input: nums = [2,4,3,3,5,4,9,6], k = 4
Output: [2,3,3,4]

Constraints:

1 <= nums.length <= 10⁵
0 <= nums[i] <= 10⁹
1 <= k <= nums.length

Solution: Stack

Use a stack to track the best solution so far, pop if the current number is less than the top of the stack and there are sufficient numbers left. Then push the current number to the stack if not full.

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

C++

// Author: Huahua

class Solution {

public:

vector<int> mostCompetitive(vector<int>& nums, int k) {

const int n = nums.size();

vector<int> ans(k);

int c = 0;

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

while (c && ans[c - 1] > nums[i] && c + n - i - 1 >= k)

--c;

if (c < k) ans[c++] = nums[i];

}

return ans;

}

};

Java

// Author: Huahua

class Solution {

public int[] mostCompetitive(int[] nums, int k) {

int n = nums.length;

int[] ans = new int[k];

int c = 0;

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

while (c > 0 && ans[c - 1] > nums[i] && c + n - i - 1 >= k)

--c;

if (c < k) ans[c++] = nums[i];

}

return ans;

}

Python3

# Author: Huahua

class Solution:

def mostCompetitive(self, nums: List[int], k: int) -> List[int]:

ans = [None] * k

n = len(nums)

c = 0

for i, x in enumerate(nums):

while c and ans[c - 1] > x and c + n - i - 1 >= k:

c -= 1

if c < k:

ans[c] = x

c += 1

return ans

花花酱 LeetCode 1609. Even Odd Tree

By zxi on October 4, 2020

A binary tree is named Even-Odd if it meets the following conditions:

The root of the binary tree is at level index 0, its children are at level index 1, their children are at level index 2, etc.
For every even-indexed level, all nodes at the level have odd integer values in strictly increasing order (from left to right).
For every odd-indexed level, all nodes at the level have even integer values in strictly decreasing order (from left to right).

Given the root of a binary tree, return true if the binary tree is Even-Odd, otherwise return false.

Example 1:

Input: root = [1,10,4,3,null,7,9,12,8,6,null,null,2]
Output: true
Explanation: The node values on each level are:
Level 0: [1]
Level 1: [10,4]
Level 2: [3,7,9]
Level 3: [12,8,6,2]
Since levels 0 and 2 are all odd and increasing, and levels 1 and 3 are all even and decreasing, the tree is Even-Odd.

Example 2:

Input: root = [5,4,2,3,3,7]
Output: false
Explanation: The node values on each level are:
Level 0: [5]
Level 1: [4,2]
Level 2: [3,3,7]
Node values in the level 2 must be in strictly increasing order, so the tree is not Even-Odd.

Example 3:

Input: root = [5,9,1,3,5,7]
Output: false
Explanation: Node values in the level 1 should be even integers.

Example 4:

Input: root = [1]
Output: true

Example 5:

Input: root = [11,8,6,1,3,9,11,30,20,18,16,12,10,4,2,17]
Output: true

Constraints:

The number of nodes in the tree is in the range [1, 10⁵].
1 <= Node.val <= 10⁶

Solution 1: DFS

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

C++

class Solution {

public:

bool isEvenOddTree(TreeNode* root) {

vector<int> vals;

function<bool(TreeNode*, int)> dfs = [&](TreeNode* root, int d) {

if (!root) return true;

if (vals.size() <= d)

vals.push_back(d % 2 == 0 ? -1 : INT_MAX);

int& val = vals[d];

if (d % 2 == 0)

if (root->val % 2 == 0 || root->val <= val) return false;

if (d % 2 == 1)

if (root->val % 2 == 1 || root->val >= val) return false;

val = root->val;

return dfs(root->left, d + 1) && dfs(root->right, d + 1);

};

return dfs(root, 0);

}

};

Python3

# Author: Huahua

class Solution:

def isEvenOddTree(self, root: TreeNode) -> bool:

vals = {}

def dfs(root: TreeNode, d: int) -> bool:

if not root: return True

if d not in vals: vals[d] = 0 if d % 2 == 0 else 10**7

comp = int.__ge__ if d % 2 else int.__le__

if root.val % 2 == d % 2 or comp(root.val, vals[d]): return False

vals[d] = root.val

return dfs(root.left, d + 1) and dfs(root.right, d + 1)

return dfs(root, 0)

Solution 2: BFS

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

Python3

# Author: Huahua

class Solution:

def isEvenOddTree(self, root: TreeNode) -> bool:

q = collections.deque([root])

odd = 1

while q:

prev = 0 if odd else 10**7

for _ in range(len(q)):

root = q.popleft()

if not root: continue

comp = int.__le__ if odd else int.__ge__

if root.val % 2 != odd or comp(root.val, prev): return False

prev = root.val

q += (root.left, root.right)

odd = 1 - odd

return True