Feed Batch Boundaries
End indices of the most contiguous blocks reorderable to match a target array
A social network has a queued feed and an approved feed. Each entry is the ID of the account that created that feed item. An account may appear more than once.
The publishing service divides the queued feed into nonempty contiguous batches. It may reorder entries within each batch, but it cannot move an entry between batches or change the order of the batches. After these local reorderings, the entire feed must equal the approved feed.
Given arrays queued and approved of equal length, return the inclusive ending indices of a partition that uses the largest possible number of batches. Return the indices in increasing order, using zero-based indexing.
If no partition can produce the approved feed, return an empty list.
For example, ending indices [1, 4] describe the batches covering indices 0..1 and 2..4.
The maximum-batch partition is uniquely determined: every boundary that can appear in a valid partition can be included together in one valid partition.
Examples
Example 1
Input: queued = [8,3,5,9,2], approved = [3,8,5,2,9] Output: [1,2,4]
The first two entries can be reordered to match the approved feed. The middle entry already matches, and the final two entries can be reordered independently. Neither of the two-entry batches can be split further.
Example 2
Input: queued = [4,4,7,4], approved = [4,7,4,4] Output: [0,2,3]
Repeated account IDs represent separate entries. The first three entries have matching account frequencies and can form one batch; the final entry forms another.
Example 3
Input: queued = [1,2,1], approved = [1,2,3] Output: []
The approved feed contains an account ID that does not occur in the queued feed, so no amount of reordering can produce it.
Constraints
- 1 <= queued.length == approved.length <= 10000
- 0 <= queued[i], approved[i] <= 1000000000
- Account IDs may repeat.
Use O(n) expected time and O(d) auxiliary space, excluding the returned indices, where d is the number of distinct account IDs. If the complete arrays have different frequencies, discard any earlier candidate boundaries.
Hints
Show hint 1Hint 1
A batch can be reordered into its approved positions exactly when the two corresponding slices have the same frequency of every account ID.
Show hint 2Hint 2
Scan aligned prefixes while maintaining frequency differences. Track how many IDs currently have a nonzero difference so that you can recognize a valid boundary efficiently.
Follow-up questions
What an interviewer might ask once you have a working solution.
- How would you change the result if every batch had to contain at least k entries?
- If valid inputs arrive as two synchronized streams, what information must be retained, and when is it safe to finalize the answer?
Practice this with an AI interviewer
Explain your approach out loud, write Python or JavaScript, run it against hidden tests (including large inputs), and get a scored debrief.
Start this problem