I received this problem for a phone screen for a software engineering role at Google.

I want to contribute this question because I assumed it was a simple problem, easily solved in O(N) time and O(N) space, however the interviewer added a twist when he asked me to solve it in O(1) space complexity which made it in actuality a very difficult problem.
Description
Given an integer N and an array of unique integers representing the order in which items are popped from a hidden stack, return whether the stack could be valid. The items must be pushed into the stack sequentially in order of 1 to N (e.g. 1, 2 must be pushed before 3 can be pushed to the stack).

This should be solved using constant space complexity.

Example:
Given poporder=[1,2,3,4,5], N=5, returns True since

Push (1), Pop (1), Push (2), Pop (2), Push (3), Pop (3), Push (4), Pop (4), Push (5), Pop (5) would give a pop order of [1,2,3,4,5].

Given poporder=[3,2,1,4,5], N=6 returns True since

Push(1), Push(2), Push (3), Pop (3), Pop (2), Pop(1), Push (4), Push (5), Pop (5), Push(5), Push (6) would give a pop order of [3,2,1,5,4],

Given poporder [3,1], N=3, returns False since

Push (1), Push (2), Push(3), Pop (3), Pop (2), Pop (1) would give a poporder of [3,2,1] ie. if 3 is in the stack 2 must be popped before 1 can be popped.

1 <= N <= INT_MAX

1 <= Integers in poporder array <= INT_MAX

1 <= size of poporder array <= INT_MAX

Solutions
An initial approach would be to simulate the stack using O(N) space and time complexity. The user could simulate a stack using an array in Python.
def isValidPoporder(N, poporder):
stack = []
inp = 1
seen = set()
for item in poporder:
if item > N
if item >= inp:
for x in range(inp, item):
stack.append(x)
inp = item + 1
elif item < inp:
if stack == [] or stack[-1] != item:
return False
else:
stack.pop(-1)

return True

An approach using O(1) space would be to take advantage of the fact that if any of the items in the stack are in the order a > b < a, then the poporder is invalid.

def isValidPoporder(N, poporder):
for i, c in enumerate(poporder):
for j in range(0, i):
for k in range(j,i):
a = poporder[j]
b = poporder[k]
if a > b and b < a:
return False
return True