First and Last Occurrence of Element in DSA Java

Mental Model

Find where a number first appears and last appears in a list by checking each item from start to end.

Analogy: Imagine looking for a friend's name in a guest list. You note the first time you see their name and the last time it appears before the list ends.

Array: [1] -> [2] -> [3] -> [2] -> [4] -> [2] -> [5]
Indexes:  0      1      2      3      4      5      6

Dry Run Walkthrough

Input: list: [1, 2, 3, 2, 4, 2, 5], find first and last occurrence of 2

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

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

[1] -> [2] -> [3] -> [2] -> [4] -> [2] -> [5]
Indexes:  0      1      2      3      4      5      6
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

[1] -> [2] -> [3] -> [2] -> [4] -> [2] -> [5]
Indexes:  0      1      2      3      4      5      6
first = 1, last = 1

Why: Found first occurrence, update both first and last to 1

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

[1] -> [2] -> [3] -> [2] -> [4] -> [2] -> [5]
Indexes:  0      1      2      3      4      5      6
first = 1, last = 1

Why: No change, continue searching

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

[1] -> [2] -> [3] -> [2] -> [4] -> [2] -> [5]
Indexes:  0      1      2      3      4      5      6
first = 1, last = 3

Why: Update last occurrence to 3

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

[1] -> [2] -> [3] -> [2] -> [4] -> [2] -> [5]
Indexes:  0      1      2      3      4      5      6
first = 1, last = 3

Why: No change, continue searching

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

[1] -> [2] -> [3] -> [2] -> [4] -> [2] -> [5]
Indexes:  0      1      2      3      4      5      6
first = 1, last = 5

Why: Update last occurrence to 5

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

[1] -> [2] -> [3] -> [2] -> [4] -> [2] -> [5]
Indexes:  0      1      2      3      4      5      6
first = 1, last = 5

Why: No change, finished scanning

Result:

Final: first occurrence at index 1, last occurrence at index 5

Annotated Code

DSA Java

public class FirstLastOccurrence {
    public static int[] findFirstLast(int[] arr, int target) {
        int first = -1;
        int last = -1;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == target) {
                if (first == -1) {
                    first = i; // record first occurrence
                }
                last = i; // update last occurrence
            }
        }
        return new int[]{first, last};
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 2, 4, 2, 5};
        int target = 2;
        int[] result = findFirstLast(arr, target);
        System.out.println("First occurrence: " + result[0]);
        System.out.println("Last occurrence: " + result[1]);
    }
}

if (arr[i] == target) {

Check if current element matches target

if (first == -1) {

If first occurrence not found yet, record current index

first = i; // record first occurrence

Set first occurrence index

last = i; // update last occurrence

Update last occurrence index to current

Output

First occurrence: 1

Last occurrence: 5

Complexity Analysis

Time: O(n) because we scan the entire list once to find all 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 -1 for both first and last since target not found

DSA Java

if (first == -1) {

Target not in array

Returns -1 for both first and last indicating no occurrence

DSA Java

if (first == -1) {

Target appears only once

First and last occurrence are the same index

DSA Java

last = i; // update last occurrence

When to Use This Pattern

When asked to find where an element appears first and last in a list, use a single pass scan updating first and last indexes to solve efficiently.

Common Mistakes

Mistake: Stopping search after finding first occurrence and not updating last occurrence
Fix: Continue scanning entire list to update last occurrence index

Mistake: Initializing first and last to 0 instead of -1, causing confusion if target is at index 0
Fix: Initialize first and last to -1 to indicate not found yet

Summary

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

Use when you need to know the range of positions where an element appears.

Keep track of first occurrence once and update last occurrence every time you find the target.

Practice

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

easy

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

B. The total count of the element in the array

C. The last index where the element appears

D. The sum of all elements before the element

Solution

1. Step 1: Understand the meaning of first occurrence

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

2. Step 2: Compare with other options

   Counting or last index are different concepts; sum is unrelated.

3. Final Answer:

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

4. Quick Check:

   First occurrence = first index found [OK]

Hint: First occurrence means earliest index found [OK]

Common Mistakes:

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

2. Which of the following Java code snippets correctly finds the first occurrence of target in array arr?

easy

A. for(int i=0; i

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

C. int index = arr.indexOf(target); return index;

D. while(arr.contains(target)) { return arr.indexOf(target); }

Solution

1. Step 1: Check loop direction and condition

   for(int i=0; i

2. Step 2: Analyze other options

   for(int i=arr.length-1; i>=0; i--) { if(arr[i] == target) return i; } return -1; loops backward, so finds last occurrence. int index = arr.indexOf(target); return index; uses invalid method for arrays. while(arr.contains(target)) { return arr.indexOf(target); } has incorrect syntax and logic.

3. Final Answer:

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

4. Quick Check:

   Loop start to end returns first match [OK]

Hint: Loop from start to find first occurrence [OK]

Common Mistakes:

• Looping backward to find first occurrence
• Using methods not available for arrays
• Incorrect loop conditions

3. What is the output of the following Java code?

int[] arr = {5, 3, 7, 3, 9};
int target = 3;
int first = -1, last = -1;
for(int i=0; i

medium

A. First: 0, Last: 4

B. First: 1, Last: 3

C. First: 3, Last: 1

D. First: -1, Last: -1

Solution

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

   At i=1, arr[1]=3 matches target, first=-1 so first=1, last=1. At i=3, arr[3]=3 matches, last=3 updated.

2. Step 2: Confirm final values

   First occurrence is index 1, last occurrence is index 3.

3. Final Answer:

   First: 1, Last: 3 -> Option B

4. Quick Check:

   First=1, Last=3 from loop [OK]

Hint: Update last on every match, first only once [OK]

Common Mistakes:

• Swapping first and last values
• Not updating last occurrence correctly
• Initializing first incorrectly

4. Identify the error in this code snippet that tries to find the last occurrence of target in arr:

int last = -1;
for(int i=0; i

medium

A. Missing return type in method

B. Variable last is not initialized

C. Loop should run backwards from end to start

D. Break statement stops loop too early, finds first not last occurrence

Solution

1. Step 1: Analyze loop and break usage

   The break inside if stops loop at first match, so last is actually first occurrence, not last.

2. Step 2: Understand correct approach

   To find last occurrence, loop should continue through entire array without break, updating last each time.

3. Final Answer:

   Break statement stops loop too early, finds first not last occurrence -> Option D

4. Quick Check:

   Break stops loop early, wrong for last occurrence [OK]

Hint: Don't break loop when searching last occurrence [OK]

Common Mistakes:

• Using break inside loop for last occurrence
• Looping forward but breaking early
• Confusing first and last occurrence logic

5. Given a sorted array arr with possible duplicates, which approach efficiently finds the first and last occurrence of target in O(log n) time?

hard

A. Use a HashMap to store indices of all elements

B. Traverse array from start to end and record first and last indices

C. Use binary search twice: once for first occurrence, once for last occurrence

D. Sort the array again and then find occurrences

Solution

1. Step 1: Understand array is sorted

   Sorted array allows binary search to find elements quickly in O(log n) time.

2. Step 2: Apply binary search twice

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

3. Step 3: Compare with other options

   Linear traversal is O(n), HashMap adds overhead, sorting again is unnecessary.

4. Final Answer:

   Use binary search twice: once for first occurrence, once for last occurrence -> Option C

5. Quick Check:

   Binary search twice = O(log n) efficient [OK]

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

Common Mistakes:

• Using linear search on sorted array
• Trying to sort array again unnecessarily
• Using extra data structures without need