First and Last Occurrence of Element in DSA Javascript

Mental Model

Find where a number first appears and last appears in a list by checking each item one by one.

Analogy: Imagine looking through a row of books to find the first and last time a certain title shows up on the shelf.

Array: [3, 5, 2, 5, 7, 5, 9]
Indexes:  0  1  2  3  4  5  6
Target: 5

Dry Run Walkthrough

Input: array: [3, 5, 2, 5, 7, 5, 9], target: 5

Goal: Find the first and last positions where 5 appears in the array

Step 1: Check element at index 0 (3), not target

[3, 5, 2, 5, 7, 5, 9]
first = -1, last = -1

Why: We start from the beginning to find the first occurrence

Step 2: Check element at index 1 (5), matches target, set first and last to 1

[3, 5, 2, 5, 7, 5, 9]
first = 1, last = 1

Why: First time we see 5, record index as first and last

Step 3: Check element at index 2 (2), not target

[3, 5, 2, 5, 7, 5, 9]
first = 1, last = 1

Why: Keep looking for later occurrences

Step 4: Check element at index 3 (5), matches target, update last to 3

[3, 5, 2, 5, 7, 5, 9]
first = 1, last = 3

Why: Found another 5, update last occurrence

Step 5: Check element at index 4 (7), not target

[3, 5, 2, 5, 7, 5, 9]
first = 1, last = 3

Why: Keep searching

Step 6: Check element at index 5 (5), matches target, update last to 5

[3, 5, 2, 5, 7, 5, 9]
first = 1, last = 5

Why: Found last occurrence so far

Step 7: Check element at index 6 (9), not target

[3, 5, 2, 5, 7, 5, 9]
first = 1, last = 5

Why: End of array reached

Result:

First occurrence at index 1, last occurrence at index 5

Annotated Code

DSA Javascript

class ArraySearch {
  static findFirstAndLastOccurrence(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; // record first occurrence
        }
        last = i; // update last occurrence
      }
    }
    return { first, last };
  }
}

// Driver code
const array = [3, 5, 2, 5, 7, 5, 9];
const target = 5;
const result = ArraySearch.findFirstAndLastOccurrence(array, target);
console.log(`First occurrence at index ${result.first}, last occurrence at index ${result.last}`);

for (let i = 0; i < arr.length; i++) {

iterate through each element to check for target

if (arr[i] === target) {

check if current element matches target

if (first === -1) { first = i; }

record first occurrence only once

last = i;

update last occurrence every time target found

Output

First occurrence at index 1, last occurrence at index 5

Complexity Analysis

Time: O(n) because we scan the entire array once to find occurrences

Space: O(1) because we only store two indexes regardless of input size

vs Alternative: Better than searching twice separately for first and last occurrence, which would be O(2n)

Edge Cases

Empty array

Returns first = -1 and last = -1 indicating target not found

DSA Javascript

for (let i = 0; i < arr.length; i++) {

Target not in array

Returns first = -1 and last = -1 indicating target not found

DSA Javascript

if (arr[i] === target) {

Array with one element equal to target

Returns first and last both equal to 0

DSA Javascript

if (first === -1) { first = i; }

When to Use This Pattern

When asked to find positions of an element's first and last appearance in a list, use a single pass scan updating indexes to solve efficiently.

Common Mistakes

Mistake: Updating first occurrence every time target is found
Fix: Only set first occurrence when it is still -1 (not set yet)

Mistake: Not initializing first and last to -1, causing wrong results when target not found
Fix: Initialize first and last to -1 to indicate target absence

Summary

Finds the first and last positions of a target element in an array.

Use when you need to know where an element starts and ends in a list.

Remember to scan once, set first occurrence once, and update last occurrence every time.

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