First and Last Position of an Element in a Sorted Array in JavaScript

Different approaches to solve the problem

Photo by The Lucky Neko on Unsplash

Approach 1: Using built-in methods in javascript

1. To find the first position of an element we can use the indexOf() method. (this works even when duplicates are present in an array)
2. To find the last position of an element we can use the lastIndexOf() method.

Time Complexity: O(n)

Space Complexity: O(1)

Approach 2:

1. Create two variables (first and last) and initialize them to -1
2. Loop over the array and when the target element is found then update the first and the last variable
3. Keep updating last element until the next element is different
4. Return first and last variables

Time Complexity: O(n)

Space Complexity: O(1)

Approach 3: Binary Search

1. The function accepts an array of n elements as an argument
2. Create an array to store the first and last index. Initialize this array to -1
3. Initialize two pointers i and j. Where i = 0 and j = n-1
4. Loop over the array with the following condition being true- i ≤ j
5. Find the mid index and then:

• If mid element of the array is less than the target- i = mid+1
• If mid element of the array is greater than the target- j = mid-1

6. If mid element is same as the target then do the following:

• Create two variables left (this will store the first index) and right (this will store the last index) and initialize them to mid (index)
• First Index: Loop over the left side of mid until the elements are same and left ≥ 0
• Last Index: Loop over the right side of mid until the elements are same and right < n
• Finally, value of first index will be left + 1, last index will be right - 1

7. Return the first and last index.

8. If the target element is not in the array then first = -1, last = -1

Time Complexity: O(log n)

Space Complexity: O(1)

Approach 4: Another Iterative Binary Search Approach

Time Complexity: O(log n)

Space Complexity: O(1)

Also Read,

Rotate the array to the right by k steps in JavaScript

Maximum And Minimum Elements Of An Array