Dynamic Stack Using Resizable Array in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output after these stack operations?

Consider a dynamic stack implemented using a resizable array. Initially, the stack is empty.

Operations:

1. push(10)
2. push(20)
3. pop()
4. push(30)
5. push(40)
6. pop()

What is the printed stack content from top to bottom?

DSA Typescript

class DynamicStack {
  private arr: number[] = [];
  push(val: number) {
    this.arr.push(val);
  }
  pop(): number | undefined {
    return this.arr.pop();
  }
  printStack() {
    console.log(this.arr.slice().reverse().join(' -> ') + ' -> null');
  }
}

const stack = new DynamicStack();
stack.push(10);
stack.push(20);
stack.pop();
stack.push(30);
stack.push(40);
stack.pop();
stack.printStack();

A 20 -> 10 -> null

B 40 -> 30 -> 10 -> null

C 10 -> 30 -> null

D 30 -> 10 -> null

💡 Hint

Remember that pop removes the top element and push adds on top.

After the operations, the stack has 10 at bottom and 30 on top. So printing top to bottom is 30 -> 10 -> null.

🧠 Conceptual

intermediate

What happens when the internal array is full in a dynamic stack?

In a dynamic stack implemented using a resizable array, what is the typical behavior when the internal array reaches its capacity and a new element is pushed?

A The array size doubles and existing elements are copied to the new array before adding the new element.

B The stack throws an overflow error and stops accepting new elements.

C The new element replaces the oldest element in the array.

D The array size remains the same and the new element is discarded.

💡 Hint

Think about how dynamic arrays handle capacity limits.

Dynamic arrays typically double their size when full to accommodate more elements, copying existing elements to the new larger array.

🔧 Debug

advanced

Identify the error in this pop method of dynamic stack

Given this pop method in a dynamic stack, what error will it cause?

pop(): number {
  if (this.arr.length === 0) {
    return -1;
  }
  return this.arr.pop();
}

A SyntaxError due to missing semicolon.

B No error, returns -1 when stack is empty.

C TypeError because pop() can return undefined but method expects number.

D Runtime error because pop() is called on empty array.

💡 Hint

Check the return type and what pop() returns when array is empty.

pop() returns undefined if array is empty, but method signature expects number, causing a TypeError in strict typing.

🚀 Application

advanced

How to optimize memory usage in a dynamic stack?

In a dynamic stack using a resizable array, which approach helps reduce memory usage when many elements are popped?

A Shrink the internal array size by half when the number of elements falls below a quarter of capacity.

B Keep the array size fixed after initial allocation to avoid resizing overhead.

C Double the array size every time an element is popped.

D Clear the entire array after every pop operation.

💡 Hint

Think about resizing strategies to balance performance and memory.

Shrinking the array when usage is low frees memory while avoiding frequent resizing.

❓ Predict Output

expert

What is the output of this dynamic stack sequence with resizing?

Given a dynamic stack with initial capacity 2, doubling capacity when full, and halving capacity when less than quarter full, what is the output of the capacity after these operations?

push(1)
push(2)
push(3)
pop()
pop()
pop()

Print the capacity after each operation in order as a list.

DSA Typescript

class DynamicStack {
  private arr: number[] = new Array(2);
  private capacity: number = 2;
  private size: number = 0;

  push(val: number) {
    if (this.size === this.capacity) {
      this.capacity *= 2;
      const newArr = new Array(this.capacity);
      for (let i = 0; i < this.size; i++) {
        newArr[i] = this.arr[i];
      }
      this.arr = newArr;
    }
    this.arr[this.size++] = val;
  }

  pop(): number | undefined {
    if (this.size === 0) return undefined;
    const val = this.arr[--this.size];
    if (this.size > 0 && this.size < this.capacity / 4) {
      this.capacity = Math.floor(this.capacity / 2);
      const newArr = new Array(this.capacity);
      for (let i = 0; i < this.size; i++) {
        newArr[i] = this.arr[i];
      }
      this.arr = newArr;
    }
    return val;
  }

  getCapacity() {
    return this.capacity;
  }
}

const stack = new DynamicStack();
const capacities = [];
stack.push(1); capacities.push(stack.getCapacity());
stack.push(2); capacities.push(stack.getCapacity());
stack.push(3); capacities.push(stack.getCapacity());
stack.pop(); capacities.push(stack.getCapacity());
stack.pop(); capacities.push(stack.getCapacity());
stack.pop(); capacities.push(stack.getCapacity());
console.log(capacities);

A [2, 2, 4, 4, 2, 2]

B [2, 2, 4, 4, 2, 1]

C [2, 2, 4, 2, 1, 1]

D [2, 2, 4, 4, 4, 2]

💡 Hint

Track capacity changes carefully after each push and pop.

Capacity doubles from 2 to 4 on third push. Pops reduce size triggering capacity halving from 4 to 2, then from 2 to 1.

Practice

1. What is the main advantage of using a dynamic stack implemented with a resizable array compared to a fixed-size array stack?

easy

A. It can grow or shrink in size as needed during runtime.

B. It uses less memory than a linked list stack.

C. It always has a fixed maximum size.

D. It does not require resizing or copying elements.

Solution

1. Step 1: Understand fixed vs dynamic size

   A fixed-size array stack has a set size and cannot grow beyond it, limiting capacity.

