How should I practice Partition Into K Subarrays With Sum at Least X?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Google onsite interview problems in FastPrep.

Is Partition Into K Subarrays With Sum at Least X associated with Google?

FastPrep tags this as a Google onsite interview coding practice problem when the problem catalog has that company and stage context.

Partition Into K Subarrays With Sum at Least X

Google● MediumNEW GRADONSITE INTERVIEW

Learn

Problem statement

You are given an integer array nums and integers k and x.

Determine whether the entire array can be partitioned, in its original order, into exactly k non-empty contiguous subarrays such that the sum of every subarray is at least x.

Return true if such a partition exists. Otherwise, return false.

Implement canPartitionWithMinimumSum(nums, k, x).

Function

canPartitionWithMinimumSum(nums: int[], k: int, x: int) → boolean

Examples

Example 1

nums = [3,1,4,2,2]k = 3x = 4return = true

One valid partition is [3,1] | [4] | [2,2]. All three subarray sums equal 4.

Example 2

nums = [100,1,1]k = 2x = 50return = false

The only cut positions produce sums 100 and 2, or 101 and 1. In both cases, one subarray sum is below 50.

Example 3

nums = [10,-5,5]k = 2x = 5return = true

The partition [10,-5] | [5] has subarray sums 5 and 5. Cutting immediately after 10 would fail, which is why a positive-only greedy rule does not handle negative values.

Constraints

1 <= nums.length <= 2000.
1 <= k <= nums.length.
-10^9 <= nums[i] <= 10^9.
1 <= x <= 10^9.
Subarray sums may exceed 32-bit integer range.