Array Access and Update at Index in DSA Rust - Time & Space Complexity

Time Complexity: Array Access and Update at Index

O(1)

Understanding Time Complexity

We want to understand how fast we can get or change a value in an array at a certain position.

The question is: how does the time to access or update an element change as the array grows?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

fn access_and_update(arr: &mut [i32], index: usize, new_value: i32) {
    let _ = arr[index];       // Access element at index
    arr[index] = new_value;   // Update element at index
}
    

This code accesses an element at a given index and then updates it with a new value.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Direct access and update at a single index in the array.
• How many times: Exactly once each for access and update, no loops or recursion.

How Execution Grows With Input

Accessing or updating an element at a specific index takes the same amount of time no matter how big the array is.

Input Size (n)	Approx. Operations
10	2 (1 access + 1 update)
100	2 (1 access + 1 update)
1000	2 (1 access + 1 update)

Pattern observation: The number of operations stays the same regardless of array size.

Final Time Complexity

Time Complexity: O(1)

This means accessing or updating an element at any index takes a constant amount of time, no matter how large the array is.

Common Mistake

[X] Wrong: "Accessing an element takes longer if the array is bigger because it has to look through all elements."

[OK] Correct: Arrays allow direct access by index, so the computer jumps straight to the spot without checking others.

Interview Connect

Knowing that array access and update are constant time helps you understand why arrays are great for quick lookups and changes by position.

Self-Check

"What if we had to search for a value instead of knowing the index? How would the time complexity change?"

Practice

1. What does the expression arr[2] do in Rust when arr is an array?

easy

A. Removes the element at index 2

B. Adds 2 to every element in the array

C. Accesses the element at index 2 of the array

D. Returns the length of the array

Solution

1. Step 1: Understand array indexing

   In Rust, arrays use zero-based indexing, so arr[2] accesses the third element.

2. Step 2: Identify the operation

   The expression retrieves the value stored at index 2 without modifying the array.

3. Final Answer:

   Accesses the element at index 2 of the array -> Option C

4. Quick Check:

   arr[2] means element at index 2 [OK]

Hint: Remember arrays start at index 0 in Rust [OK]

Common Mistakes:

• Thinking indexing starts at 1
• Confusing access with modification
• Assuming it returns array length

2. Which of the following is the correct syntax to update the element at index 1 of a mutable array arr to 10 in Rust?

easy

A. arr[1] = 10;

B. arr(1) = 10;

C. arr{1} = 10;

D. arr->1 = 10;

Solution

1. Step 1: Recall Rust array update syntax

   In Rust, to update an element, use square brackets with the index and assign a new value.

2. Step 2: Check each option

   Only arr[1] = 10; uses correct square bracket indexing and assignment syntax.

3. Final Answer:

   arr[1] = 10; -> Option A

4. Quick Check:

   Use square brackets for indexing and assignment [OK]

Hint: Use square brackets [] for indexing and assignment [OK]

Common Mistakes:

• Using parentheses () instead of brackets
• Using curly braces {} for indexing
• Using arrow operator -> incorrectly

3. What will be the output of the following Rust code?

fn main() {
    let mut arr = [5, 10, 15, 20];
    arr[2] = 25;
    println!("{:?}", arr);
}

medium

A. [5, 10, 15, 20]

B. Compilation error

C. [25, 10, 15, 20]

D. [5, 10, 25, 20]

Solution

1. Step 1: Analyze array initialization and update

   The array arr starts as [5, 10, 15, 20]. The statement arr[2] = 25; changes the element at index 2 (third element) from 15 to 25.

2. Step 2: Understand the print output

   The println!("{:?}", arr); prints the entire array showing the updated value.

3. Final Answer:

   [5, 10, 25, 20] -> Option D

4. Quick Check:

   Updated index 2 to 25, array prints updated [OK]

Hint: Remember index 2 is third element, updated value shows in print [OK]

Common Mistakes:

• Thinking index 2 is second element
• Assuming original array prints without update
• Expecting compilation error due to mutability

4. Identify the error in the following Rust code snippet:

fn main() {
    let arr = [1, 2, 3];
    arr[1] = 5;
    println!("{:?}", arr);
}

medium

A. Cannot assign to element of immutable array

B. Index out of bounds error

C. Syntax error in array declaration

D. Missing semicolon after assignment

Solution

1. Step 1: Check array mutability

   The array arr is declared without mut, so it is immutable and cannot be changed.

2. Step 2: Identify assignment error

   The line arr[1] = 5; tries to modify an immutable array element, causing a compile-time error.

3. Final Answer:

   Cannot assign to element of immutable array -> Option A

4. Quick Check:

   Immutable arrays cannot be updated [OK]

Hint: Declare array with 'mut' to allow updates [OK]

Common Mistakes:

• Ignoring mut keyword for mutability
• Assuming index out of bounds error
• Thinking syntax error causes failure

5. Given a mutable array arr of length 4 initialized as [2, 4, 6, 8], which code snippet correctly doubles the value at index 3 and then prints the updated array?

hard

A. arr[4] = arr[4] * 2;
println!("{:?}", arr);

B. arr[3] = arr[3] * 2;
println!("{:?}", arr);

C. arr[3] *= 2
println!("{:?}", arr);

D. arr[3] = arr[3] + 2;
println!("{:?}", arr);

Solution

1. Step 1: Identify correct index and operation

   Index 3 is the fourth element (value 8). Doubling means multiplying by 2, so arr[3] = arr[3] * 2; is correct.

2. Step 2: Check syntax and print statement

   arr[3] = arr[3] * 2; println!("{:?}", arr); uses correct syntax with semicolon and prints the updated array properly.

3. Final Answer:

   arr[3] = arr[3] * 2; println!("{:?}", arr); -> Option B

4. Quick Check:

   Multiply element at index 3 by 2, then print [OK]

Hint: Use correct index and multiply, remember semicolons [OK]

Common Mistakes:

• Using index 4 which is out of bounds
• Forgetting semicolon after assignment
• Adding 2 instead of multiplying by 2