Matching multiple patterns in Rust - Time & Space Complexity

Time Complexity: Matching multiple patterns

O(n)

Understanding Time Complexity

When we match multiple patterns in Rust, we want to know how long it takes as the input changes.

We ask: How does the time grow when we check many patterns?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

fn check_number(num: i32) {
    match num {
        1 | 2 | 3 => println!("Small number"),
        4 | 5 | 6 => println!("Medium number"),
        _ => println!("Other number"),
    }
}
    

This code checks if a number matches any of several patterns grouped with | (or).

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Checking the input against each pattern in order.
• How many times: Up to the number of patterns until a match is found.

How Execution Grows With Input

As the number of patterns grows, the checks grow too, but only until a match is found.

Input Size (patterns)	Approx. Operations
3	Up to 3 checks
10	Up to 10 checks
100	Up to 100 checks

Pattern observation: The number of checks grows linearly with the number of patterns.

Final Time Complexity

Time Complexity: O(n)

This means the time to match grows in a straight line as you add more patterns.

Common Mistake

[X] Wrong: "Matching multiple patterns happens all at once, so time stays the same no matter how many patterns."

[OK] Correct: Rust checks patterns one by one until it finds a match, so more patterns mean more checks in the worst case.

Interview Connect

Understanding how pattern matching time grows helps you write clear and efficient code, a skill valued in many coding challenges and real projects.

Self-Check

"What if we changed the patterns to use ranges instead of individual values? How would the time complexity change?"

Practice

1. In Rust, which symbol is used to match multiple patterns in a single match arm?

easy

A. |

B. &

C. +

D. &&

Solution

1. Step 1: Recall the syntax for matching multiple patterns

   Rust uses the vertical bar | to separate multiple patterns in one match arm.

2. Step 2: Identify the correct symbol

   The symbol | means "or" in pattern matching, allowing multiple cases to be handled together.

3. Final Answer:

   | -> Option A

4. Quick Check:

   Multiple patterns use | in match arms [OK]

Hint: Use | to combine patterns in one match arm [OK]

Common Mistakes:

• Using & instead of |
• Confusing + with pattern separator
• Using && which is logical AND, not pattern OR

2. Which of the following Rust match arms correctly matches the values 1, 2, or 3 using multiple patterns?

easy

A. 1 & 2 & 3 => println!("Matched 1, 2, or 3"),

B. 1 | 2 | 3 => println!("Matched 1, 2, or 3"),

C. 1 + 2 + 3 => println!("Matched 1, 2, or 3"),

D. 1, 2, 3 => println!("Matched 1, 2, or 3"),

Solution

1. Step 1: Check the syntax for multiple patterns

   Rust uses | to separate multiple patterns in a match arm, so 1 | 2 | 3 is correct.

2. Step 2: Identify incorrect options

   & is not used for matching multiple patterns, + is arithmetic, and commas are invalid here.

3. Final Answer:

   1 | 2 | 3 => println!("Matched 1, 2, or 3"), -> Option B

4. Quick Check:

   Multiple patterns use | separator [OK]

Hint: Separate patterns with | inside match arms [OK]

Common Mistakes:

• Using & instead of | for multiple patterns
• Trying to separate patterns with commas
• Using + which is arithmetic, not pattern matching

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

let x = 2;
match x {
    1 | 2 | 3 => println!("Small number"),
    4 | 5 | 6 => println!("Medium number"),
    _ => println!("Other number"),
}

medium

A. Compilation error

B. Medium number

C. Small number

D. Other number

Solution

1. Step 1: Identify which pattern matches x=2

   The first arm matches 1, 2, or 3. Since x is 2, it matches this arm.

2. Step 2: Determine the output

   The matched arm prints "Small number" to the console.

3. Final Answer:

   Small number -> Option C

4. Quick Check:

   2 matches 1|2|3 arm [OK]

Hint: Check which pattern includes the value [OK]

Common Mistakes:

• Choosing Medium number for 2
• Thinking _ arm matches first
• Assuming syntax error due to multiple patterns

4. Find the error in this Rust code snippet that tries to match multiple patterns:

let ch = 'a';
match ch {
    'a' | 'e' | 'i' | 'o' | 'u' => println!("Vowel"),
    'a' | 'b' => println!("Letter a or b"),
    _ => println!("Other"),
}

medium

A. Missing semicolon after println! macros

B. Match expression missing a default arm

C. Incorrect use of | operator for multiple patterns

D. Duplicate pattern 'a' in multiple arms causes unreachable code

Solution

1. Step 1: Identify duplicate patterns in match arms

   The character 'a' appears in both the first and second arms, causing the second arm's 'a' pattern to be unreachable.

2. Step 2: Understand Rust's pattern matching rules

   Rust does not allow unreachable patterns; the compiler will warn or error about the duplicate 'a'.

3. Final Answer:

   Duplicate pattern 'a' in multiple arms causes unreachable code -> Option D

4. Quick Check:

   Duplicate patterns cause unreachable code errors [OK]

Hint: Avoid repeating same pattern in multiple match arms [OK]

Common Mistakes:

• Ignoring unreachable pattern warnings
• Thinking | is invalid for multiple patterns
• Missing default arm (actually present here)

5. You want to write a Rust function that returns "Weekend" for Saturday or Sunday, "Weekday" for Monday to Friday, and "Invalid" otherwise. Which match arm correctly uses multiple patterns to do this?

fn day_type(day: &str) -> &str {
    match day {
        ? => "Weekend",
        ? => "Weekday",
        _ => "Invalid",
    }
}

hard

A. "Saturday" | "Sunday",
"Monday" | "Tuesday" | "Wednesday" | "Thursday" | "Friday"

B. "Saturday", "Sunday",
"Monday", "Tuesday", "Wednesday", "Thursday", "Friday"

C. "Saturday" & "Sunday",
"Monday" & "Tuesday" & "Wednesday" & "Thursday" & "Friday"

D. "Saturday" + "Sunday",
"Monday" + "Tuesday" + "Wednesday" + "Thursday" + "Friday"

Solution

1. Step 1: Use | to match multiple string patterns in one arm

   Rust allows multiple patterns separated by | to group cases like "Saturday" | "Sunday".

2. Step 2: Check other options for invalid syntax

   Commas separate arms, not patterns; & and + are invalid for pattern matching.

3. Final Answer:

   "Saturday" | "Sunday", "Monday" | "Tuesday" | "Wednesday" | "Thursday" | "Friday" -> Option A

4. Quick Check:

   Use | to combine multiple string patterns [OK]

Hint: Use | to combine multiple string patterns in match arms [OK]

Common Mistakes:

• Using commas instead of | inside match arms
• Using & or + which are invalid for patterns
• Forgetting to cover all weekdays or weekend days