2. Step 2: Understand dynamic resizing

   A dynamic stack with resizable array can increase or decrease its size during runtime to fit more or fewer elements.

3. Final Answer:

   It can grow or shrink in size as needed during runtime. -> Option A

4. Quick Check:

   Dynamic resizing = flexible size [OK]

Hint: Dynamic arrays resize automatically when full or empty [OK]

Common Mistakes:

• Thinking dynamic stack has fixed max size
• Confusing memory use with linked list
• Assuming no resizing needed

2. Which of the following TypeScript code snippets correctly doubles the size of the internal array when the stack is full?

easy

A. this.array = [...this.array, ...new Array(this.array.length)];

B. this.array.push(...new Array(this.array.length));

C. this.array.length = this.array.length * 2;

D. const newArray = new Array(this.array.length * 2); for(let i=0; i

Solution

1. Step 1: Understand resizing by copying

   To resize, create a new larger array and copy existing elements into it.

2. Step 2: Check each option

   A uses spread but adds empty elements, not doubling size properly; B creates new array, copies elements, then replaces original array; C only changes length property but does not copy elements; D pushes empty elements, not resizing properly.

3. Final Answer:

   const newArray = new Array(this.array.length * 2); for(let i=0; i -> Option D

4. Quick Check:

   Copy elements to new larger array = B [OK]

Hint: Resize by copying elements to new bigger array [OK]

Common Mistakes:

• Only changing length without copying
• Using push to resize array
• Adding empty elements without copying

3. Consider this TypeScript code for a dynamic stack push operation:

push(value: number) {
  if (this.size === this.array.length) {
    const newArray = new Array(this.array.length * 2);
    for (let i = 0; i < this.array.length; i++) {
      newArray[i] = this.array[i];
    }
    this.array = newArray;
  }
  this.array[this.size] = value;
  this.size++;
}

If the initial array length is 2 and we push 3 elements: 10, 20, 30, what is the internal array state after these pushes?

medium

A. [10, 20, 30, undefined]

B. [10, 20, undefined, undefined]

C. [10, 20, 30, 0]

D. [10, 20, 30]

Solution

1. Step 1: Trace initial array and pushes

   Initial array length is 2, so after pushing 10 and 20, array is full.

2. Step 2: On pushing 30, array resizes to length 4 and copies elements 10, 20.

   Then 30 is added at index 2, size becomes 3.

3. Final Answer:

   [10, 20, 30, undefined] -> Option A

4. Quick Check:

   Resize doubles length, elements copied, new slot added [OK]

Hint: Resize doubles array, new elements added at next index [OK]

Common Mistakes:

• Forgetting to resize before adding third element
• Assuming array length stays 2
• Confusing undefined with 0

4. Given this pop method for a dynamic stack:

pop(): number | undefined {
  if (this.size === 0) return undefined;
  this.size--;
  const value = this.array[this.size];
  this.array[this.size] = undefined;
  if (this.size > 0 && this.size === Math.floor(this.array.length / 4)) {
    const newArray = new Array(Math.floor(this.array.length / 2));
    for (let i = 0; i < this.size; i++) {
      newArray[i] = this.array[i];
    }
    this.array = newArray;
  }
  return value;
}

What is the bug in this code?

medium

A. It does not check for empty stack before popping.

B. It sets popped element to undefined before copying, losing data.

C. It shrinks the array too early, causing frequent resizing.

D. It does not update the size after popping.

Solution

1. Step 1: Analyze order of operations

   The code sets this.array[this.size] = undefined before copying elements to newArray.

2. Step 2: Understand effect on copying

   When copying, the popped element is already undefined, so data is lost if resizing happens now.

3. Final Answer:

   It sets popped element to undefined before copying, losing data. -> Option B

4. Quick Check:

   Clear after copying to avoid data loss [OK]

Hint: Clear popped slot after resizing to keep data safe [OK]

Common Mistakes:

• Ignoring order of clearing and copying
• Shrinking array too often is not the main bug here
• Missing empty stack check is false here

5. You want to implement a dynamic stack using a resizable array that shrinks its size when the number of elements falls below one-quarter of the array length. Which approach below correctly avoids frequent resizing when pushing and popping many elements?

hard

A. Resize array to double size on push when full, and halve size on pop when size is exactly one-quarter of array length.

B. Resize array to double size on push when full, and halve size on pop when size is less than or equal to one-quarter of array length.

C. Resize array to double size on push when full, and halve size on pop only when size is less than one-quarter of array length and array length is greater than initial capacity.

D. Resize array to double size on push when full, and halve size on pop whenever size decreases.

Solution

1. Step 1: Understand resizing conditions

   Doubling on push when full is standard. Halving on pop should avoid frequent resizing.

2. Step 2: Avoid frequent resizing by checking size and minimum capacity

   Only halve when size is less than one-quarter and array length is above initial capacity to prevent shrinking too small.

3. Final Answer:

   Resize array to double size on push when full, and halve size on pop only when size is less than one-quarter of array length and array length is greater than initial capacity. -> Option C

4. Quick Check:

   Resize carefully to avoid thrashing [OK]

Hint: Shrink only if size < 1/4 and array bigger than initial [OK]

Common Mistakes:

• Shrinking too early causing many resizes
• Shrinking when size equals one-quarter causing thrashing
• Shrinking below initial capacity