LeetCode 3631 - Sort Threats by Severity and Exploitability
The problem gives a list of threats, where each threat is represented as a triplet [IDi, sevi, expi]. Each threat has a unique identifier, a severity value, and an exploitability value.
Difficulty: 🟡 Medium
Topics: Array, Sorting
Solution
Problem Understanding
The problem gives a list of threats, where each threat is represented as a triplet [IDi, sevi, expi]. Each threat has a unique identifier, a severity value, and an exploitability value. From these two attributes, a derived metric called score is defined as score = 2 × severity + exploitability.
The task is to reorder the entire list of threats based on this computed score in descending order. If two or more threats share the same score, they must be ordered by their ID in ascending order.
The input is a 2D array with up to 10^5 entries, which immediately implies that any solution worse than O(n log n) will likely be too slow. Each ID is unique, so there is no need to handle duplicate identifiers, but there can be duplicate scores, which is why the tie-break rule is necessary.
Edge cases include scenarios where all threats have identical scores, where only one threat exists, or where severity and exploitability values are large enough that the score computation must be done carefully without overflow concerns in languages with fixed integer sizes (though Python handles this safely). Another subtle case is ensuring stable tie-breaking by ID when scores match.
Approaches
The brute-force approach conceptually computes the score for each element and then repeatedly selects the maximum remaining element, placing it into the result. This can be implemented using selection sort or by repeatedly scanning the list for the next best candidate. While correct, this approach is inefficient because each selection requires scanning the remaining elements, leading to quadratic behavior.
The optimal approach observes that the score for each element can be computed independently in constant time, and once computed, the problem reduces to a standard sorting problem with a custom comparator. Sorting algorithms like Timsort or mergesort variants handle this efficiently in O(n log n), which is appropriate for the input size constraint of up to 100,000 elements. The tie-breaking condition can be incorporated directly into the sorting key.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force (repeated selection) | O(n^2) | O(1) | Repeatedly find max score by scanning remaining elements |
| Optimal (sorting with key) | O(n log n) | O(n) | Compute score and sort using composite key |
Algorithm Walkthrough
The optimal algorithm works by transforming each threat into a sortable representation using its derived score and ID, then sorting the list according to the required ordering rules.
- First, iterate through each threat in the input list and compute its score using the formula
score = 2 × severity + exploitability. This step is necessary because sorting directly on raw attributes would require recomputing the score multiple times during comparisons, which is unnecessary overhead. - For each threat, create a sorting key that captures both required ordering rules. Since we want descending order of score, we store the negative of the score. For tie-breaking, we use the ID in ascending order, which naturally fits as-is.
- Store each threat along with its computed key in a structure suitable for sorting, typically as a tuple
(−score, ID, original_threat). - Sort the entire collection using the key. The sorting algorithm will first prioritize higher scores because of the negation, and for equal scores, it will automatically order by smaller IDs first.
- After sorting, extract the original threat arrays from the sorted structure and return them in order.
The reason this works is that sorting by a composite key enforces a strict total ordering over all elements. By encoding descending score as a negative value and ascending ID as a natural value, we transform the problem into lexicographic sorting, which guarantees correctness and consistency.
Python Solution
from typing import List
class Solution:
def sortThreats(self, threats: List[List[int]]) -> List[List[int]]:
decorated = []
for tid, sev, exp in threats:
score = 2 * sev + exp
decorated.append((-score, tid, [tid, sev, exp]))
decorated.sort()
return [item[2] for item in decorated]
The implementation first builds a list of decorated tuples where each threat is paired with its computed score and ID in a form suitable for sorting. The negative score ensures descending order when Python performs ascending sort. After sorting, the original threat structures are extracted in the newly ordered sequence.
Go Solution
import "sort"
func sortThreats(threats [][]int) [][]int {
type item struct {
id int
score int
raw []int
}
n := len(threats)
arr := make([]item, n)
for i := 0; i < n; i++ {
id := threats[i][0]
sev := threats[i][1]
exp := threats[i][2]
score := 2*sev + exp
arr[i] = item{
id: id,
score: score,
raw: threats[i],
}
}
sort.Slice(arr, func(i, j int) bool {
if arr[i].score == arr[j].score {
return arr[i].id < arr[j].id
}
return arr[i].score > arr[j].score
})
result := make([][]int, n)
for i := 0; i < n; i++ {
result[i] = arr[i].raw
}
return result
}
In the Go implementation, a struct is used to group each threat with its computed score and ID. This makes the comparator logic in sort.Slice clearer and avoids recomputing the score multiple times. The sorting function explicitly encodes the descending score order and ascending ID tie-break rule. Go’s slice-based sorting is stable enough for this usage, but correctness here relies entirely on the comparator logic.
Worked Examples
For the input [[101,2,3],[102,3,2],[103,3,3]], the computed scores are 7, 8, and 9 respectively.
Initially, the decorated list becomes:
| ID | Severity | Exploitability | Score |
|---|---|---|---|
| 101 | 2 | 3 | 7 |
| 102 | 3 | 2 | 8 |
| 103 | 3 | 3 | 9 |
After converting to sort keys:
[(−7,101), (−8,102), (−9,103)]
Sorting places the most negative score first, resulting in order by score 9, 8, 7. The final output is [[103,3,3],[102,3,2],[101,2,3]].
For the second example [[101,4,1],[103,1,5],[102,1,5]], the scores are 9, 7, and 7.
The key transformation becomes:
[(−9,101), (−7,103), (−7,102)]
After sorting, the equal score group 7 is ordered by ID, producing 102 before 103. The final output is [[101,4,1],[102,1,5],[103,1,5]].
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n log n) | Dominated by sorting n threats using a custom comparator or key |
| Space | O(n) | Additional storage for decorated structures used during sorting |
The computation of scores is linear, but sorting dominates overall runtime. The auxiliary space is linear due to storing decorated tuples or structs alongside the original input references.
Test Cases
# provided example 1
assert Solution().sortThreats([[101,2,3],[102,3,2],[103,3,3]]) == [[103,3,3],[102,3,2],[101,2,3]]
# provided example 2
assert Solution().sortThreats([[101,4,1],[103,1,5],[102,1,5]]) == [[101,4,1],[102,1,5],[103,1,5]]
# single element
assert Solution().sortThreats([[1,10,10]]) == [[1,10,10]]
# all equal score, tie-break by ID
assert Solution().sortThreats([[3,1,1],[1,1,1],[2,1,1]]) == [[1,1,1],[2,1,1],[3,1,1]]
# large severity difference
assert Solution().sortThreats([[1,1,100],[2,50,1]]) == [[2,50,1],[1,1,100]]
| Test | Why |
|---|---|
| two provided examples | validates core sorting logic and tie-breaking |
| single element | ensures base case correctness |
| identical scores different IDs | validates tie-break rule |
| large severity vs exploitability mix | ensures correct score computation dominance |
Edge Cases
One important edge case is when all threats produce identical scores. In this situation, the algorithm must rely entirely on ID ordering. Because the comparator explicitly uses ID as the secondary key, the result remains deterministic and correct.
Another edge case is a single-element input. Since sorting a single element is trivial, the algorithm should simply return the same list. Both implementations naturally handle this without special casing because sorting and iteration are safe on length-one arrays.
A further edge case involves very large input sizes up to 100,000 elements. This stresses performance and makes O(n^2) approaches infeasible. The chosen O(n log n) sorting-based solution remains efficient and within typical constraints.
A final subtle edge case is numerical magnitude. Since severity and exploitability can be as large as 10^9, the computed score can reach 2 × 10^9 + 10^9, which is still safely within Python’s integer range and Go’s 64-bit integer capacity when using default int on most modern platforms.