Huahua’s Tech Road

花花酱 LeetCode 1913. Maximum Product Difference Between Two Pairs

By zxi on December 24, 2021

The product difference between two pairs (a, b) and (c, d) is defined as (a * b) - (c * d).

For example, the product difference between (5, 6) and (2, 7) is (5 * 6) - (2 * 7) = 16.

Given an integer array nums, choose four distinct indices w, x, y, and z such that the product difference between pairs (nums[w], nums[x]) and (nums[y], nums[z]) is maximized.

Return the maximum such product difference.

Example 1:

Input: nums = [5,6,2,7,4]
Output: 34
Explanation: We can choose indices 1 and 3 for the first pair (6, 7) and indices 2 and 4 for the second pair (2, 4).
The product difference is (6 * 7) - (2 * 4) = 34.

Example 2:

Input: nums = [4,2,5,9,7,4,8]
Output: 64
Explanation: We can choose indices 3 and 6 for the first pair (9, 8) and indices 1 and 5 for the second pair (2, 4).
The product difference is (9 * 8) - (2 * 4) = 64.

Constraints:

4 <= nums.length <= 10⁴
1 <= nums[i] <= 10⁴

Solution: Greedy

Since all the numbers are positive, we just need to find the largest two numbers as the first pair and smallest two numbers are the second pair.

Time complexity: O(nlogn) / sorting, O(n) / finding min/max elements.
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int maxProductDifference(vector<int>& nums) {

const int n = nums.size();

sort(begin(nums), end(nums));

return nums[n - 1] * nums[n - 2] - nums[0] * nums[1];

}

};

Python3

# Author: Huahua

class Solution:

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

nums.sort()

return nums[-1] * nums[-2] - nums[0] * nums[1]

花花酱 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;

}

};

Huahua's Tech Road

花花酱 LeetCode 1913. Maximum Product Difference Between Two Pairs

Solution: Greedy

C++

Python3

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