First and Last Occurrence of Element in DSA C - Execution Trace

Concept Flow - First and Last Occurrence of Element

Start

↓

Initialize first = -1, last = -1

↓

Traverse array from i=0 to n-1

↓

Check if arr[i

↓

If first == -1, set first = i

↓

Set last = i

↓

Continue traversal

↓

End traversal

↓

Return first and last

↓

Done

We scan the array once, updating first and last positions when we find the target element.

Execution Sample

DSA C

int first = -1, last = -1;
for (int i = 0; i < n; i++) {
  if (arr[i] == target) {
    if (first == -1) first = i;
    last = i;
  }
}

This code finds the first and last positions of target in the array.

Execution Table

Step	Operation	Index i	arr[i]	Condition arr[i]==target	first	last	Visual State
1	Initialize	-	-	-	-1	-1	first=-1, last=-1
2	Check arr[0]	0	5	No	-1	-1	No change
3	Check arr[1]	1	3	No	-1	-1	No change
4	Check arr[2]	2	7	Yes	2	2	first=2, last=2
5	Check arr[3]	3	7	Yes	2	3	last updated to 3
6	Check arr[4]	4	2	No	2	3	No change
7	Check arr[5]	5	7	Yes	2	5	last updated to 5
8	End traversal	-	-	-	2	5	first=2, last=5

💡 Traversal ends after i reaches n-1; first and last hold first and last occurrence indices.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	Final
first	-1	-1	-1	2	2	2	2	2
last	-1	-1	-1	2	3	3	5	5

Key Moments - 3 Insights

Why do we check if first == -1 before setting it?

Because first should store the index of the first time we find the target. If we set it every time, it would always be the last occurrence. See execution_table rows 4 and 5.

What if the target is not in the array at all?

first and last remain -1, indicating the target was never found. This is shown in the initial state and no updates happen if condition is never true.

Why do we update last every time we find the target?

Because last should always point to the most recent occurrence of the target. This is shown in execution_table rows 4, 5, and 7 where last changes.

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of 'first' after step 5?

A 3

B 2

C -1

D 5

💡 Hint

Check the 'first' column in execution_table row 5.

At which step does the 'last' variable first get updated?

A Step 4

B Step 5

C Step 2

D Step 7

💡 Hint

Look at the 'last' column in execution_table rows 2 to 5.

If the target was not found in the array, what would be the final values of 'first' and 'last'?

A first=length-1, last=length-1

B first=0, last=0

C first=-1, last=-1

D first=last=undefined

💡 Hint

Refer to the initial values in variable_tracker and execution_table step 1.

Concept Snapshot

First and Last Occurrence of Element:
- Initialize first and last to -1
- Traverse array from start to end
- If element matches target:
  - If first == -1, set first = current index
  - Always update last = current index
- After traversal, first and last hold positions or -1 if not found

Full Transcript

To find the first and last occurrence of an element in an array, we start with two variables first and last set to -1. We scan the array from the beginning. Each time we find the target element, if first is still -1, we set it to the current index. We always update last to the current index when we find the target. After scanning the entire array, first and last will hold the indices of the first and last occurrence of the target element. If the target is not found, both remain -1.

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