Posts tagged as “sorting”

花花酱 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 2099. Find Subsequence of Length K With the Largest Sum

By zxi on December 12, 2021

You are given an integer array nums and an integer k. You want to find a subsequence of nums of length k that has the largest sum.

Return any such subsequence as an integer array of length k.

A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.

Example 1:

Input: nums = [2,1,3,3], k = 2
Output: [3,3]
Explanation:
The subsequence has the largest sum of 3 + 3 = 6.

Example 2:

Input: nums = [-1,-2,3,4], k = 3
Output: [-1,3,4]
Explanation: 
The subsequence has the largest sum of -1 + 3 + 4 = 6.

Example 3:

Input: nums = [3,4,3,3], k = 2
Output: [3,4]
Explanation:
The subsequence has the largest sum of 3 + 4 = 7. 
Another possible subsequence is [4, 3].

Constraints:

1 <= nums.length <= 1000
-10⁵ <= nums[i] <= 10⁵
1 <= k <= nums.length

Solution 1: Full sorting + Hashtable

Make a copy of the original array, sort it in whole and put k largest elements in a hashtable.

Scan the original array and append the number to the answer array if it’s in the hashtable.

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

C++

// Author: Huahua

class Solution {

public:

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

vector<int> ans;

vector<int> s(nums);

sort(rbegin(s), rend(s));

unordered_map<int, int> m;

for (int i = 0; i < k; ++i) ++m[s[i]];

for (int x : nums)

if (--m[x] >= 0)

ans.push_back(x);

return ans;

}

};

Solution 2: k-th element

Use quick select / partial sort to find the k-th largest element of the array. Any number greater than that must be in the sequence. The tricky part is: what about the pivot itself? We couldn’t include ’em all blindly. Need to figure out how many copies of the pivot is there in the k largest and only include as many as of that in the final answer.

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

C++

// Author: Huahua

class Solution {

public:

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

vector<int> ans;

vector<int> s(nums);

nth_element(begin(s), begin(s) + k - 1, end(s), greater<int>());

const int pivot = s[k - 1];

// How many pivots in the largest k elements.

int left = count(begin(s), begin(s) + k, pivot);

for (size_t i = 0; i != nums.size(); ++i)

if (nums[i] > pivot || (nums[i] == pivot && --left >= 0))

ans.push_back(nums[i]);

return ans;

}

};

花花酱 LeetCode 2089. Find Target Indices After Sorting Array

By zxi on November 28, 2021

You are given a 0-indexed integer array nums and a target element target.

A target index is an index i such that nums[i] == target.

Return a list of the target indices of nums after sorting nums in non-decreasing order. If there are no target indices, return an empty list. The returned list must be sorted in increasing order.

Example 1:

Input: nums = [1,2,5,2,3], target = 2
Output: [1,2]
Explanation: After sorting, nums is [1,2,2,3,5].
The indices where nums[i] == 2 are 1 and 2.

Example 2:

Input: nums = [1,2,5,2,3], target = 3
Output: [3]
Explanation: After sorting, nums is [1,2,2,3,5].
The index where nums[i] == 3 is 3.

Example 3:

Input: nums = [1,2,5,2,3], target = 5
Output: [4]
Explanation: After sorting, nums is [1,2,2,3,5].
The index where nums[i] == 5 is 4.

Example 4:

Input: nums = [1,2,5,2,3], target = 4
Output: []
Explanation: There are no elements in nums with value 4.

Constraints:

1 <= nums.length <= 100
1 <= nums[i], target <= 100

Solution: Sorting

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

C++

// Author: Huahua

class Solution {

public:

vector<int> targetIndices(vector<int>& nums, int target) {

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

vector<int> ans;

for (int i = 0; i < nums.size(); ++i)

if (nums[i] == target) ans.push_back(i);

return ans;

}

};

花花酱 LeetCode 1727. Largest Submatrix With Rearrangements

By zxi on January 17, 2021

You are given a binary matrix matrix of size m x n, and you are allowed to rearrange the columns of the matrix in any order.

Return the area of the largest submatrix within matrix where every element of the submatrix is 1 after reordering the columns optimally.

Example 1:

Input: matrix = [[0,0,1],[1,1,1],[1,0,1]]
Output: 4
Explanation: You can rearrange the columns as shown above.
The largest submatrix of 1s, in bold, has an area of 4.

Example 2:

Input: matrix = [[1,0,1,0,1]]
Output: 3
Explanation: You can rearrange the columns as shown above.
The largest submatrix of 1s, in bold, has an area of 3.

Example 3:

Input: matrix = [[1,1,0],[1,0,1]]
Output: 2
Explanation: Notice that you must rearrange entire columns, and there is no way to make a submatrix of 1s larger than an area of 2.

Example 4:

Input: matrix = [[0,0],[0,0]]
Output: 0
Explanation: As there are no 1s, no submatrix of 1s can be formed and the area is 0.

Constraints:

m == matrix.length
n == matrix[i].length
1 <= m * n <= 10⁵
matrix[i][j] is 0 or 1.

Solution: DP + Sorting

Preprocess each column, for col j, matrix[i][j] := length consecutive ones of col j.

[0,0,1]    [0,0,1]
[1,1,1] => [1,1,2]
[1,0,1]    [2,0,3]

Then we enumerate ending row, for each ending row i, we sort row[i] in deceasing order

e.g. i = 2

[0,0,1]                  [-,-,-]
[1,1,2] sort by row 2 => [-,-,-]
[2,0,3]                  [3,2,0]

row[2][1] = 3, means there is a 3×1 all ones sub matrix, area = 3
row[2][2] = 2, means there is a 2×2 all ones sub matrix, area = 4.

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

C++

// Author: Huahua

class Solution {

public:

int largestSubmatrix(vector<vector<int>>& matrix) {

const int m = matrix.size();

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

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

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

if (matrix[i][j]) matrix[i][j] += matrix[i - 1][j];

int ans = 0;

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

sort(rbegin(matrix[i]), rend(matrix[i]));

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

ans = max(ans, (j + 1) * matrix[i][j]);

}

return ans;

}

};

花花酱 LeetCode 1707. Maximum XOR With an Element From Array

By zxi on December 27, 2020

You are given an array nums consisting of non-negative integers. You are also given a queries array, where queries[i] = [x_i, m_i].

The answer to the i^th query is the maximum bitwise XOR value of x_i and any element of nums that does not exceed m_i. In other words, the answer is max(nums[j] XOR x_i) for all j such that nums[j] <= m_i. If all elements in nums are larger than m_i, then the answer is -1.

Return an integer array answer where answer.length == queries.length and answer[i] is the answer to the i^th query.

Example 1:

Input: nums = [0,1,2,3,4], queries = [[3,1],[1,3],[5,6]]
Output: [3,3,7]
Explanation:
1) 0 and 1 are the only two integers not greater than 1. 0 XOR 3 = 3 and 1 XOR 3 = 2. The larger of the two is 3.
2) 1 XOR 2 = 3.
3) 5 XOR 2 = 7.

Example 2:

Input: nums = [5,2,4,6,6,3], queries = [[12,4],[8,1],[6,3]]
Output: [15,-1,5]

Constraints:

1 <= nums.length, queries.length <= 10⁵
queries[i].length == 2
0 <= nums[j], x_i, m_i <= 10⁹

Solution: Trie on the fly

We can build the trie on the fly by sorting nums in ascending order and queries by its limit, insert nums into the trie up the limit.

Time complexity: O(nlogn + QlogQ)
Space complexity: O(n)

C++

// Author: Huahua

class Trie {

public:

Trie(): children{nullptr, nullptr} {}

Trie* children[2];

};

class Solution {

public:

vector<int> maximizeXor(vector<int>& nums, vector<vector<int>>& queries) {

const int n = nums.size();

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

const int Q = queries.size();

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

queries[i].push_back(i);

sort(begin(queries), end(queries), [](const auto& q1, const auto& q2) {

return q1[1] < q2[1];

});

Trie root;

auto insert = [&](int num) {

Trie* node = &root;

for (int i = 31; i >= 0; --i) {

int bit = (num >> i) & 1;

if (!node->children[bit])

node->children[bit] = new Trie();

node = node->children[bit];

}

};

auto query = [&](int num) {

Trie* node = &root;

int sum = 0;

for (int i = 31; i >= 0; --i) {

if (!node) return -1;

int bit = (num >> i) & 1;

if (node->children[1 - bit]) {

sum |= (1 << i);

node = node->children[1 - bit];

} else {

node = node->children[bit];

}

return sum;

};

vector<int> ans(Q);

int i = 0;

for (const auto& q : queries) {

while (i < n && nums[i] <= q[1]) insert(nums[i++]);

ans[q[2]] = query(q[0]);

}

return ans;

}

};