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

Concept Flow - First and Last Occurrence of Element

Start at index 0

↓

Check if element at index == target?

No→Move to next index

↓

Reached end of array?

No→Repeat check

↓

Record index as first occurrence if none yet

↓

Continue to find last occurrence

↓

Reached end of array?

Yes→Return first and last occurrence indices

Start from the beginning of the array, check each element. Record the first time the target appears, keep updating the last occurrence until the end.

Execution Sample

DSA C#

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

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

Execution Table

Step	Operation	Index i	Element at i	First Occurrence	Last Occurrence	Visual State
1	Start loop	0	2	-1	-1	[2, 3, 2, 4, 2]
2	Check arr[0] == 2?	0	2	-1	-1	[2, 3, 2, 4, 2]
3	Match found, set first=0, last=0	0	2	0	0	[2, 3, 2, 4, 2]
4	Next iteration	1	3	0	0	[2, 3, 2, 4, 2]
5	Check arr[1] == 2?	1	3	0	0	[2, 3, 2, 4, 2]
6	No match, continue	1	3	0	0	[2, 3, 2, 4, 2]
7	Next iteration	2	2	0	0	[2, 3, 2, 4, 2]
8	Check arr[2] == 2?	2	2	0	0	[2, 3, 2, 4, 2]
9	Match found, first=0 (unchanged), last=2	2	2	0	2	[2, 3, 2, 4, 2]
10	Next iteration	3	4	0	2	[2, 3, 2, 4, 2]
11	Check arr[3] == 2?	3	4	0	2	[2, 3, 2, 4, 2]
12	No match, continue	3	4	0	2	[2, 3, 2, 4, 2]
13	Next iteration	4	2	0	2	[2, 3, 2, 4, 2]
14	Check arr[4] == 2?	4	2	0	2	[2, 3, 2, 4, 2]
15	Match found, first=0 (unchanged), last=4	4	2	0	4	[2, 3, 2, 4, 2]
16	End loop, return first=0, last=4	-	-	0	4	[2, 3, 2, 4, 2]

💡 Loop ends after index 4, all elements checked.

Variable Tracker

Variable	Start	After Step 3	After Step 9	After Step 15	Final
first	-1	0	0	0	0
last	-1	0	2	4	4
i	-	0	2	4	-

Key Moments - 3 Insights

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

Because we want to record the very first time the target appears. After that, we don't change 'first' anymore. See step 3 and 9 in execution_table where 'first' stays 0.

Why do we keep updating 'last' every time we find the target?

Because 'last' should always point to the most recent occurrence of the target. Look at steps 3, 9, and 15 where 'last' changes to 0, then 2, then 4.

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

Then 'first' and 'last' remain -1, meaning no occurrence found. This is implied by the initial values and no updates in the loop.

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of 'last' at step 9?

A 2

B -1

C 0

D 4

💡 Hint

Check the 'Last Occurrence' column at step 9 in the execution_table.

At which step does the first occurrence get set?

A Step 2

B Step 9

C Step 3

D Step 15

💡 Hint

Look for when 'first' changes from -1 to 0 in the execution_table.

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

A Both 0

B Both -1

C first = -1, last = 0

D first = 0, last = -1

💡 Hint

Refer to the initial values and note no updates if no match found.

Concept Snapshot

First and Last Occurrence:
- Initialize first and last to -1
- Loop through array from start to end
- If element == target:
  - If first == -1, set first = current index
  - Always update last = current index
- After loop, 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, start with two variables first and last set to -1. Loop through each element by index. When you find the target element, if first is still -1, set it to the current index. Always update last to the current index when you find the target. Continue until the end of the array. If the target is not found, first and last remain -1. This method ensures you get the earliest and latest positions of the target in one pass.

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 elements 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: Differentiate from other array queries

   It is not about sums, max/min, or counting unique elements, but about positions of a target element.

3. Final Answer:

   The first and last positions where a given element appears -> Option D

4. Quick Check:

   Positions of element = first and last occurrence [OK]

Hint: Look for positions of target element, not values or counts [OK]

Common Mistakes:

• Confusing with finding max or min element
• Trying to sum elements instead of finding positions
• Counting unique elements instead of occurrences

2. Which of the following C# code snippets correctly initializes an array to find the first and last occurrence of an element?

easy

A. int arr = {1, 2, 3, 4, 5};

