Huahua’s Tech Road

花花酱 LeetCode 1910. Remove All Occurrences of a Substring

By zxi on December 24, 2021

Given two strings s and part, perform the following operation on s until all occurrences of the substring part are removed:

Find the leftmost occurrence of the substring part and remove it from s.

Return s after removing all occurrences of part.

A substring is a contiguous sequence of characters in a string.

Example 1:

Input: s = "daabcbaabcbc", part = "abc"
Output: "dab"
Explanation: The following operations are done:
- s = "daabcbaabcbc", remove "abc" starting at index 2, so s = "dabaabcbc".
- s = "dabaabcbc", remove "abc" starting at index 4, so s = "dababc".
- s = "dababc", remove "abc" starting at index 3, so s = "dab".
Now s has no occurrences of "abc".

Example 2:

Input: s = "axxxxyyyyb", part = "xy"
Output: "ab"
Explanation: The following operations are done:
- s = "axxxxyyyyb", remove "xy" starting at index 4 so s = "axxxyyyb".
- s = "axxxyyyb", remove "xy" starting at index 3 so s = "axxyyb".
- s = "axxyyb", remove "xy" starting at index 2 so s = "axyb".
- s = "axyb", remove "xy" starting at index 1 so s = "ab".
Now s has no occurrences of "xy".

Constraints:

1 <= s.length <= 1000
1 <= part.length <= 1000
s and part consists of lowercase English letters.

Solution: Simulation

Time complexity: O(n²/m)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

string removeOccurrences(string s, string part) {

while (true) {

size_t i = s.find(part);

if (i == string::npos) break;

s.erase(i, part.size());

}

return s;

}

};

花花酱 LeetCode 1909. Remove One Element to Make the Array Strictly Increasing

By zxi on December 24, 2021

Given a 0-indexed integer array nums, return true if it can be made strictly increasing after removing exactly one element, or false otherwise. If the array is already strictly increasing, return true.

The array nums is strictly increasing if nums[i - 1] < nums[i] for each index (1 <= i < nums.length).

Example 1:

Input: nums = [1,2,10,5,7]
Output: true
Explanation: By removing 10 at index 2 from nums, it becomes [1,2,5,7].
[1,2,5,7] is strictly increasing, so return true.

Example 2:

Input: nums = [2,3,1,2]
Output: false
Explanation:
[3,1,2] is the result of removing the element at index 0.
[2,1,2] is the result of removing the element at index 1.
[2,3,2] is the result of removing the element at index 2.
[2,3,1] is the result of removing the element at index 3.
No resulting array is strictly increasing, so return false.

Example 3:

Input: nums = [1,1,1]
Output: false
Explanation: The result of removing any element is [1,1].
[1,1] is not strictly increasing, so return false.

Constraints:

2 <= nums.length <= 1000
1 <= nums[i] <= 1000

Solution 1: Brute Force

Enumerate the element to remove and check.

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

C++

// Author: Huahua

class Solution {

public:

bool canBeIncreasing(vector<int>& nums) {

const int n = nums.size();

auto check = [&](int k) {

vector<int> arr(nums);

arr.erase(begin(arr) + k);

for (int i = 1; i < n - 1; ++i)

if (arr[i] <= arr[i - 1]) return false;

return true;

};

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

if (check(i)) return true;

return false;

}

};

C++/O(1) Space

// Author: Huahua

class Solution {

public:

bool canBeIncreasing(vector<int>& nums) {

const int n = nums.size();

auto check = [&](int k) {

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

int j = (i - 1 == k) ? (i - 2) : (i - 1);

if (i != k && j >= 0 && nums[i] <= nums[j])

return false;

}

return true;

};

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

if (check(i)) return true;

return false;

}

};

花花酱 LeetCode 1300. Sum of Mutated Array Closest to Target

By zxi on December 24, 2021

Given an integer array arr and a target value target, return the integer value such that when we change all the integers larger than value in the given array to be equal to value, the sum of the array gets as close as possible (in absolute difference) to target.

In case of a tie, return the minimum such integer.

Notice that the answer is not neccesarilly a number from arr.

Example 1:

Input: arr = [4,9,3], target = 10
Output: 3
Explanation: When using 3 arr converts to [3, 3, 3] which sums 9 and that's the optimal answer.

Example 2:

Input: arr = [2,3,5], target = 10
Output: 5

Example 3:

Input: arr = [60864,25176,27249,21296,20204], target = 56803
Output: 11361

Constraints:

1 <= arr.length <= 10⁴
1 <= arr[i], target <= 10⁵

Solution: Binary Search

Find the smallest number x s.t. sum of the mutated array is >= target. Answer must be either x or x – 1.

Note, the search range should be [0, max(arr))

Time complexity: O(nlogm)
Space complexity: O(1)

C++

// Author: Huahua]

