List patterns in C Sharp (C#) - Time & Space Complexity

Time Complexity: List patterns

O(n)

Understanding Time Complexity

When working with lists, it is important to know how the time to complete tasks changes as the list grows.

We want to understand how operations like searching or iterating through a list take more or less time depending on the list size.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

List<int> numbers = new List<int> {1, 2, 3, 4, 5};
int target = 3;

bool found = false;
foreach (int num in numbers)
{
    if (num == target)
    {
        found = true;
        break;
    }
}

This code searches for a target number in a list by checking each item one by one until it finds the target or reaches the end.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through the list items one by one.
• How many times: Up to once for each item in the list until the target is found or the list ends.

How Execution Grows With Input

As the list gets bigger, the number of checks grows roughly the same as the list size.

Input Size (n)	Approx. Operations
10	Up to 10 checks
100	Up to 100 checks
1000	Up to 1000 checks

Pattern observation: The number of operations grows directly with the size of the list.

Final Time Complexity

Time Complexity: O(n)

This means the time to find the target grows in a straight line with the list size.

Common Mistake

[X] Wrong: "Searching a list always takes the same time no matter how big it is."

[OK] Correct: Because the program may need to check many items, the time grows as the list grows.

Interview Connect

Understanding how list operations scale helps you explain your code choices clearly and shows you know how to write efficient programs.

Self-Check

"What if we used a sorted list and applied binary search? How would the time complexity change?"

Practice

1. What does the list pattern [] match in C#?

easy

A. An empty list with no elements

B. A list with exactly one element

C. A list with two or more elements

D. Any list regardless of elements

Solution

1. Step 1: Understand the empty list pattern

   The pattern [] is used to match lists that have no elements at all.

2. Step 2: Compare with other list patterns

   Patterns like [var x] match one element, and [var x, .. var rest] match lists with multiple elements, so they don't match empty lists.

3. Final Answer:

   An empty list with no elements -> Option A

4. Quick Check:

   Empty list = [] pattern [OK]

Hint: Empty list pattern is just empty brackets [] [OK]

Common Mistakes:

• Confusing [] with single element pattern
• Thinking [] matches any list
• Assuming [] matches lists with elements

2. Which of the following is the correct syntax to match a list with exactly one element using list patterns in C#?

easy

A. [var x, .. var rest]

B. [var x]

C. [.. var rest]

D. []

Solution

1. Step 1: Identify the pattern for one element

   The pattern [var x] matches a list with exactly one element, binding it to x.

2. Step 2: Understand other patterns

   [var x, .. var rest] matches lists with at least one element plus the rest, [.. var rest] matches any list, and [] matches empty lists.

3. Final Answer:

   [var x] -> Option B

4. Quick Check:

   One element list = [var x] [OK]

Hint: One element list uses [var x] syntax [OK]

Common Mistakes:

• Using [var x, .. var rest] for single element
• Using [] for single element list
• Confusing .. var rest with single element

3. What is the output of this C# code snippet using list patterns?

var list = new List<int> { 5, 10, 15 };
switch (list)
{
    case []:
        Console.WriteLine("Empty");
        break;
    case [var x]:
        Console.WriteLine($"One element: {x}");
        break;
    case [var x, .. var rest]:
        Console.WriteLine($"First: {x}, Rest count: {rest.Count}");
        break;
}

medium

A. Empty

B. One element: 5

C. No match

D. First: 5, Rest count: 2

Solution

1. Step 1: Analyze the list contents

   The list has three elements: 5, 10, and 15.

2. Step 2: Match the list pattern cases

   The first case matches empty list, which is false. The second case matches exactly one element, which is false. The third case matches a list with at least one element: [var x, .. var rest]. Here, x is 5, and rest contains 10 and 15, so count is 2.

3. Final Answer:

   First: 5, Rest count: 2 -> Option D

4. Quick Check:

   List with 3 elements matches [x, ..rest] pattern [OK]

Hint: More than one element matches [x, ..rest] pattern [OK]

Common Mistakes:

• Choosing empty or one element case incorrectly
• Miscounting rest elements
• Ignoring pattern order in switch

4. Identify the error in this C# code using list patterns:

var numbers = new List<int> { 1, 2, 3 };
if (numbers is [var first, var second])
{
    Console.WriteLine($"First: {first}, Second: {second}");
}

medium

A. The variable names first and second are invalid

B. List patterns cannot be used with List<int>

C. The pattern [var first, var second] requires exactly two elements, but list has three

D. Missing else block after if

Solution

1. Step 1: Understand the pattern [var first, var second]

   This pattern matches lists with exactly two elements, binding them to first and second.

2. Step 2: Check the list size

   The list has three elements: 1, 2, and 3, so it does not match the pattern requiring exactly two elements.

3. Final Answer:

   The pattern [var first, var second] requires exactly two elements, but list has three -> Option C

4. Quick Check:

   Pattern length must match list length exactly [OK]

Hint: Pattern length must match list length exactly [OK]

Common Mistakes:

• Assuming pattern matches partial list
• Thinking variable names cause error
• Ignoring list size in pattern matching

5. Given a list of integers, how can you use list patterns in C# to check if the list starts with 1 and has at least two elements? Choose the correct pattern.

hard

A. [1, var second, .. var rest]

B. [var first, 1, .. var rest]

C. [1, .. var rest]

D. [.. var rest, 1]

Solution

1. Step 1: Understand the requirement

   The list must start with 1, then have a second element, and then zero or more elements after that (at least two elements total).

2. Step 2: Analyze each pattern

   [1, var second, .. var rest]: [1, var second, .. var rest] matches a list starting with 1, then a second element, then the rest (zero or more). This fits the requirement.
   [var first, 1, .. var rest]: [var first, 1, .. var rest] matches lists where the second element is 1, not the first.
   [1, .. var rest]: [1, .. var rest] matches lists starting with 1 but allows zero or more elements after, so it matches lists with only one element too.
   [.. var rest, 1]: [.. var rest, 1] matches lists ending with 1, not starting.

3. Final Answer:

   [1, var second, .. var rest] -> Option A

4. Quick Check:

   Start with 1 and at least two elements = [1, var second, .. rest] [OK]

Hint: Start with 1 and two elements uses [1, var second, .. rest] [OK]

Common Mistakes:

• Confusing element positions in pattern
• Using patterns that allow only one element
• Matching end of list instead of start