First and Last Occurrence of Element in DSA C

Mental Model

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

Analogy: Imagine a row of mailboxes with letters inside. You want to find the first and last mailbox that has a letter from your friend. You check each mailbox from start to end and remember the first and last times you see your friend's letter.

Array: [1] -> [2] -> [3] -> [2] -> [4] -> [2] -> null
Indices:  0      1      2      3      4      5

Dry Run Walkthrough

Input: array: [1, 2, 3, 2, 4, 2], target: 2

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

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

[1] -> [2] -> [3] -> [2] -> [4] -> [2] -> null
first = -1, last = -1

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

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

[1] -> [2] -> [3] -> [2] -> [4] -> [2] -> null
first = 1, last = 1

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

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

[1] -> [2] -> [3] -> [2] -> [4] -> [2] -> null
first = 1, last = 1

Why: No change since value is not target

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

[1] -> [2] -> [3] -> [2] -> [4] -> [2] -> null
first = 1, last = 3

Why: Update last occurrence to current index

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

[1] -> [2] -> [3] -> [2] -> [4] -> [2] -> null
first = 1, last = 3

Why: No change since value is not target

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

[1] -> [2] -> [3] -> [2] -> [4] -> [2] -> null
first = 1, last = 5

Why: Update last occurrence to current index

Result:

Final: first = 1, last = 5

Annotated Code

DSA C

#include <stdio.h>

void findFirstAndLastOccurrence(int arr[], int n, int target, int *first, int *last) {
    *first = -1;
    *last = -1;
    for (int i = 0; i < n; i++) {
        if (arr[i] == target) {
            if (*first == -1) {
                *first = i; // record first occurrence
            }
            *last = i; // update last occurrence
        }
    }
}

int main() {
    int arr[] = {1, 2, 3, 2, 4, 2};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 2;
    int first, last;

    findFirstAndLastOccurrence(arr, n, target, &first, &last);

    printf("First occurrence of %d is at index: %d\n", target, first);
    printf("Last occurrence of %d is at index: %d\n", target, last);

    return 0;
}

