Huahua’s Tech Road

花花酱 LeetCode 1726. Tuple with Same Product

By zxi on January 17, 2021

Given an array nums of distinct positive integers, return the number of tuples (a, b, c, d) such that a * b = c * d where a, b, c, and d are elements of nums, and a != b != c != d.

Example 1:

Input: nums = [2,3,4,6]
Output: 8
Explanation: There are 8 valid tuples:
(2,6,3,4) , (2,6,4,3) , (6,2,3,4) , (6,2,4,3)
(3,4,2,6) , (4,3,2,6) , (3,4,6,2) , (4,3,6,2)

Example 2:

Input: nums = [1,2,4,5,10]
Output: 16
Explanation: There are 16 valids tuples:
(1,10,2,5) , (1,10,5,2) , (10,1,2,5) , (10,1,5,2)
(2,5,1,10) , (2,5,10,1) , (5,2,1,10) , (5,2,10,1)
(2,10,4,5) , (2,10,5,4) , (10,2,4,5) , (10,2,4,5)
(4,5,2,10) , (4,5,10,2) , (5,4,2,10) , (5,4,10,2)

Example 3:

Input: nums = [2,3,4,6,8,12]
Output: 40

Example 4:

Input: nums = [2,3,5,7]
Output: 0

Constraints:

1 <= nums.length <= 1000
1 <= nums[i] <= 10⁴
All elements in nums are distinct.

Solution: HashTable

Similar idea to 花花酱 LeetCode 1. Two Sum

Use a hashtable to store all the pair product counts.

Enumerate all possible pairs, increase the answer by the same product counts * 8.

Why time 8? C(4,1) * C(1,1) * C(2,1) * C(1,1)

For pair one AxB, A can be placed at any position in a four tuple, B’s position is then fixed. For another pair CxD, C has two positions to choose from, D is fixed.

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

C++

// Author: Huahua

class Solution {

public:

int tupleSameProduct(vector<int>& nums) {

const int n = nums.size();

unordered_map<int, int> m;

int ans = 0;

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

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

ans += 8 * m[nums[i] * nums[j]]++;

return ans;

}

};

花花酱 LeetCode 1725. Number Of Rectangles That Can Form The Largest Square

By zxi on January 17, 2021

You are given an array rectangles where rectangles[i] = [l_i, w_i] represents the i^th rectangle of length l_i and width w_i.

You can cut the i^th rectangle to form a square with a side length of k if both k <= l_i and k <= w_i. For example, if you have a rectangle [4,6], you can cut it to get a square with a side length of at most 4.

Let maxLen be the side length of the largest square you can obtain from any of the given rectangles.

Return the number of rectangles that can make a square with a side length of maxLen.

Example 1:

Input: rectangles = [[5,8],[3,9],[5,12],[16,5]]
Output: 3
Explanation: The largest squares you can get from each rectangle are of lengths [5,3,5,5].
The largest possible square is of length 5, and you can get it out of 3 rectangles.

Example 2:

Input: rectangles = [[2,3],[3,7],[4,3],[3,7]]
Output: 3

Constraints:

1 <= rectangles.length <= 1000
rectangles[i].length == 2
1 <= l_i, w_i <= 10⁹
l_i != w_i

Solution: Running Max of Shortest Edge

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

C++

// Author: Huahua

class Solution {

public:

int countGoodRectangles(vector<vector<int>>& rectangles) {

int cur = 0;

int ans = 0;

for (const auto& r : rectangles) {

if (min(r[0], r[1]) > cur) {

cur = min(r[0], r[1]);

ans = 0;

}

if (min(r[0], r[1]) == cur) ++ans;

}

return ans;

}

};

花花酱 LeetCode 1723. Find Minimum Time to Finish All Jobs

By zxi on January 10, 2021

You are given an integer array jobs, where jobs[i] is the amount of time it takes to complete the i^th job.

There are k workers that you can assign jobs to. Each job should be assigned to exactly one worker. The working time of a worker is the sum of the time it takes to complete all jobs assigned to them. Your goal is to devise an optimal assignment such that the maximum working time of any worker is minimized.

Return the minimum possible maximum working time of any assignment.

Example 1:

Input: jobs = [3,2,3], k = 3
Output: 3
Explanation: By assigning each person one job, the maximum time is 3.

Example 2:

Input: jobs = [1,2,4,7,8], k = 2
Output: 11
Explanation: Assign the jobs the following way:
Worker 1: 1, 2, 8 (working time = 1 + 2 + 8 = 11)
Worker 2: 4, 7 (working time = 4 + 7 = 11)
The maximum working time is 11.

Constraints:

1 <= k <= jobs.length <= 12
1 <= jobs[i] <= 10⁷

Solution 1: All subsets

dp[i][t] := min of max working time by assigning a subset of jobs s to the first i workers.

dp[i][t] = min{max(dp[i – 1][s], cost[s ^ t])} where s is a subset of t.

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

C++

// Author: Huahua

class Solution {

public:

int minimumTimeRequired(vector<int>& jobs, int k) {

const int n = jobs.size();

int dp[13][4096];

memset(dp, 0x7f, sizeof(dp));

dp[0][0] = 0;

vector<int> cost(1 << n);

for (int t = 0; t < 1 << n; ++t) {

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

if (t >> j & 1) cost[t] += jobs[j];

dp[1][t] = cost[t]; // do jobs t by one worker

}

for (int i = 2; i <= k; ++i)

for (int t = 0; t < 1 << n; ++t)

for (int s = t; s; s = (s - 1) & t)

dp[i][t] = min(dp[i][t], max(dp[i - 1][s], cost[t ^ s]));

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

}

};

Solution 2: Search + Pruning

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

C++

class Solution {

public:

int minimumTimeRequired(vector<int>& jobs, int k) {

vector<int> times(k);

int ans = INT_MAX;

function<void(int, int)> dfs = [&](int i, int cur) {

if (cur >= ans) return;

if (i == jobs.size()) {

ans = cur;

return;

}

unordered_set<int> seen;

for (int j = 0; j < k; ++j) {

if (!seen.insert(times[j]).second) continue;

times[j] += jobs[i];

dfs(i + 1, max(cur, times[j]));

times[j] -= jobs[i];

}

};

sort(rbegin(jobs), rend(jobs));

dfs(0, 0);

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;

}

};

Huahua's Tech Road

花花酱 LeetCode 1726. Tuple with Same Product

Solution: HashTable

C++

花花酱 LeetCode 1725. Number Of Rectangles That Can Form The Largest Square

Solution: Running Max of Shortest Edge

C++

花花酱 LeetCode 1723. Find Minimum Time to Finish All Jobs

Solution 1: All subsets

C++

Solution 2: Search + Pruning

C++

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

Solution: Union Find

C++

花花酱 LeetCode 1721. Swapping Nodes in a Linked List

Solution:

C++