Array Deletion at End in DSA Rust - Time & Space Complexity

Time Complexity: Array Deletion at End

O(1)

Understanding Time Complexity

We want to understand how fast it is to remove an item from the end of an array.

This helps us know how the work grows when the array gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

fn delete_last_element(arr: &mut Vec<i32>) {
    if !arr.is_empty() {
        arr.pop();
    }
}
    

This code removes the last element from a dynamic array if it is not empty.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Removing the last element using pop().
• How many times: This operation happens once per call.

How Execution Grows With Input

Removing the last element takes the same amount of work no matter how big the array is.

Input Size (n)	Approx. Operations
10	1
100	1
1000	1

Pattern observation: The work stays constant as the array grows.

Final Time Complexity

Time Complexity: O(1)

This means removing the last item takes the same small amount of time no matter how big the array is.

Common Mistake

[X] Wrong: "Removing the last element takes longer if the array is bigger because it has to shift all elements."

[OK] Correct: When deleting at the end, no elements need to move. Only the last slot is removed, so the time stays the same.

Interview Connect

Knowing that deleting at the end is very fast helps you choose the right data structure for tasks where you add and remove items often.

Self-Check

"What if we changed to deleting the first element instead? How would the time complexity change?"

Practice

1. What happens when you remove the last element from a Rust Vec using pop()?

easy

A. The last element is removed and returned as Some(value).

B. The first element is removed and returned.

C. The entire vector is cleared.

D. The vector becomes immutable.

Solution

1. Step 1: Understand pop() behavior

   The pop() method removes the last element from the vector and returns it wrapped in Some(value) if the vector is not empty.

2. Step 2: Confirm it does not affect other elements

   Only the last element is removed; the rest of the vector remains unchanged.

3. Final Answer:

   The last element is removed and returned as Some(value). -> Option A

4. Quick Check:

   pop() removes last element [OK]

Hint: pop() removes and returns last element wrapped in Some [OK]

Common Mistakes:

• Thinking pop() removes the first element
• Assuming pop() clears the entire vector
• Believing pop() makes vector immutable

2. Which of the following is the correct syntax to remove the last element from a mutable vector v in Rust?

easy

A. v.erase_last();

B. v.remove_last();

C. v.delete_end();

D. v.pop();

Solution

1. Step 1: Recall Rust vector methods

   The standard method to remove the last element from a vector is pop().

2. Step 2: Check method names

   Methods like remove_last(), delete_end(), and erase_last() do not exist in Rust's Vec API.

3. Final Answer:

   v.pop(); -> Option D

4. Quick Check:

   Correct method to remove last element is pop() [OK]

Hint: Use pop() to remove last element from vector [OK]

Common Mistakes:

• Using non-existent methods like remove_last()
• Confusing pop() with remove() which removes by index
• Trying to use erase_last() or delete_end() which are invalid

3. What is the output of the following Rust code?

let mut v = vec![10, 20, 30];
let x = v.pop();
println!("{:?}", v);
println!("{:?}", x);

medium

A. [10, 20]
None

B. [10, 20, 30]
None

C. [10, 20]
Some(30)

D. [20, 30]
Some(10)

Solution

1. Step 1: Understand pop() effect on vector

   The pop() removes the last element, which is 30, and returns Some(30).

2. Step 2: Check vector after pop

   After removal, the vector contains [10, 20].

3. Final Answer:

   [10, 20] Some(30) -> Option C

4. Quick Check:

   pop() removes last element 30, vector left with [10, 20] [OK]

Hint: pop() returns last element and shortens vector [OK]

Common Mistakes:

• Expecting pop() to remove first element
• Assuming pop() returns None when vector is not empty
• Confusing vector contents after pop

4. Identify the error in the following Rust code that tries to remove the last element from a vector:

let v = vec![1, 2, 3];
v.pop();

medium

A. pop() method does not exist for vectors.

B. Cannot call pop() on an immutable vector.

C. pop() removes the first element, not the last.

D. The vector must be empty before calling pop().

Solution

1. Step 1: Check vector mutability

   The vector v is declared immutable with let. To modify it, it must be mutable.

2. Step 2: Understand pop() requirements

   The pop() method requires a mutable vector to remove the last element.

3. Final Answer:

   Cannot call pop() on an immutable vector. -> Option B

4. Quick Check:

   pop() needs mutable vector [OK]

Hint: Make vector mutable with 'mut' before pop() [OK]

Common Mistakes:

• Trying to pop from immutable vector
• Thinking pop() removes first element
• Assuming pop() works on empty vector without error

5. Given a vector v with elements [5, 10, 15, 20], write Rust code to remove the last two elements and print the resulting vector. What will be printed?

hard

A. [5, 10]

B. [5, 10, 15]

C. [15, 20]

D. [5, 10, 15, 20]

Solution

1. Step 1: Remove last element twice using pop()

   Calling pop() twice removes 20 then 15, leaving [5, 10].

2. Step 2: Print the vector after removals

   Printing v now shows [5, 10].

3. Final Answer:

   [5, 10] -> Option A

4. Quick Check:

   Two pops remove last two elements [OK]

Hint: Call pop() twice to remove last two elements [OK]

Common Mistakes:

• Removing only one element instead of two
• Confusing pop() with remove(index)
• Expecting vector to be empty after two pops