Number of Great Partitions
01 · Problem
You are given an array nums of positive integers and an integer k. Split the elements into two ordered groups (a first group and a second group) so that every element belongs to exactly one group. A split is great if the sum of each group is at least k.
Return the number of distinct great splits modulo 10^9 + 7. Two splits are different if some index i is in the first group in one split and in the second group in the other, so equal values at different indices are treated as different elements, and swapping the two groups gives a different split. Since k >= 1, a great split never has an empty group.
02 · Examples
nums = [1,2,3,4], k = 4
6
The great splits are ([1,2,3],[4]), ([1,3],[2,4]), ([1,4],[2,3]) and the same three with the groups swapped.
nums = [3,3,3], k = 4
0
The total is 9, so one group always has sum at most 3 (or 0). No split gives both groups a sum of at least 4.
nums = [6,6], k = 2
2
Put index 0 in the first group and index 1 in the second, or the other way round. Both groups have sum 6.
03 · Constraints
- 011 <= nums.length <= 1000
- 021 <= nums[i] <= 109
- 031 <= k <= 1000
04 · Optimal complexity
- Time
- O(n * k)
- Space
- O(k)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.