3631. Sort Threats by Severity and Exploitability π
Problem Description
You are given a 2D integer array threats
, where each threats[i] = [ID_i, sev_i, exp_i]
ID_i
: Unique identifier of the threat.sev_i
: Indicates the severity of the threat.exp_i
: Indicates the exploitability of the threat.
The score of a threat i
is defined as:
score = 2 * sev_i + exp_i
Your task is to return threats
sorted in descending order of score.
If multiple threats have the same score, sort them by ascending ID.
Intuition
The problem asks us to sort a list based on a calculated score for each threat. To do this, first compute the score for each threat using the formula score = 2 * sev_i + exp_i
. Then, sort the threats so that those with a higher score appear first. If two threats have the same score, use the ID to break ties by sorting them in ascending order. This approach makes use of the fact that sorting by multiple criteria is straightforward if we combine them properly in the sorting key.
Solution Approach
The solution uses sorting to reorder the threats
array based on the rules described in the problem.
- For each threat in the list, calculate its score using the formula:
score = 2 * sev_i + exp_i
. - Set up a custom sort where:
- The primary key is the negative score (
-(2 * sev_i + exp_i)
), to sort in descending order. - The secondary key is the ID (
ID_i
), to sort in ascending order when scores are equal.
- The primary key is the negative score (
- Use the built-in sort function with a custom key, so for each threat
x
, the key is(-(x[1] * 2 + x[2]), x[0])
. - The sorting is done in-place, but you could also return a new list if needed.
By sorting the array with these keys, we guarantee that threats are ordered from highest to lowest score, and threats with the same score are ordered by increasing ID. This approach is both simple and efficient for the problem's requirements.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Suppose the input is:
threats = [ [101, 3, 6], # ID=101, sev=3, exp=6 --> score=2*3+6=12 [102, 5, 1], # ID=102, sev=5, exp=1 --> score=2*5+1=11 [103, 4, 4], # ID=103, sev=4, exp=4 --> score=2*4+4=12 [104, 2, 8] # ID=104, sev=2, exp=8 --> score=2*2+8=12 ]
Step 1: Compute the score for each threat
[101, 3, 6]
β score = 12[102, 5, 1]
β score = 11[103, 4, 4]
β score = 12[104, 2, 8]
β score = 12
Step 2: Sort the threats
- Primary: Descending by score
- Secondary: Ascending by ID if scores tie
Step 3: Sort based on key (-(2 * sev_i + exp_i), ID_i)
- Key for 101: (-12, 101)
- Key for 102: (-11, 102)
- Key for 103: (-12, 103)
- Key for 104: (-12, 104)
Resulting order: Entries with score 12 come first, sorted by ID for tie-breaking, then entry with score 11.
Final output:
sorted_threats = [ [101, 3, 6], # score 12, ID 101 [103, 4, 4], # score 12, ID 103 [104, 2, 8], # score 12, ID 104 [102, 5, 1] # score 11, ID 102 ]
This shows how the custom sorting works: first by computed score descending, then by ID ascending for tie-breaking.
Solution Implementation
1from typing import List
2
3class Solution:
4 def sortThreats(self, threats: List[List[int]]) -> List[List[int]]:
5 # Sort threats by descending priority (calculated as 2 * threat[1] + threat[2]),
6 # and use threat[0] (id) as a tiebreaker in ascending order.
7 threats.sort(key=lambda threat: (-(threat[1] * 2 + threat[2]), threat[0]))
8 return threats
9
1class Solution {
2 // Sorts the threats array based on a custom scoring formula.
3 public int[][] sortThreats(int[][] threats) {
4 // Sort using a comparator with a custom score calculation.
5 Arrays.sort(threats, (threatA, threatB) -> {
6 // Calculate score for threatA: 2 * threatA[1] + threatA[2]
7 long scoreA = 2L * threatA[1] + threatA[2];
8 // Calculate score for threatB: 2 * threatB[1] + threatB[2]
9 long scoreB = 2L * threatB[1] + threatB[2];
10
11 // If scores are equal, sort by threat ID (threatA[0] and threatB[0]) in ascending order
12 if (scoreA == scoreB) {
13 return Integer.compare(threatA[0], threatB[0]);
14 }
15 // Otherwise, sort by score in descending order
16 return Long.compare(scoreB, scoreA);
17 });
18 // Return the sorted array
19 return threats;
20 }
21}
22
1class Solution {
2public:
3 // Sorts a list of threats using a custom score and returns the sorted threats.
4 vector<vector<int>> sortThreats(vector<vector<int>>& threats) {
5 // Define the custom comparator for sorting
6 sort(threats.begin(), threats.end(), [](const vector<int>& a, const vector<int>& b) {
7 // Compute the score for each threat: 2 * second element + third element
8 long long scoreA = 2LL * a[1] + a[2];
9 long long scoreB = 2LL * b[1] + b[2];
10 // If scores are equal, sort by the first element in ascending order
11 if (scoreA == scoreB) {
12 return a[0] < b[0];
13 }
14 // Otherwise, sort in descending order by score
15 return scoreA > scoreB;
16 });
17 // Return the sorted list
18 return threats;
19 }
20};
21
1/**
2 * Sorts a 2D array of threats based on custom scoring:
3 * - Score = 2 * threat[1] + threat[2]
4 * - Higher scores come first
5 * - If scores are equal, lower threat[0] (id) comes first
6 *
7 * @param threats - An array of arrays, each sub-array is [id, severity, urgency]
8 * @returns The sorted threats (sorted in-place and returned)
9 */
10function sortThreats(threats: number[][]): number[][] {
11 // Custom sorting using the algorithm specified above
12 threats.sort((a: number[], b: number[]) => {
13 // Calculate scores for both threats
14 const scoreA: number = 2 * a[1] + a[2]; // a[1]: severity, a[2]: urgency
15 const scoreB: number = 2 * b[1] + b[2];
16
17 // If scores are equal, sort by ascending id (a[0])
18 if (scoreA === scoreB) {
19 return a[0] - b[0];
20 }
21 // Otherwise, higher score comes first
22 return scoreB - scoreA;
23 });
24 return threats;
25}
26
Time and Space Complexity
The time complexity is O(n \log n)
, where n
is the length of threats
, as the sort()
method uses Timsort with that complexity.
The space complexity is O(\log n)
, which is due to the additional stack space used by Timsort during sorting.
What data structure does Breadth-first search typically uses to store intermediate states?
Recommended Readings
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https assets algo monster recursion jpg You first call Ben and ask
Want a Structured Path to Master System Design Too? Donβt Miss This!