493. Reverse Pairs LeetCode Solution
In this guide, you will get 493. Reverse Pairs LeetCode Solution with the best time and space complexity. The solution to Reverse Pairs problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Table of Contents
- Problem Statement
- Complexity Analysis
- Reverse Pairs solution in C++
- Reverse Pairs solution in Java
- Reverse Pairs solution in Python
- Additional Resources
Problem Statement of Reverse Pairs
Given an integer array nums, return the number of reverse pairs in the array.
A reverse pair is a pair (i, j) where:
0 <= i < j 2 * nums[j].
Example 1:
Input: nums = [1,3,2,3,1]
Output: 2
Explanation: The reverse pairs are:
(1, 4) –> nums[1] = 3, nums[4] = 1, 3 > 2 * 1
(3, 4) –> nums[3] = 3, nums[4] = 1, 3 > 2 * 1
Example 2:
Input: nums = [2,4,3,5,1]
Output: 3
Explanation: The reverse pairs are:
(1, 4) –> nums[1] = 4, nums[4] = 1, 4 > 2 * 1
(2, 4) –> nums[2] = 3, nums[4] = 1, 3 > 2 * 1
(3, 4) –> nums[3] = 5, nums[4] = 1, 5 > 2 * 1
Constraints:
1 <= nums.length <= 5 * 104
-231 <= nums[i] <= 231 – 1
Complexity Analysis
- Time Complexity: O(n\log n)
- Space Complexity: O(n)
493. Reverse Pairs LeetCode Solution in C++
class FenwickTree {
public:
FenwickTree(int n) : sums(n + 1) {}
void add(int i, int delta) {
while (i < sums.size()) {
sums[i] += delta;
i += lowbit(i);
}
}
int get(int i) const {
int sum = 0;
while (i > 0) {
sum += sums[i];
i -= lowbit(i);
}
return sum;
}
private:
vector<int> sums;
static inline int lowbit(int i) {
return i & -i;
}
};
class Solution {
public:
int reversePairs(vector<int>& nums) {
int ans = 0;
const unordered_map<long, int> ranks = getRanks(nums);
FenwickTree tree(ranks.size());
for (int i = nums.size() - 1; i >= 0; --i) {
const long num = nums[i];
ans += tree.get(ranks.at(num) - 1);
tree.add(ranks.at(num * 2), 1);
}
return ans;
}
private:
unordered_map<long, int> getRanks(const vector<int>& nums) {
unordered_map<long, int> ranks;
set<long> sorted(nums.begin(), nums.end());
for (const long num : nums)
sorted.insert(num * 2);
int rank = 0;
for (const long num : sorted)
ranks[num] = ++rank;
return ranks;
}
};
/* code provided by PROGIEZ */493. Reverse Pairs LeetCode Solution in Java
class SegmentTree {
public:
explicit SegmentTree(const vector<int>& nums) : n(nums.size()), tree(n * 4) {
build(nums, 0, 0, n - 1);
}
// Adds val to nums[i].
void add(int i, int val) {
add(0, 0, n - 1, i, val);
}
// Returns sum(nums[i..j]).
int query(int i, int j) const {
return query(0, 0, n - 1, i, j);
}
private:
const int n; // the size of the input array
vector<int> tree; // the segment tree
void build(const vector<int>& nums, int treeIndex, int lo, int hi) {
if (lo == hi) {
tree[treeIndex] = nums[lo];
return;
}
const int mid = (lo + hi) / 2;
build(nums, 2 * treeIndex + 1, lo, mid);
build(nums, 2 * treeIndex + 2, mid + 1, hi);
tree[treeIndex] = merge(tree[2 * treeIndex + 1], tree[2 * treeIndex + 2]);
}
void add(int treeIndex, int lo, int hi, int i, int val) {
if (lo == hi) {
tree[treeIndex] += val;
return;
}
const int mid = (lo + hi) / 2;
if (i <= mid)
add(2 * treeIndex + 1, lo, mid, i, val);
else
add(2 * treeIndex + 2, mid + 1, hi, i, val);
tree[treeIndex] = merge(tree[2 * treeIndex + 1], tree[2 * treeIndex + 2]);
}
int query(int treeIndex, int lo, int hi, int i, int j) const {
if (i <= lo && hi <= j) // [lo, hi] lies completely inside [i, j].
return tree[treeIndex];
if (j < lo || hi < i) // [lo, hi] lies completely outside [i, j].
return 0;
const int mid = (lo + hi) / 2;
return merge(query(treeIndex * 2 + 1, lo, mid, i, j),
query(treeIndex * 2 + 2, mid + 1, hi, i, j));
}
int merge(int left, int right) const {
return left + right;
}
};
class Solution {
public:
int reversePairs(vector<int>& nums) {
int ans = 0;
const unordered_map<long, int> ranks = getRanks(nums);
SegmentTree tree(vector<int>(ranks.size() + 1));
for (int i = nums.size() - 1; i >= 0; --i) {
const long num = nums[i];
ans += tree.query(0, ranks.at(num) - 1);
tree.add(ranks.at(num * 2), 1);
}
return ans;
}
private:
unordered_map<long, int> getRanks(const vector<int>& nums) {
unordered_map<long, int> ranks;
set<long> sorted(nums.begin(), nums.end());
for (const long num : nums)
sorted.insert(num * 2);
int rank = 0;
for (const long num : sorted)
ranks[num] = ++rank;
return ranks;
}
};
// code provided by PROGIEZ493. Reverse Pairs LeetCode Solution in Python
struct SegmentTreeNode {
int lo;
int hi;
int sum;
SegmentTreeNode* left;
SegmentTreeNode* right;
SegmentTreeNode(int lo, int hi, int sum, SegmentTreeNode* left = nullptr,
SegmentTreeNode* right = nullptr)
: lo(lo), hi(hi), sum(sum), left(left), right(right) {}
~SegmentTreeNode() {
delete left;
delete right;
left = nullptr;
right = nullptr;
}
};
class SegmentTree {
public:
explicit SegmentTree(const vector<int>& nums)
: root(build(nums, 0, nums.size() - 1)) {}
void add(int i, int val) {
add(root.get(), i, val);
}
int query(int i, int j) const {
return query(root.get(), i, j);
}
private:
std::unique_ptr<SegmentTreeNode> root;
SegmentTreeNode* build(const vector<int>& nums, int lo, int hi) const {
if (lo == hi)
return new SegmentTreeNode(lo, hi, nums[lo]);
const int mid = (lo + hi) / 2;
auto left = build(nums, lo, mid);
auto right = build(nums, mid + 1, hi);
return new SegmentTreeNode(lo, hi, left->sum + right->sum, left, right);
}
void add(SegmentTreeNode* root, int i, int val) {
if (root->lo == i && root->hi == i) {
root->sum += val;
return;
}
const int mid = (root->lo + root->hi) / 2;
if (i <= mid)
add(root->left, i, val);
else
add(root->right, i, val);
root->sum = root->left->sum + root->right->sum;
}
int query(SegmentTreeNode* root, int i, int j) const {
if (root->lo == i && root->hi == j)
return root->sum;
const int mid = (root->lo + root->hi) / 2;
if (j <= mid)
return query(root->left, i, j);
if (i > mid)
return query(root->right, i, j);
return merge(query(root->left, i, mid), query(root->right, mid + 1, j));
}
int merge(int left, int right) const {
return left + right;
}
};
class Solution {
public:
int reversePairs(vector<int>& nums) {
int ans = 0;
const unordered_map<long, int> ranks = getRanks(nums);
SegmentTree tree(vector<int>(ranks.size() + 1));
for (int i = nums.size() - 1; i >= 0; --i) {
const long num = nums[i];
ans += tree.query(0, ranks.at(num) - 1);
tree.add(ranks.at(num * 2), 1);
}
return ans;
}
private:
unordered_map<long, int> getRanks(const vector<int>& nums) {
unordered_map<long, int> ranks;
set<long> sorted(nums.begin(), nums.end());
for (const long num : nums)
sorted.insert(num * 2);
int rank = 0;
for (const long num : sorted)
ranks[num] = ++rank;
return ranks;
}
};
# code by PROGIEZAdditional Resources
- Explore all LeetCode problem solutions at Progiez here
- Explore all problems on LeetCode website here
Happy Coding! Keep following PROGIEZ for more updates and solutions.