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).