Check if two stacks are equal in O(1) space

Question

I was asked this in an interview:

Check if given two stacks are equal (size and order of elements) using O(1) space.

Stacks should maintain their earlier state (order of elements).

Recursion uses stack space so not valid.

One of my friend suggested to use String variable and append elements from one stack into it and push popped to the other one and then push from S2(old elements of S1) to S1 and do the same thing with S2. But this depends on the size of the Stack as String will grow depending on the size of stack.

Answer 1

Recursion vs iteration is not the issue here. The issue is how to leave the stacks intact, because the only way to inspect a stack in full is to empty it.

So what you need to do is store the popped members onto temporary stacks. This does not change the overall space requirements, since you only push onto the temporary stack objects that are popped elsewhere, and thus you are satisfying the O(1) spare requirement.

Here’s the pseudocode for an iterative solution:

function stacks_are_equal
  precondition: stacks s1, s2

  set equal? to true

  while s1 is not empty and s2 is not empty
    pop x from s1
    pop y from s2
    push x onto temp1
    push y onto temp2

    if x ≠ y then
      set equal? to false
      break out of loop

  if s1 is not empty or s2 is not empty set equal? to false

  while temp1 is not empty
    pop x from temp1
    pop y from temp2
    push x onto s1
    push y onto s2

  return equal?

And here’s the recursive solution:

function stacks_are_equal(s1, s2)
  if s1 is empty and s2 is empty return true
  if s1 is empty or s2 is empty return false

  pop x from s1
  pop y from s2

  empty? := x = y and stacks_are_equal(s1, s2)

  push x onto s1
  push y onto s2

  return empty?

Answer 2

Use recursion...Here is an example using java.

private static boolean equalhelper(Stack<Integer> s1, Stack<Integer> s2)
{
    if(s1.isEmpty() && s2.isEmpty())
        return true;
    if(s1.isEmpty() || s2.isEmpty())
        return false;       

    Integer a=s1.pop();
    Integer b=s2.pop();
    if(!a.equals(b))
    {
        s1.push(a);
        s2.push(b);
        return false;
    }
    else
    {
        boolean check= equalhelper( s1, s2);
        s1.push(a);
        s2.push(b);
        return check;
    }
}