class Solution {

public:

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

int l = 0;

int r = *max_element(begin(arr), end(arr));

int ans = 0;

auto sum = [&](int v) {

int ans = 0;

for (int x : arr)

ans += min(x, v);

return ans;

};

while (l < r) {

int m = l + (r - l) / 2;

if (sum(m) >= target)

r = m;

else

l = m + 1;

}

return abs(sum(l) - target) < abs(sum(l - 1) - target) ? l : l - 1;

}

};

花花酱 LeetCode 1232. Check If It Is a Straight Line

By zxi on December 23, 2021

You are given an array coordinates, coordinates[i] = [x, y], where [x, y] represents the coordinate of a point. Check if these points make a straight line in the XY plane.

Example 1:

Input: coordinates = [[1,2],[2,3],[3,4],[4,5],[5,6],[6,7]]
Output: true

Example 2:

Input: coordinates = [[1,1],[2,2],[3,4],[4,5],[5,6],[7,7]]
Output: false

Constraints:

2 <= coordinates.length <= 1000
coordinates[i].length == 2
-10^4 <= coordinates[i][0], coordinates[i][1] <= 10^4
coordinates contains no duplicate point.

Solution: Slope and Hashset

This is not a easy problem, a few corner cases:

dx == 0
dy == 0
dx < 0

Basically we are counting (dx / gcd(dx, dy), dy / gcd(dx, dy)). We will have only ONE entry if all the points are on the same line.

Time complexity: O(n)
Space complexity: O(1) w/ early exit.

C++

// Author: Huahua

class Solution {

public:

bool checkStraightLine(vector<vector<int>>& coordinates) {

set<pair<int, int>> s;

for (int i = 1; i < coordinates.size(); ++i) {

int dx = coordinates[i][0] - coordinates[0][0];

int dy = coordinates[i][1] - coordinates[0][1];

if (dy == 0)

s.emplace(1, 0);

else if (dx == 0)

s.emplace(0, 1);

else {

if (dx < 0) dx *= -1, dy *= -1;

const int d = gcd(dx, dy);

s.emplace(dx / d, dy / d);

}

if (s.size() > 1) return false;

}

return true;

}

};

花花酱 LeetCode 835. Image Overlap

By zxi on December 23, 2021

You are given two images, img1 and img2, represented as binary, square matrices of size n x n. A binary matrix has only 0s and 1s as values.

We translate one image however we choose by sliding all the 1 bits left, right, up, and/or down any number of units. We then place it on top of the other image. We can then calculate the overlap by counting the number of positions that have a 1 in both images.

Note also that a translation does not include any kind of rotation. Any 1 bits that are translated outside of the matrix borders are erased.

Return the largest possible overlap.

Example 1:

Input: img1 = [[1,1,0],[0,1,0],[0,1,0]], img2 = [[0,0,0],[0,1,1],[0,0,1]]
Output: 3
Explanation: We translate img1 to right by 1 unit and down by 1 unit.

The number of positions that have a 1 in both images is 3 (shown in red).

Example 2:

Input: img1 = [[1]], img2 = [[1]]
Output: 1

Example 3:

Input: img1 = [[0]], img2 = [[0]]
Output: 0

Constraints:

n == img1.length == img1[i].length
n == img2.length == img2[i].length
1 <= n <= 30
img1[i][j] is either 0 or 1.
img2[i][j] is either 0 or 1.

Solution: Hashtable of offsets

Enumerate all pairs of 1 cells (x1, y1) (x2, y2), the key / offset will be ((x1-x2), (y1-y2)), i.e how should we shift the image to have those two cells overlapped. Use a counter to find the most common/best offset.

Time complexity: O(n⁴) Note: this is the same as brute force / simulation method if the matrix is dense.
Space complexity: O(n²)

C++

// Author: Huahua

class Solution {

public:

int largestOverlap(vector<vector<int>>& img1, vector<vector<int>>& img2) {

const int n = img1.size();

unordered_map<int, int> m;

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

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

if (img1[y1][x1])

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

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

if (img2[y2][x2])

++m[(x1 - x2) * 100 + (y1 - y2)];

int ans = 0;

for (const auto [key, count] : m)

ans = max(ans, count);

return ans;

}

};

Huahua's Tech Road

花花酱 LeetCode 1910. Remove All Occurrences of a Substring

Solution: Simulation

C++

花花酱 LeetCode 1909. Remove One Element to Make the Array Strictly Increasing

Solution 1: Brute Force

C++

C++/O(1) Space

花花酱 LeetCode 1300. Sum of Mutated Array Closest to Target

Solution: Binary Search

C++

花花酱 LeetCode 1232. Check If It Is a Straight Line

Solution: Slope and Hashset

C++

花花酱 LeetCode 835. Image Overlap

Solution: Hashtable of offsets

C++