Withdrawal Tape Agreement

Whether two arrays yield equal sequences after appends and deletions

MediumTwo PointersReverse TraversalConstant Space

A stock exchange stores temporary quote drafts as instruction tapes. Each tape starts with an empty draft and is processed from left to right.

  • A nonnegative instruction appends that integer as a quote value.
  • A negative instruction -k withdraws the last k quotes currently in the draft. If fewer than k quotes remain, it withdraws all of them. Any unused withdrawals are discarded; they do not affect later instructions.

Given two tapes, first and second, return true if their final drafts contain exactly the same quote values in exactly the same order, and false otherwise.

A quote value of zero is valid. Repeated quote values remain separate entries.

Your solution should run in linear time and use constant auxiliary space, without constructing either final draft.

Examples

Example 1

Input: first = [105,108,-1,110], second = [105,110]
Output: true

The first tape withdraws 108 before appending 110. Both final drafts therefore contain 105 followed by 110.

Example 2

Input: first = [-4,90,92,-1], second = [90,-2,90]
Output: true

The initial withdrawal on the first tape has nothing to remove. It later removes 92, leaving 90. The second tape removes its first 90 and then appends another 90, so the final drafts agree.

Example 3

Input: first = [40,50,-1,60], second = [40,61]
Output: false

The first tape finishes with 40 followed by 60, while the second finishes with 40 followed by 61. Their final quote values differ.

Constraints

  • 0 <= first.length, second.length <= 5000
  • -10^9 <= first[i], second[i] <= 10^9
  • All tape entries are integers.

Withdrawals never remove instructions; they remove quotes produced by earlier instructions. Target complexity: O(len(first) + len(second)) time and O(1) auxiliary space. Pending-withdrawal counters may exceed the magnitude of one instruction, so use a sufficiently wide numeric type.

Hints

Show hint 1

Look for the last surviving quote in each tape without replaying the complete draft.

Show hint 2

When scanning backward, accumulate withdrawal amounts. A nonnegative entry either consumes one pending withdrawal or becomes the next surviving quote.

Follow-up questions

What an interviewer might ask once you have a working solution.

  • How would you return the length of the common suffix of the two final drafts while retaining constant auxiliary space?
  • If instructions arrive as forward-only streams that cannot be reread, what storage would your solution need?

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