3631. Sort Threats by Severity and Exploitability 🔒

MediumArraySorting

Leetcode Link

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.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

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.
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 Evaluator

Example 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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using the following tree as input?

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12

1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18

1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

1 2 3 6 x x

1 2 3 x x x 6 x x

1 2 6 x x x 3 x x

I don't know