Delete K Subsets for Maximum Score
Updated
Problem statement
You are given an integer array nums of length m, a 2D integer array subsets of length n, and an integer k. Each subsets[i] is a list of distinct indices into nums.
You must delete exactly k of the lists in subsets. After that, let U be the set of all indices that appear in at least one of the remaining n - k lists.
Your score is the sum of all elements of nums minus the sum of nums[j] for every index j in U. In other words, the score is the total of the elements whose index appears in none of the remaining lists.
Return the maximum score you can get.
Function
maxScore(nums: int[], subsets: int[][], k: int) → intExamples
Example 1
nums = [10,20,30,40]subsets = [[0,1],[1,2],[3]]k = 1return = 40The total of nums is 100. You delete exactly one list.
- Delete
[0, 1]: the rest cover indices1,2,3, so the score is100 - 90 = 10. - Delete
[1, 2]: the rest cover indices0,1,3, so the score is100 - 70 = 30. - Delete
[3]: the rest cover indices0,1,2, so the score is100 - 60 = 40.
The best score is 40.
Example 2
nums = [5,1,2]subsets = [[0],[2]]k = 0return = 1Nothing is deleted, so indices 0 and 2 are covered. Only index 1 is free, and the score is 1.
Example 3
nums = [3,4]subsets = [[0,1],[1]]k = 2return = 7Both lists are deleted, so no index is covered. The score is the whole total, 3 + 4 = 7.
Constraints
1 <= m == nums.length <= 301 <= nums[i] <= 10^41 <= n == subsets.length <= 201 <= subsets[i].length <= m0 <= subsets[i][j] < m, and the indices in eachsubsets[i]are distinct.0 <= k <= n
More Rubrik Online Assessment questions
- Delete and Freeze GameOA · Seen Nov 2026
- Distribute Elements Into Two Arrays IIOA · Seen Nov 2026
- Minimum Replacements to Sort the ArrayOA · Seen Nov 2026
- Minimum Swaps To Binary PalindromeOA · Seen Apr 2026
- Get Minimum OperationsOA · Seen Nov 2024
- Horizontal Pod AutoscalerOA · Seen Nov 2024
- Stock PricesOA · Seen Nov 2024
- StarlightOA · Seen Oct 2024
- Energy CrisisOA · Seen Sep 2024
- Mike and GemsOA · Seen Sep 2024
Similar questions at other companies
- Optimize Discount Selection Under a Point BudgetPalantir · OAPalantir interview questions
- Maximum Index-Weighted Sum with Disjoint SwapsVisa · OAVisa interview questions
- Distinct OR Values of Increasing SubsequencesScale AI · OAScale AI interview questions
- Vehicle Builds for Required Terrain (Game Adaptation)Roblox · OARoblox interview questions
- Bitwise XOR SubsequencesJP Morgan Chase · OAJP Morgan Chase interview questions
- Bitwise XOR SubsequencesGoldman Sachs · OAGoldman Sachs interview questions
- Minimum Racks for Server ResourcesGoogle · PHONE SCREENGoogle interview questions
- Minimum Cost for a Target WeightPace Stock Broking Services · PHONE SCREEN
- Smallest Sufficient TeamExpedia · ONSITE INTERVIEWExpedia interview questions
- Split Array to Minimize the Largest SumInfosys · OAInfosys interview questions