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?"

Practice

1. What does the "First and Last Occurrence of Element" problem ask you to find in an array?

easy

A. The number of unique elements in the array

B. The sum of all elements in the array

C. The maximum and minimum values in the array

D. The first and last positions where a given element appears

Solution

1. Step 1: Understand the problem statement

   The problem asks to find the first and last positions of a specific element in an array.

2. Step 2: Identify what is being searched

   We look for the first index and last index where the element appears.

3. Final Answer:

   The first and last positions where a given element appears -> Option D

4. Quick Check:

   First and last occurrence = positions of element [OK]

Hint: Look for start and end indexes of the element [OK]

Common Mistakes:

• Confusing with sum or count of elements
• Looking for max/min values instead
• Ignoring the order of occurrences

2. Which of the following JavaScript code snippets correctly finds the first occurrence index of element 5 in array [1, 5, 3, 5, 7]?

easy

A. array.indexOf(5)

B. array.findIndex(5)

C. array.lastIndexOf(5)

D. array.find(5)

Solution

1. Step 1: Recall JavaScript methods for finding index

   indexOf returns the first index of the element, lastIndexOf returns the last index.

2. Step 2: Check method usage

   array.indexOf(5) correctly returns the first occurrence index of 5.

3. Final Answer:

   array.indexOf(5) -> Option A

4. Quick Check:

   indexOf finds first occurrence [OK]

Hint: Use indexOf for first occurrence, lastIndexOf for last [OK]

Common Mistakes:

• Using findIndex incorrectly with a value instead of a function
• Using find which returns element, not index
• Confusing lastIndexOf with first occurrence

3. What will be the output of the following code?

const arr = [2, 4, 6, 4, 8];
const first = arr.indexOf(4);
const last = arr.lastIndexOf(4);
console.log([first, last]);

medium

A. [2, 4]

B. [3, 1]

C. [1, 3]

D. [0, 4]

Solution

1. Step 1: Find first occurrence of 4 in array

   4 appears first at index 1.

2. Step 2: Find last occurrence of 4 in array

   4 appears last at index 3.

3. Final Answer:

   [1, 3] -> Option C

4. Quick Check:

   First = 1, Last = 3 [OK]

Hint: indexOf gives first, lastIndexOf gives last [OK]

Common Mistakes:

• Mixing up first and last indexes
• Using wrong array indexes
• Confusing element values with indexes

4. Identify the error in the following code that tries to find the first and last occurrence of 7 in array [7, 2, 7, 5]:

const arr = [7, 2, 7, 5];
const first = arr.findIndex(7);
const last = arr.findLastIndex(7);
console.log([first, last]);

medium

A. findLastIndex is not a valid JavaScript method

B. findIndex and findLastIndex require a function, not a value

C. The array does not contain 7, so indexes are -1

D. The code is correct and will output [0, 2]

Solution

1. Step 1: Check usage of findIndex and findLastIndex

   Both methods require a function as argument, not a direct value.

2. Step 2: Identify the error in argument

   Passing 7 directly causes incorrect usage; should pass a function like x => x === 7.

3. Final Answer:

   findIndex and findLastIndex require a function, not a value -> Option B

4. Quick Check:

   Methods need function argument [OK]

Hint: Pass a function to findIndex, not a direct value [OK]

Common Mistakes:

• Passing value instead of function to findIndex
• Assuming findLastIndex exists in all JS versions
• Confusing findIndex with indexOf

5. Given an array arr = [3, 5, 3, 7, 5, 3], write a function in JavaScript that returns an object with the first and last occurrence indexes of element 3. What will be the output of findOccurrences(arr, 3)?

function findOccurrences(array, element) {
  return {
    first: array.indexOf(element),
    last: array.lastIndexOf(element)
  };
}

const arr = [3, 5, 3, 7, 5, 3];
console.log(findOccurrences(arr, 3));

hard

A. {"first": 0, "last": 5}

B. {"first": 2, "last": 5}

C. {"first": 1, "last": 4}

D. {"first": 0, "last": 2}

Solution

1. Step 1: Find first occurrence of 3 in array

   3 first appears at index 0.

2. Step 2: Find last occurrence of 3 in array

   3 last appears at index 5.

3. Final Answer:

   {"first": 0, "last": 5} -> Option A

4. Quick Check:

   First = 0, Last = 5 [OK]

Hint: Use indexOf and lastIndexOf to get first and last indexes [OK]

Common Mistakes:

• Mixing up first and last indexes
• Returning values instead of indexes
• Incorrectly reading array indexes