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
OutputSuccess
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.