First and Last Occurrence of a Target

You are given an array of n integers that may contain duplicate values, along with a target value x. Using a single left-to-right linear scan, determine the first index and the last index at which x occurs in the array. If x does not occur anywhere in the array, report -1 for both positions. Indices are 0-based.

Input: The first line contains the integer n. The second line contains n space-separated integers, the array. The third line contains the integer target x. Output: Print two space-separated integers: the first index and the last index of x, or "-1 -1" if x is not present.

1 <= n <= 10^5 -10^9 <= a[i] <= 10^9 -10^9 <= x <= 10^9

Initializing both answers to -1 upfront is what makes the 'not found' case handle itself automatically - if the target never appears, both values simply stay at their initial -1, with no extra conditional logic needed.

Find the first and last positions of a target value in an array using a single linear pass. Brute force: Scan the array twice - once from the front to find the first occurrence, once from the back to find the last - this works but costs two passes when a single combined pass suffices. Optimised: Since the FIRST occurrence only needs to be recorded ONCE (the first time it's still unset) while the LAST occurrence needs continuous updating on EVERY match, both can be tracked simultaneously in a SINGLE left-to-right pass, with no need for a second scan or for binary search (which the sortedness-dependent version would use instead).

1. Initialize both the first-index and last-index answers to -1, so the 'not found' case falls out naturally without a separate check. 2. Walk the array once, left to right. 3. Update the FIRST-index variable ONLY when it's still unset (-1); update the LAST-index variable EVERY TIME you see a match.

Time: O(n) - a single linear pass through the array. Space: O(1) - just two index variables.

The target may not appear at all (print -1 -1), may appear exactly once (first equals last), or every element may equal the target.

Be ready to contrast this with the SORTED-array version of this same question (solved with two binary searches in O(log n)) - this version explicitly works on an UNSORTED array, requiring the full O(n) linear scan instead.