LeetCode 3631 - Sort Threats by Severity and Exploitability

We are asked to sort a list of threats according to a computed score. Each threat is represented as a 3-element array [IDi, sevi, expi], where IDi is a unique identifier, sevi is the severity, and expi is the exploitability.

leetcodemediumarraysorting

LeetCode Problem 3631

Difficulty: 🟡 Medium
Topics: Array, Sorting

Solution

Problem Understanding

We are asked to sort a list of threats according to a computed score. Each threat is represented as a 3-element array [IDi, sevi, expi], where IDi is a unique identifier, sevi is the severity, and expi is the exploitability. The score of a threat is defined as:

score = 2 × sevi + expi

The required output is the same array of threats, but sorted first by descending score. If two threats have the same score, they should be sorted by ascending ID.

Constraints clarify that there can be up to 10^5 threats, each with large integer values for severity and exploitability (≤ 10^9), and all IDs are unique (1 ≤ IDi ≤ 10^6). This guarantees that we do not need to handle duplicate IDs or invalid input.

Important edge cases include:

  • Multiple threats having the same score, requiring secondary sorting by ID.
  • The minimum input size of one threat.
  • Large numbers for sevi and expi to ensure arithmetic does not overflow.

The problem is fundamentally a custom sort problem.

Approaches

The brute-force approach would iterate through the array, compute the score for each threat, and repeatedly insert threats into a new sorted array by comparing scores one by one. While correct, this insertion-based approach would have O(n²) time complexity due to repeated comparisons and shifting, which is prohibitive for n = 10^5.

The optimal approach leverages a single sorting pass using a custom key. Compute the score for each threat once, then sort the array by a tuple (score descending, ID ascending) using a stable or efficient built-in sorting algorithm (Timsort in Python, introsort in Go). This reduces the time complexity to O(n log n) and requires only O(n) auxiliary space for the sort operation.

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(n) Insert threats one by one into sorted array by score
Optimal O(n log n) O(n) Compute score once, sort by (score descending, ID ascending)

The key observation is that computing the score is a simple arithmetic operation, and sorting with a tuple key guarantees the secondary order requirement.

Algorithm Walkthrough

  1. Iterate through the list of threats. For each threat [IDi, sevi, expi], compute its score = 2 × sevi + expi. This is a local computation and does not modify the original data.
  2. Sort the threats array using a composite key:
  • Primary key: negative of the score (to achieve descending order).
  • Secondary key: the ID itself (to achieve ascending order if scores tie).
  1. Return the sorted array.

Why it works:

The sort uses a total ordering on tuples (−score, ID), which guarantees that for any pair of threats a and b, one of the three possibilities holds: a comes before b, b comes before a, or they are identical (which cannot happen because IDs are unique). Sorting by −score ensures descending order for the main metric, and sorting by ID resolves ties in a deterministic manner.

Python Solution

from typing import List

class Solution:
    def sortThreats(self, threats: List[List[int]]) -> List[List[int]]:
        # Define a custom key for sorting
        def threat_key(threat: List[int]) -> tuple[int, int]:
            ID, sev, exp = threat
            score = 2 * sev + exp
            return (-score, ID)
        
        # Sort the threats in-place using the key
        threats.sort(key=threat_key)
        return threats

Implementation walkthrough:

The threat_key function computes score = 2 * sev + exp and returns a tuple (-score, ID). Sorting by this tuple ensures descending score order and ascending ID order on ties. Python's built-in sort uses Timsort, which is stable and efficient for large arrays. Sorting is done in-place, and the sorted array is returned.

Go Solution

import "sort"

func sortThreats(threats [][]int) [][]int {
    sort.Slice(threats, func(i, j int) bool {
        scoreI := 2*threats[i][1] + threats[i][2]
        scoreJ := 2*threats[j][1] + threats[j][2]
        if scoreI != scoreJ {
            return scoreI > scoreJ
        }
        return threats[i][0] < threats[j][0]
    })
    return threats
}

Go-specific notes:

In Go, sort.Slice requires a boolean comparator function. We compute scoreI and scoreJ inline and compare them. The logic scoreI > scoreJ achieves descending order. For equal scores, threats[i][0] < threats[j][0] ensures ascending ID. Go handles slices directly, so no extra memory allocation is necessary.

Worked Examples

Example 1:

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

Compute scores:

ID sev exp Score
101 2 3 7
102 3 2 8
103 3 3 9

Sort by descending score:

Sorted ID sev exp Score
103 3 3 9
102 3 2 8
101 2 3 7

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

Example 2:

Input: [[101,4,1],[103,1,5],[102,1,5]]

Compute scores:

ID sev exp Score
101 4 1 9
103 1 5 7
102 1 5 7

Sort by descending score, tie-break by ID:

Sorted ID sev exp Score
101 4 1 9
102 1 5 7
103 1 5 7

Output: [[101,4,1],[102,1,5],[103,1,5]]

Complexity Analysis

Measure Complexity Explanation
Time O(n log n) Sorting an array of length n with a comparison-based algorithm
Space O(n) Sorting uses auxiliary space, either in-place (Python) or slice overhead (Go)

The arithmetic for computing scores is O(n) and negligible compared to the sort.

Test Cases

# Provided examples
assert Solution().sortThreats([[101,2,3],[102,3,2],[103,3,3]]) == [[103,3,3],[102,3,2],[101,2,3]]  # standard case
assert Solution().sortThreats([[101,4,1],[103,1,5],[102,1,5]]) == [[101,4,1],[102,1,5],[103,1,5]]  # tie on score

# Edge cases
assert Solution().sortThreats([[1,1,1]]) == [[1,1,1]]  # single element
assert Solution().sortThreats([[2,1,1],[1,1,1]]) == [[1,1,1],[2,1,1]]  # tie score, sort by ID
assert Solution().sortThreats([[1000000,10**9,10**9],[999999,10**9,10**9]]) == [[999999,10**9,10**9],[1000000,10**9,10**9]]  # large values, tie score
Test Why
[[101,2,3],[102,3,2],[103,3,3]] Standard case with different scores
[[101,4,1],[103,1,5],[102,1,5]] Tie on score, check ID ordering
[[1,1,1]] Minimum input size
[[2,1,1],[1,1,1]] Tie score with ascending ID sorting
[[1000000,10**9,10**9],[999999,10**9,10**9]] Test large integer values

Edge Cases

  1. Single-element array: The sort operation should handle n = 1 without errors. The algorithm correctly returns the single element unchanged