Sort Threats

14
0

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, a and b. In each row, index 0 contains the ID, index 1 contains severity, and index 2 contains exploitability.

  • For each comparison, it calculates scoreA = 2 × a[1] + a[2] and scoreB = 2 × b[1] + b[2].

  • The comparator uses scoreA > scoreB to decide whether a comes before b when the scores differ. When they are equal, it uses a[0] < b[0].

  • The built-in sorting function receives this comparator and rearranges the rows of threats according to its comparison results.

  • After sorting finishes, the algorithm returns the updated threats array.

Note: In Python, instead of a pairwise comparator, this logic is implemented using a key lambda function returning (-(2 * row[1] + row[2]), row[0]) to achieve the exact same ordering.

Dry Run

Sort Threats - Custom Sorting

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 code
int 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.

SortingTCS NQT

Read Similar Blogs

Comments0