Dynamic Stack Using Resizable Array in DSA Typescript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a dynamic stack using a resizable array?

A dynamic stack using a resizable array is a stack data structure that grows or shrinks its underlying array size automatically when elements are pushed or popped, allowing flexible memory use without fixed size limits.

intermediate

Why do we resize the array in a dynamic stack?

We resize the array to handle more elements when the stack is full (usually doubling the size) and to save memory when the stack is mostly empty (usually halving the size), keeping operations efficient and memory use balanced.

beginner

What happens when you push an element on a full dynamic stack array?

When pushing on a full dynamic stack array, the array size is doubled, all existing elements are copied to the new larger array, and then the new element is added on top.

intermediate

How does popping elements affect the size of the dynamic stack array?

When popping elements causes the number of elements to drop below a certain threshold (like one-fourth of the array size), the array size is halved to free unused space, keeping memory efficient.

intermediate

What is the time complexity of push and pop operations in a dynamic stack using a resizable array?

Push and pop operations are usually O(1) on average (amortized) because resizing happens rarely. When resizing occurs, it takes O(n) time to copy elements, but this cost is spread out over many operations.

What triggers the resizing of the array in a dynamic stack?

A When the stack has exactly one element

B Only when the stack is empty

C When the stack is full or too empty

D Only when the stack is full

The array resizes when it is full (to grow) or when it is too empty (to shrink).

What is the usual new size of the array when it grows?

A Double the current size

B Half the current size

C Same size

D Triple the current size

The array size is usually doubled to accommodate more elements efficiently.

What is the main advantage of using a dynamic stack over a fixed-size stack?

A It is slower

B It uses less memory always

C It never needs resizing

D It can handle more elements without running out of space

Dynamic stacks can grow as needed, so they don't run out of space like fixed-size stacks.

What is the amortized time complexity of push operation in a dynamic stack?

A O(log n)

B O(1)

C O(n)

D O(n^2)

Push is O(1) on average because resizing happens rarely and its cost is spread out.

When shrinking the array, what is a common threshold to trigger resizing?

A When size is less than one-fourth of capacity

B When size is half of capacity

C When size is zero

D When size equals capacity

Shrinking usually happens when the number of elements is less than one-fourth of the array capacity.

Explain how a dynamic stack using a resizable array manages memory when pushing and popping elements.

Think about when and why the array size changes.

Describe the steps involved in pushing an element onto a full dynamic stack implemented with a resizable array.

Focus on what happens before adding the new element.

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