First and Last Occurrence of Element in DSA Typescript

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: [5, 3, 7, 3, 9, 3, 2]
Indexes:  0  1  2  3  4  5  6
We want to find first and last position of 3.

Dry Run Walkthrough

Input: list: [5, 3, 7, 3, 9, 3, 2], find element 3

Goal: Find the first and last index where 3 appears in the list

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

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

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

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

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

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

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

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

Why: No change, keep looking

Step 4: Check element at index 3 (3), matches target

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

Why: Update last occurrence to index 3

Step 5: Check element at index 4 (9), not 3

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

Why: No change, continue

Step 6: Check element at index 5 (3), matches target

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

Why: Update last occurrence to index 5

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

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

Why: No change, finished scanning

Result:

Final: first occurrence = 1, last occurrence = 5

Annotated Code

DSA Typescript

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

// Driver code
const arr = [5, 3, 7, 3, 9, 3, 2];
const target = 3;
const [first, last] = FirstLastOccurrence.findFirstAndLast(arr, target);
console.log(`First occurrence of ${target}: ${first}`);
console.log(`Last occurrence of ${target}: ${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 index if not set yet

last = i;

update last occurrence index to current

Output

First occurrence of 3: 1

Last occurrence of 3: 5

Complexity Analysis

Time: O(n) because we scan the entire list 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; this does both in one pass

Edge Cases

Empty array

Returns [-1, -1] indicating target not found

DSA Typescript

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

Target not in array

Returns [-1, -1] since no match found

DSA Typescript

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

Target appears once

First and last occurrence are the same index

DSA Typescript

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 first and last indexes.

Common Mistakes

Mistake: Searching for first and last occurrence in separate loops
Fix: Combine into one loop to improve efficiency

Mistake: Not initializing first to -1 and assuming target is always found
Fix: Initialize first and last to -1 to handle target absence properly

Summary

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

Use when you need both positions efficiently in one pass.

Remember to update last occurrence every time you find the target, and set first only once.