Randomly partition array into k segments

Question

Given a list of integers and an integer k representing the number of segments, write a function that randomly partitions the list into k non-empty segments and returns them as a list of lists. Explain your approach, discuss its time and space complexity, and describe how you would test the randomness of your solution.

Seeded Random k-Segment Partition

Given an integer array nums, an integer k (1 <= k <= len(nums)), and a 32-bit unsigned integer seed, return a uniformly random partition of nums into k non-empty contiguous segments. Model the partition as placing k-1 cuts among the n-1 gaps between elements, uniformly over all C(n-1, k-1) choices. For reproducibility, use exactly the following PRNG and sampling method:

• PRNG: 32-bit linear congruential generator (LCG). State is initialized as seed mod 2^32. Each draw sets state = (1664525 * state + 1013904223) mod 2^32 and returns state.
• To draw a uniform integer in [0, m-1], use rejection sampling: let M = 2^32 and limit = (M // m) * m. Repeatedly draw r until r < limit, then return r % m.
• To choose k-1 distinct cut positions uniformly from [1, n-1], use Floyd's algorithm: iterate j from (n-1)-(k-1)+1 to (n-1), pick t uniformly in [1, j]; if t is already chosen, include j; otherwise include t. Sort the selected positions and cut after those indices to form segments.

Constraints

• 1 <= len(nums) <= 100000
• 1 <= k <= len(nums)
• -10^9 <= nums[i] <= 10^9
• 0 <= seed < 2^32
• Output must be k non-empty contiguous subarrays whose concatenation equals nums

Examples

Example 1

Input: nums = [1,2,3,4,5], k = 2, seed = 42
Output: [[1,2],[3,4,5]]

Explanation: n=5 -> gaps=4. Using the specified LCG and rejection sampling, Floyd's algorithm selects cut {2}. Cutting after index 2 yields [[1,2],[3,4,5]].

Example 2

Input: nums = [-1,0,7,8], k = 2, seed = 1
Output: [[-1],[0,7,8]]

Explanation: n=4 -> gaps=3. The first PRNG draw maps to cut {1}. Cutting after index 1 yields [[-1],[0,7,8]].

Hints

1. Reduce the problem to choosing k-1 distinct cut positions among n-1 gaps.
2. Use a seeded PRNG to make the output deterministic for testing.
3. Floyd's algorithm samples without replacement in O(k) time and O(k) space.
4. After selecting cuts, sort them and slice the array accordingly.
5. To test randomness quality, run many trials and apply frequency checks (e.g., chi-square) over cut positions.

Approach

The partition is determined by k-1 cut positions among n-1 available gaps. To ensure uniformity and reproducibility, we use a fixed 32-bit LCG and rejection sampling to obtain unbiased integers in ranges. Floyd's algorithm samples k-1 distinct gap indices uniformly without replacement in O(k) time by iterating j and choosing t uniformly in [1..j], resolving collisions by substituting j. After sorting the cuts, we slice nums at those positions to produce k non-empty contiguous segments. Randomness validation (not required by the function) can be done by running many trials and comparing observed frequencies of cut positions against the expected uniform distribution using statistical tests such as chi-square.

• Time complexity: O(n + k)
• Space complexity: O(k) extra (excluding output)