First and Last Occurrence of Element in DSA Go - Time & Space Complexity

Time Complexity: First and Last Occurrence of Element

O(n)

Understanding Time Complexity

We want to know how long it takes to find the first and last positions of a number in a list.

How does the time needed change when the list gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

func firstAndLastOccurrence(arr []int, target int) (int, int) {
    first, last := -1, -1
    for i := 0; i < len(arr); i++ {
        if arr[i] == target {
            if first == -1 {
                first = i
            }
            last = i
        }
    }
    return first, last
}

This code finds the first and last places where the target number appears in the list.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: One loop that goes through each item in the list once.
• How many times: Exactly once for each item in the list, from start to end.

How Execution Grows With Input

As the list gets bigger, the time to check each item grows directly with the size.

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

Pattern observation: The number of checks grows evenly as the list grows.

Final Time Complexity

Time Complexity: O(n)

This means the time needed grows in a straight line with the size of the list.

Common Mistake

[X] Wrong: "Since we only want first and last, we can stop early and the time is always small."

[OK] Correct: The code checks every item to find the last occurrence, so it must look at the whole list in the worst case.

Interview Connect

Understanding this helps you explain how searching through data works and shows you can analyze simple loops clearly.

Self-Check

"What if we used binary search on a sorted list to find the first and last occurrence? How would the time complexity change?"