Skip to main content
Talentd

Sort Threats by Severity and Exploitability - Solution & Explanation

MediumPremiumFree on FleetCodeArraySorting7 min read
Practice this problem

Problem Statement

You are given a 2D integer array threats, where each threats[i] = [IDi, sevi​, expi]

  • IDi: Unique identifier of the threat.
  • sevi: Indicates the severity of the threat.
  • expi: Indicates the exploitability of the threat.

The score of a threat i is defined as: score = 2 × sevi + expi

Your task is to return threats sorted in descending order of score.

If multiple threats have the same score, sort them by ascending ID​​​​​​​.

 

Example 1:

Input: threats = [[101,2,3],[102,3,2],[103,3,3]]

Output: [[103,3,3],[102,3,2],[101,2,3]]

Explanation:

Threat ID sev exp Score = 2 × sev + exp
threats[0] 101 2 3 2 × 2 + 3 = 7
threats[1] 102 3 2 2 × 3 + 2 = 8
threats[2] 103 3 3 2 × 3 + 3 = 9

Sorted Order: [[103, 3, 3], [102, 3, 2], [101, 2, 3]]

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 ID sev exp Score = 2 × sev + exp
threats[0] 101 4 1 2 × 4 + 1 = 9
threats[1] 103 1 5 2 × 1 + 5 = 7
threats[2] 102 1 5 2 × 1 + 5 = 7

threats[1] and threats[2] have same score, thus sort them by ascending ID.

Sorted Order: [[101, 4, 1], [102, 1, 5], [103, 1, 5]]

 

Constraints:

  • 1 <= threats.length <= 105
  • threats[i] == [IDi, sevi, expi]
  • 1 <= IDi <= 106
  • 1 <= sevi <= 109
  • 1 <= expi <= 109
  • All IDi are unique

Approach Overview

Problem Overview: You receive a list of security threats where each item includes two ranking signals: severity and exploitability. The goal is to order the threats so the most dangerous ones appear first. Sorting must prioritize higher severity, and when two threats share the same severity, exploitability becomes the tie‑breaker.

Approach 1: Brute Force Pairwise Ordering (O(n²) time, O(1) space)

A direct way to solve the problem is to repeatedly compare every pair of threats and swap them if they are out of order. The comparison rule checks severity first and then exploitability when severities match. This behaves similarly to simple algorithms like bubble sort or selection sort. The implementation is straightforward and clearly expresses the ordering rule, but it performs poorly for large inputs because it scans the array multiple times. Time complexity is O(n²) and extra space remains O(1).

Approach 2: Custom Comparator Sorting (O(n log n) time, O(log n) space)

The practical solution uses a standard library sort with a custom comparator. Each comparison evaluates two fields: first compare severity, then exploitability if severities are equal. Most modern languages allow passing a comparator or key function to the sort routine. Under the hood, algorithms like Timsort or introsort handle the heavy lifting. You iterate once to call the sort function, and the comparator ensures threats are ordered correctly. The runtime is O(n log n) with O(log n) auxiliary stack space depending on the implementation.

This approach works naturally with arrays because the elements can be compared directly during sorting. If threats are represented as objects or tuples, the comparator simply extracts the two attributes and applies the ordering rule. Many implementations convert the ranking rule into a tuple key like (-severity, -exploitability) so that a single built‑in sort operation handles both priorities.

Approach 3: Counting / Bucket Sort (O(n + k) time, O(k) space)

If severity and exploitability values come from small bounded ranges, a non‑comparison sort can outperform general sorting. You create buckets for each severity level and place threats accordingly. Within each bucket, threats are ordered by exploitability using another counting pass or small local sort. This reduces the runtime to O(n + k), where k represents the range of possible values. The tradeoff is additional memory proportional to the number of buckets.

Recommended for interviews: The custom comparator sorting approach is what interviewers expect. It demonstrates that you can translate a multi‑field ranking rule into a deterministic comparison while leveraging efficient built‑in algorithms. Showing the brute force idea first proves you understand the ordering logic, while the O(n log n) solution highlights practical problem‑solving with sorting on top of a simple array structure.

Solution

We can directly sort the array according to the requirements of the problem. Note that the score is a long integer, so we need to use long integers when comparing to avoid overflow.

The time complexity is O(n times log n), and the space complexity is O(log n), where n is the length of the array threats.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Pairwise / Brute Force SortingO(n²)O(1)Good for demonstrating the ordering logic or very small inputs
Custom Comparator with Built-in SortO(n log n)O(log n)General case and expected interview solution
Counting / Bucket SortO(n + k)O(k)When severity and exploitability ranges are small and bounded

Video Solution

Sort Threats By Severity And Exploitability • Owen Wu • 27 views views

Frequently Asked Questions

Is Sort Threats by Severity and Exploitability easy or hard?
The problem is generally classified as Medium difficulty. The logic is straightforward once you recognize it as a multi-field sorting task, but interview candidates must correctly implement the comparator and reason about ordering rules and complexity.
Sort Threats by Severity and Exploitability Python/Java solution
In Python, the problem is typically solved with sorted() or list.sort() using a key such as (-severity, -exploitability). In Java, developers use Arrays.sort or Collections.sort with a custom Comparator that compares severity first and exploitability second.
How to solve Sort Threats by Severity and Exploitability in O(n)?
An O(n) solution is possible only if severity and exploitability values come from small bounded ranges. In that case, counting sort or bucket sort can group threats by severity and then order them by exploitability within each bucket. The runtime becomes O(n + k), where k is the range of values.
What is the best approach for Sort Threats by Severity and Exploitability?
The best approach is sorting with a custom comparator. Compare threats by severity first and use exploitability as a tie‑breaker when severities match. Using the built‑in sorting functions available in most languages results in O(n log n) time complexity with minimal extra space.
Is Sort Threats by Severity and Exploitability asked at Google/Amazon/Meta?
Problems involving multi-key sorting appear frequently in interviews at companies like Amazon, Google, and Meta. While the exact problem title may vary, interviewers often test whether candidates can implement custom comparators and reason about sorting complexity.
What data structure is used in Sort Threats by Severity and Exploitability?
The primary data structure is an array or list containing threat records. The algorithm applies a sorting technique with a comparator that inspects two attributes for each element: severity and exploitability.
What is the time complexity of Sort Threats by Severity and Exploitability?
The optimal solution runs in O(n log n) time because it relies on comparison-based sorting. Each comparison checks severity and possibly exploitability, but that comparison still takes constant time. Space complexity is typically O(log n) due to recursion or stack usage in the sorting algorithm.

Ready to solve this problem?

Practice Sort Threats by Severity and Exploitability with our built-in code editor and test cases.

Practice on FleetCode
Previous

Sort the Students by Their Kth Score