for (int i = 0; i < n; i++) {

iterate through each element in the array

if (arr[i] == target) {

check if current element matches the target

if (*first == -1) {

if first occurrence not set, set it now

*first = i; // record first occurrence

record index of first occurrence

*last = i; // update last occurrence

update last occurrence index to current

Output

First occurrence of 2 is at index: 1

Last occurrence of 2 is at index: 5

Complexity Analysis

Time: O(n) because we check each element once

Space: O(1) because we only store two indices

vs Alternative: This is better than searching twice (once for first and once for last) which would be O(2n). Here we do it in one pass.

Edge Cases

target not in array

first and last remain -1 indicating no occurrence

DSA C

if (*first == -1) {

array with one element equal to target

first and last both set to 0

DSA C

if (*first == -1) {

all elements are target

first is 0, last is last index

DSA C

*last = i; // update last occurrence

When to Use This Pattern

When asked to find the first and last position of a value in a list, use a single pass scan updating first and last indices to efficiently find both.

Common Mistakes

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

Mistake: Not initializing first to -1, causing wrong first occurrence
Fix: Initialize first to -1 before loop to detect first match correctly

Summary

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

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

Remember to scan once and update first and last indices as you go.

Practice

1. What does the term first occurrence of an element in an array mean?

easy

A. The last index where the element appears

B. The total count of the element in the array

C. The index of the first time the element appears in the array

D. The sum of all elements before the element

Solution

1. Step 1: Understand the meaning of first occurrence

   The first occurrence means the earliest position where the element is found in the array, starting from index 0.

2. Step 2: Compare options with definition

   The index of the first time the element appears in the array matches this definition exactly, while others describe different concepts.

3. Final Answer:

   The index of the first time the element appears in the array -> Option C

4. Quick Check:

   First occurrence = first index found [OK]

Hint: First occurrence means earliest index found [OK]

Common Mistakes:

• Confusing first occurrence with count of element
• Mixing first occurrence with last occurrence
• Thinking it means sum or total

2. Which of the following C code snippets correctly finds the first occurrence of x in array arr of size n?

easy

A. for(int i=0; i

B. for(int i=n-1; i>=0; i--) { if(arr[i] == x) return i; } return -1;

C. int i=0; while(arr[i] != x) i++; return i;

D. for(int i=0; i

Solution

1. Step 1: Analyze each code snippet

   for(int i=0; i

2. Step 2: Check other options for correctness

   for(int i=n-1; i>=0; i--) { if(arr[i] == x) return i; } return -1; searches from end, so it finds last occurrence. int i=0; while(arr[i] != x) i++; return i; may cause out-of-bound error if x not found. for(int i=0; i

3. Final Answer:

   for(int i=0; i -> Option A

4. Quick Check:

   Start to end loop with match check = for(int i=0; i

Hint: Loop from start, return index on first match [OK]

Common Mistakes:

• Looping backward for first occurrence
• Not handling element not found case
• Returning wrong index when element differs

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

int arr[] = {2, 4, 6, 4, 8};
int n = 5, x = 4;
int first = -1, last = -1;
for(int i=0; i

medium

A. 1 3

B. 3 1

C. 0 4

D. -1 -1

Solution

1. Step 1: Trace the loop to find first and last occurrence

   Array: [2,4,6,4,8], x=4. Loop i=0 to 4:
   i=0: arr[0]=2 !=4, skip
   i=1: arr[1]=4 ==4, first=-1 so first=1, last=1
   i=2: arr[2]=6 !=4, skip
   i=3: arr[3]=4 ==4, first=1 (unchanged), last=3
   i=4: arr[4]=8 !=4, skip

2. Step 2: Print first and last

   first=1, last=3

3. Final Answer:

   1 3 -> Option A

4. Quick Check:

   First=1, Last=3 indexes for 4 [OK]

Hint: Track first when unset, update last on every match [OK]

Common Mistakes:

• Swapping first and last values
• Not updating last occurrence
• Ignoring first occurrence initialization

4. Identify the error in the following code that tries to find the last occurrence of x in array arr of size n:

int lastOccurrence(int arr[], int n, int x) {
  int last = -1;
  for(int i=0; i

medium

A. Loop should run from n-1 to 0 for last occurrence

B. Using assignment (=) instead of comparison (==) in if condition

C. Variable last should be initialized to 0

D. Return statement should be inside the loop

Solution

1. Step 1: Check the if condition inside the loop

   The condition uses single '=' which is assignment, not comparison. This causes wrong behavior.

2. Step 2: Correct the condition

   It should be 'if(arr[i] == x)' to compare values properly.

3. Final Answer:

   Using assignment (=) instead of comparison (==) in if condition -> Option B

4. Quick Check:

   Use '==' for comparison, not '=' [OK]

Hint: Use '==' for comparison, '=' is assignment [OK]

Common Mistakes:

• Using '=' instead of '==' in conditions
• Loop direction confusion for last occurrence
• Wrong initialization of variables

5. Given a sorted array arr of size n with possible duplicates, which approach is the most efficient to find the first and last occurrence of element x?

hard

A. Sort the array again and then find occurrences

B. Traverse the array from start to end once to find both occurrences

C. Use linear search twice: once from start, once from end

D. Use two binary searches: one for first occurrence, one for last occurrence

Solution

1. Step 1: Understand the array is sorted

   Since the array is sorted, binary search can be used to find positions efficiently.

2. Step 2: Use binary search twice

   One binary search finds the first occurrence by moving left on matches, another finds last occurrence by moving right on matches.

3. Final Answer:

   Use two binary searches: one for first occurrence, one for last occurrence -> Option D

4. Quick Check:

   Sorted array + binary search = fastest method [OK]

Hint: Use binary search twice on sorted array [OK]

Common Mistakes:

• Using linear search on sorted array (slow)
• Sorting array again unnecessarily
• Not using binary search for efficiency