B. int arr = new int[5] {1, 2, 3, 4, 5};

C. int[] arr = new int[] {1, 2, 3, 4, 5};

D. int arr[] = new int[] {1, 2, 3, 4, 5};

Solution

1. Step 1: Check array initialization syntax in C#

   Correct syntax is: int[] arr = new int[] {1, 2, 3, 4, 5};

2. Step 2: Identify incorrect options

   int arr = new int[5] {1, 2, 3, 4, 5}; has wrong syntax (cannot assign array with size and initializer like that), A is missing 'new int[]', D uses C-style syntax invalid in C#.

3. Final Answer:

   int[] arr = new int[] {1, 2, 3, 4, 5}; -> Option C

4. Quick Check:

   Correct C# array syntax = int[] arr = new int[] {1, 2, 3, 4, 5}; [OK]

Hint: Use 'int[] arr = new int[] { ... }' for array initialization [OK]

Common Mistakes:

• Using C/C++ style array declarations
• Omitting 'new int[]' keyword
• Assigning array size with initializer incorrectly

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

int[] arr = {5, 3, 7, 3, 9};
int target = 3;
int first = -1, last = -1;
for (int i = 0; i < arr.Length; i++) {
  if (arr[i] == target) {
    if (first == -1) first = i;
    last = i;
  }
}
Console.WriteLine($"{first} {last}");

medium

A. 3 1

B. 1 3

C. 0 4

D. -1 -1

Solution

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

   Array: [5, 3, 7, 3, 9]. Target = 3. Indices: 0 to 4.
   i=0: arr[0]=5 !=3 skip
   i=1: arr[1]=3 == target, first=-1 so first=1, last=1
   i=2: arr[2]=7 !=3 skip
   i=3: arr[3]=3 == target, first=1 (unchanged), last=3
   i=4: arr[4]=9 !=3 skip

2. Step 2: Print first and last

   first=1, last=3

3. Final Answer:

   1 3 -> Option B

4. Quick Check:

   First and last index of 3 = 1 and 3 [OK]

Hint: Track first when found, update last every time [OK]

Common Mistakes:

• Swapping first and last indices
• Not updating last occurrence correctly
• Initializing first and last with wrong values

4. Identify the error in the following code that tries to find the first and last occurrence of an element:

int[] arr = {2, 4, 2, 5, 2};
int target = 2;
int first = 0, last = 0;
for (int i = 0; i < arr.Length; i++) {
  if (arr[i] == target) {
    first = i;
    last = i;
  }
}
Console.WriteLine($"{first} {last}");

medium

A. first and last are initialized incorrectly, causing wrong output

B. Loop condition should be i <= arr.Length

C. Target value is not assigned properly

D. Console.WriteLine syntax is incorrect

Solution

1. Step 1: Analyze initialization of first and last

   Both first and last start at 0. Inside loop, first and last are set to i every time target is found, so first will be overwritten and end up as last occurrence index.

2. Step 2: Identify correct approach

   First should be set only once when first occurrence is found (e.g., if first == -1). Last should update every time target is found.

3. Final Answer:

   first and last are initialized incorrectly, causing wrong output -> Option A

4. Quick Check:

   Initialize first to -1 and update only once [OK]

Hint: Initialize first to -1 and update only once [OK]

Common Mistakes:

• Overwriting first occurrence index
• Using wrong loop boundary
• Incorrect Console.WriteLine format

5. Given a sorted array with possible duplicates, how can you efficiently find the first and last occurrence of a target element using C#?

hard

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

B. Traverse the array twice: once from start, once from end

C. Use a dictionary to store element counts

D. Sort the array again and find the target

Solution

1. Step 1: Understand the array is sorted with duplicates

   Sorted array allows binary search to find positions efficiently.

2. Step 2: Use binary search twice

   One binary search finds the first occurrence by moving left when target found, another finds last occurrence by moving right.

3. Step 3: Avoid full traversal or extra sorting

   Traversing twice or sorting again is inefficient. Dictionary counts do not give positions.

4. Final Answer:

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

5. Quick Check:

   Binary search twice = efficient first and last occurrence [OK]

Hint: Binary search twice for first and last occurrence in sorted array [OK]

Common Mistakes:

• Using linear search on large sorted arrays
• Sorting array again unnecessarily
• Using dictionary counts instead of positions