Check if an array is stack-sortable

user_9849118 0
Viewed 192

Here is the question:

We want to rearrange a sorted array [1, ..., N] using a stack.

Ex:

 * push 1 then pop 1.
 * push 2 then push 3 then pop twice and get 3 then 2.

Then we can get [1,3,2] from [1,2,3]

Check if we can get the given array by rearranging the sorted array (ascending order) using a stack.

Limitation:

 * 0 < The size of the given array (N) <= 100,000
 * 1 <= The items of the given array <= N
 * No duplicates inside the given array

Test cases:

 * [1, 3, 2]: true
 * [3,1,2]: false

I wanted to know what I am missing from the code below. The following code fails on some test cases:

function solution(array) {
  const stack = [];
  let idx = 0;

  for (let i = 1; i <= array.length; i++) {
    if (i !== array[idx]) {
      stack.push(i);
    } else {
      idx++;
    }
  }

  for (idx; idx < array.length; idx++) {
    let item = stack.pop();
    if (item !== array[idx]) {
      return false;
    }
  }

  return true;
}

Many thanks!

stack sorting arrays algorithm javascript
1 Answers

The logic is not correct, as already mentioned in the comments, you cannot just push and then pop.

The easiest way is to always push if the number is not matching and if it is a match then pop as many values as possible:

function solution(array) {
    const stack = []
    let idx = 0
    for (let i = 1; i <= array.length; i++) {
        if (i != array[idx]) {
           stack.push(i)
        } else {
           idx++
           while (stack.length > 0 && stack[stack.length - 1] == array[idx]) {
               idx++
               stack.pop()
           }
        }
    }
    return idx == array.length
}

console.log(solution([1,3,2]))
console.log(solution([3,1,2]))

user_47851100
Related