Problem Link - Pair Sort Version 3 Practice Problem in Jump from 2* to 3*
Problem Statement:
To solve this problem, we need to sort pairs of two arrays, A and B, based on specific conditions:
- Primary Sort: Sort the pairs in decreasing order based on the second element (i.e., the corresponding element from array B).
- Secondary Sort: If the second elements are the same, sort those pairs by the first element (i.e., the corresponding element from array A) in increasing order.
Approach:
Understanding the Sorting Criteria:
- The first thing to understand is that we need a custom sorting order for these pairs.
- Given that sorting based on the second element is the primary requirement, we will prioritize sorting by B_i first, ensuring that the pairs with higher values of B_i come before the ones with lower values.
- If two pairs have the same second element, then the first element A_i should be considered, and we sort those pairs in increasing order based on A_i.
Data Representation:
- We will create pairs of (A_i,B_i), where
iranges from0toN−1. These pairs will be stored as a vector of pair<int, int>, which is a standard C++ data structure for representing pairs of integers.
Sorting Using Custom Comparator:
- C++ allows us to define custom sorting criteria by passing a comparison function to the sort function. In this case, the comparator should compare the second elements of the pairs in descending order, and in case of a tie, it should compare the first elements in ascending order.
Complexity:
- Time Complexity: The time complexity is
O(N log N), whereNis the number of pairs. This is because the main operation is sorting the pairs, which takesO(N log N). - Space Complexity: The space complexity is
O(N)due to the storage required for the vector of pairs.