Coding Challenge — 2

This problem was recently asked by Airbnb

Given a sorted array, A, with possibly duplicated elements, find the indices of the first and last occurrences of a target element, x. Return -1 if the target is not found.

Example:

`Input: A = [1,3,3,5,7,8,9,9,9,15], target = 9`

Output: [6,8]

Input: A = [100, 150, 150, 153], target = 150

Output: [1,2]

Input: A = [1,2,3,4,5,6,10], target = 9

Output: [-1, -1]

Here is a function signature example:

**class** Solution**:**

**def** getRange**(**self**,** arr**,** target**):**

*# Fill this in.*

*# Test program *

arr **=** **[1,** **2,** **2,** **2,** **2,** **3,** **4,** **7,** **8,** **8]**

x **=** **2**

**print(**Solution**().**getRange**(**arr**,** x**))**

*# [1, 4]*

Solution:

Time complexity O(n)

class Solution:

def getRange(self, arr, target):

res = [0] * 2

find_first = 0

for i in range(len(arr)):

if arr[i] == x and find_first == 0:

find_first = 1

res[0] = i

if arr[i] == x:

res[1] = ireturn res