Problem Statement
You are given a 2D integer array threats. Each row contains three values:
ID: A unique identifier for the threat.sev: The severity of the threat.exp: The exploitability of the threat.
The score of a threat is: score = 2 × sev + exp
Return the threats sorted by decreasing score. If two threats have the same score, place the threat with the smaller ID first.
Example 1
Input: threats = [[101, 2, 3], [102, 3, 2], [103, 3, 3]]
Output: [[103, 3, 3], [102, 3, 2], [101, 2, 3]]
Explanation: The scores of threats 101, 102, and 103 are 7, 8, and 9. Sorting by decreasing score places them in the order 103, 102, 101.
Example 2
Input: threats = [[101, 4, 1], [103, 1, 5], [102, 1, 5]]
Output: [[101, 4, 1], [102, 1, 5], [103, 1, 5]]
Explanation: Threat 101 has a score of 9, so it comes first. Threats 103 and 102 both have a score of 7. Since 102 is the smaller ID, it comes before 103.
Approach
The sorting order depends on two values: the score and the ID. A custom comparator allows the built-in sorting function to follow these rules.
When comparing two threats, the comparator calculates their scores. If the scores differ, it places the threat with the higher score first. Otherwise, it compares their IDs and places the threat with the smaller ID first. This handles both rules while keeping each threat’s details together.
Algorithm
A custom comparator takes two threat rows,
aandb. In each row, index0contains the ID, index1contains severity, and index2contains exploitability.For each comparison, it calculates
scoreA = 2 × a[1] + a[2]andscoreB = 2 × b[1] + b[2].The comparator uses
scoreA > scoreBto decide whetheracomes beforebwhen the scores differ. When they are equal, it usesa[0] < b[0].The built-in sorting function receives this comparator and rearranges the rows of
threatsaccording to its comparison results.After sorting finishes, the algorithm returns the updated
threatsarray.
Note: In Python, instead of a pairwise comparator, this logic is implemented using a
keylambda function returning(-(2 * row[1] + row[2]), row[0])to achieve the exact same ordering.
Dry Run
Sort Threats - Custom Sorting
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Sort threats by highest score, breaking ties by lowest ID. vector<vector<int>> sortThreats(vector<vector<int>>& threats) { // Sort threats by score, keeping the higher score first. sort(threats.begin(), threats.end(), [](const vector<int>& first, const vector<int>& second) { // Calculate the score for both threats. long long firstScore = 2LL * first[1] + first[2]; long long secondScore = 2LL * second[1] + second[2]; if (firstScore != secondScore) { return firstScore > secondScore; } // If scores are equal, compare their IDs. return first[0] < second[0]; }); return threats; }};// Driver codeint main() { vector<vector<int>> threats = { {101, 2, 3}, {102, 3, 2}, {103, 3, 3} }; Solution solution; vector<vector<int>> result = solution.sortThreats(threats); cout << "["; for (size_t i = 0; i < result.size(); ++i) { if (i > 0) cout << ", "; cout << "[" << result[i][0] << ", " << result[i][1] << ", " << result[i][2] << "]"; } cout << "]\n"; return 0;}Complexity Analysis
Time Complexity: O(N log N), where N is the number of threats. Sorting the threats takes O(N log N) time, and calculating the score and comparing two threats takes O(1) time per comparison.
Space Complexity: O(log N) on average for the sorting recursion stack. The sorting algorithm may require additional temporary space depending on the implementation.
Interview follow-up Questions
Use stable_sort() with a comparator that compares only scores. This preserves the original order of threats having equal scores.
Be the first to add a comment.