First and Last Occurrence of Element in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Find first and last occurrence indexes in a sorted array

What is the output of the following Go code that finds the first and last occurrence of the number 3 in a sorted array?

DSA Go

package main
import "fmt"

func firstAndLast(arr []int, target int) (int, int) {
    first, last := -1, -1
    for i, v := range arr {
        if v == target {
            if first == -1 {
                first = i
            }
            last = i
        }
    }
    return first, last
}

func main() {
    arr := []int{1, 2, 3, 3, 3, 4, 5}
    f, l := firstAndLast(arr, 3)
    fmt.Printf("%d %d\n", f, l)
}

A 2 4

B 1 3

C 3 5

D -1 -1

💡 Hint

Look for the first and last index where the target appears in the array.

The function scans the array and updates first when it finds the target for the first time, and keeps updating last as it finds more occurrences. For target 3, first is at index 2 and last at index 4.

❓ Predict Output

intermediate

Output of binary search for first occurrence

What is the output of this Go code that uses binary search to find the first occurrence of 5 in a sorted array?

DSA Go

package main
import "fmt"

func firstOccurrence(arr []int, target int) int {
    low, high := 0, len(arr)-1
    result := -1
    for low <= high {
        mid := (low + high) / 2
        if arr[mid] == target {
            result = mid
            high = mid - 1
        } else if arr[mid] < target {
            low = mid + 1
        } else {
            high = mid - 1
        }
    }
    return result
}

func main() {
    arr := []int{1, 3, 5, 5, 5, 7, 9}
    fmt.Println(firstOccurrence(arr, 5))
}

A 3

B 4

C 2

D -1

💡 Hint

Binary search moves left when it finds the target to find the first occurrence.

The first occurrence of 5 is at index 2. The binary search updates result and moves left to find if there is an earlier occurrence.

🔧 Debug

advanced

Identify the error in last occurrence binary search

What error does the following Go code produce when trying to find the last occurrence of 4 in the array?

DSA Go

package main
import "fmt"

func lastOccurrence(arr []int, target int) int {
    low, high := 0, len(arr)-1
    result := -1
    for low <= high {
        mid := (low + high) / 2
        if arr[mid] == target {
            result = mid
            low = mid + 1
        } else if arr[mid] > target {
            high = mid - 1
        } else {
            low = mid + 1
        }
    }
    return result
}

func main() {
    arr := []int{1, 2, 4, 4, 4, 5, 6}
    fmt.Println(lastOccurrence(arr, 4))
}

A No error, output is 4

B Index out of range runtime error

C Compilation error

D Infinite loop

💡 Hint

Check the loop conditions and index updates carefully.

The code correctly updates low and high pointers and returns the last occurrence index 4 without errors.

❓ Predict Output

advanced

Output of combined first and last occurrence function

What is the output of this Go program that finds first and last occurrence of 7 in a sorted array?

DSA Go

package main
import "fmt"

func firstAndLastOccurrence(arr []int, target int) (int, int) {
    first, last := -1, -1
    low, high := 0, len(arr)-1
    // Find first occurrence
    for low <= high {
        mid := (low + high) / 2
        if arr[mid] == target {
            first = mid
            high = mid - 1
        } else if arr[mid] < target {
            low = mid + 1
        } else {
            high = mid - 1
        }
    }
    low, high = 0, len(arr)-1
    // Find last occurrence
    for low <= high {
        mid := (low + high) / 2
        if arr[mid] == target {
            last = mid
            low = mid + 1
        } else if arr[mid] > target {
            high = mid - 1
        } else {
            low = mid + 1
        }
    }
    return first, last
}

func main() {
    arr := []int{1, 3, 5, 7, 7, 7, 9, 11}
    f, l := firstAndLastOccurrence(arr, 7)
    fmt.Printf("%d %d\n", f, l)
}

A 4 6

B 2 4

C -1 -1

D 3 5

💡 Hint

Binary search finds first and last indexes separately.

The first 7 is at index 3 and last 7 is at index 5 in the array.

🧠 Conceptual

expert

Time complexity of first and last occurrence search

What is the time complexity of finding the first and last occurrence of an element in a sorted array using binary search?

A O(n)

B O(log n)

C O(n log n)

D O(1)

💡 Hint

Binary search divides the search space in half each step.

Each binary search (for first and last occurrence) takes O(log n), so combined still O(log n).

Practice

1. What does the "First and Last Occurrence of Element" problem ask you to find in an array?

easy

A. The sum of all elements in the array

B. The first and last positions where a given element appears

C. The maximum and minimum values in the array

D. The number of unique elements in the array

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: Identify what is required

   We need to return the indices of the first and last occurrence of the element, not sums or counts.

3. Final Answer:

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

4. Quick Check:

   First and last occurrence = positions [OK]

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

