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

Time Complexity: First and Last Occurrence of Element

O(n)

Understanding Time Complexity

We want to know how the time to find the first and last positions of a number in a list grows as the list gets bigger.

How does the number of steps change when the list size increases?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function firstAndLastOccurrence(arr, target) {
  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 appears first and last.

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 as many times as there are items in the list (n times).

How Execution Grows With Input

As the list gets bigger, the number of steps grows directly with the size of the list.

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

Pattern observation: Doubling the list size roughly doubles the work done.

Final Time Complexity

Time Complexity: O(n)

This means the time to find the first and last occurrence grows in a straight line with the list size.

Common Mistake

[X] Wrong: "Since we only want two positions, we can stop as soon as we find the first occurrence, so it's always fast."

[OK] Correct: We must check the whole list to find the last occurrence, so the loop runs through all items in the worst case.

Interview Connect

Understanding how to analyze simple loops like this helps you explain your code clearly and shows you know how work grows with input size.

Self-Check

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