First and Last Occurrence of Element in DSA Typescript - 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 place a number appears 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.

function firstAndLastOccurrence(arr: number[], target: number): [number, number] {
  let first = -1;
  let last = -1;
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) {
      if (first === -1) first = i;
      last = i;
    }
  }
  return [first, last];
}
    

This code looks through the list once to find where the target number first and last appear.

Identify Repeating Operations

• Primary operation: One loop that goes through each item in the list once.
• How many times: Exactly once for each item, so as many times as the list length.

How Execution Grows With Input

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

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

Pattern observation: The number of steps 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 time is constant."

[OK] Correct: We must check every item to be sure the last occurrence is found, so time grows with list size.

Interview Connect

Understanding how loops affect time helps you explain your code clearly and choose better methods when needed.

Self-Check

"What if the list was sorted? How would that change the time complexity of finding first and last occurrences?"