Common Mistakes:

• Confusing occurrence with sum or count
• Looking for max/min instead of positions
• Ignoring the last occurrence

2. Which of the following Go code snippets correctly declares a function to find the first occurrence of an element in a slice?

easy

A. func firstOccurrence(arr []int, x int) int { for _, v := range arr { if v == x { return i } } return -1 }

B. func firstOccurrence(arr []int, x int) int { for i := range arr { if arr[i] = x { return i } } return -1 }

C. func firstOccurrence(arr []int, x int) { for i := 0; i < len(arr); i++ { if arr[i] == x { return i } } return -1 }

D. func firstOccurrence(arr []int, x int) int { for i := 0; i < len(arr); i++ { if arr[i] == x { return i } } return -1 }

Solution

1. Step 1: Check function signature and return type

   The function must return an int index, so signature must be func firstOccurrence(arr []int, x int) int.

2. Step 2: Verify loop and condition syntax

   func firstOccurrence(arr []int, x int) int { for i := 0; i < len(arr); i++ { if arr[i] == x { return i } } return -1 } uses a for loop with index and correct equality check (arr[i] == x) and returns index or -1.

3. Final Answer:

   func firstOccurrence(arr []int, x int) int { for i := 0; i < len(arr); i++ { if arr[i] == x { return i } } return -1 } -> Option D

4. Quick Check:

   Correct syntax and return type = func firstOccurrence(arr []int, x int) int { for i := 0; i < len(arr); i++ { if arr[i] == x { return i } } return -1 } [OK]

Hint: Check function return type and equality operator carefully [OK]

Common Mistakes:

• Missing return type in function signature
• Using assignment '=' instead of equality '=='
• Returning inside a void function

3. What will be the output of the following Go code snippet?

arr := []int{2, 4, 4, 4, 6, 7}
first := -1
last := -1
x := 4
for i, v := range arr {
  if v == x {
    if first == -1 {
      first = i
    }
    last = i
  }
}
fmt.Println(first, last)

medium

A. 1 3

B. 2 4

C. 1 4

D. 0 3

Solution

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

   Indices with value 4 are 1, 2, 3. First occurrence is 1, last occurrence is 3.

2. Step 2: Confirm printed values

   Variables first and last hold 1 and 3 respectively, so output is "1 3".

3. Final Answer:

   1 3 -> Option A

4. Quick Check:

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

Hint: Track indices where element matches, update first once, last every time [OK]

Common Mistakes:

• Confusing index positions starting at 0
• Updating first occurrence multiple times
• Not updating last occurrence correctly

4. Identify the bug in this Go function that finds the last occurrence of an element in a slice:

func lastOccurrence(arr []int, x int) int {
  last := -1
  for i := 0; i <= len(arr); i++ {
    if arr[i] == x {
      last = i
    }
  }
  return last
}

medium

A. Loop condition should be i < len(arr), not i <= len(arr) to avoid out-of-range error

B. Variable 'last' should be initialized to 0 instead of -1

C. The function should return first occurrence, not last

D. The if condition should use '!=' instead of '=='

Solution

1. Step 1: Check loop boundary conditions

   The loop uses i <= len(arr), which causes index out-of-range error because valid indices are 0 to len(arr)-1.

2. Step 2: Correct loop condition

   Change to i < len(arr) to safely access elements without error.

3. Final Answer:

   Loop condition should be i < len(arr), not i <= len(arr) to avoid out-of-range error -> Option A

4. Quick Check:

   Loop index must be less than length [OK]

Hint: Use i < len(arr) for loops to avoid index errors [OK]

Common Mistakes:

• Using <= instead of < in loop condition
• Initializing last to 0 causing wrong default
• Confusing last occurrence with first

5. Given a sorted slice of integers, which approach is the most efficient to find the first and last occurrence of a target element x?

hard

A. Sort the slice again and then find occurrences linearly

B. Scan the slice from start to end once, record first and last occurrence

C. Use two binary searches: one to find first occurrence, one for last occurrence

D. Use a hash map to store all indices of elements and look up x

Solution

1. Step 1: Understand the input is sorted

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

2. Step 2: Use two binary searches

   One binary search finds the first occurrence, another finds the last occurrence of x in O(log n) time.

3. Step 3: Compare with other options

   Linear scan is O(n), sorting again is unnecessary and costly, hash map adds extra space and complexity.

4. Final Answer:

   Use two binary searches: one to find first occurrence, one for last occurrence -> Option C

5. Quick Check:

   Sorted array + binary search = efficient [OK]

Hint: Use binary search twice on sorted data for first and last positions [OK]

Common Mistakes:

• Using linear scan on sorted data ignoring binary search
• Sorting already sorted data again
• Using extra space unnecessarily