Search for a range Leetcode – Find first and last position of element in sorted array

Find first and last position of element in sorted array

In this article, we will look into an interesting problem asked in Coding Interviews related to Searching Algorithms. The problem is: Given a Sorted Array, we need to find the first and last position of an element in Sorted array. This problem is also known as Search for a range on Leetcode. We will look at different approaches to solve the problem along with their implementation and analyze the complexities of our approach.

Basically, we need to determine the first and last occurrence of a duplicate key element in the Array. Consider this array for example:

Sorted Array with Duplicate Elements.

Here, we can see an array of size 10 with duplicate elements 5 and 7. If we want to know the first and last occurrence of element 5, it will be at index 3 and 4 respectively. Similarly, for element 7, the first and last occurrence is at position/index 5 and 7 respectively.

Now let us look at our approaches to solve this problem.

Approach 1 (Using Linear Search)

In this method, we will follow these steps:

  • At first, we will traverse the array from the beginning or start index of the array. As soon as we get the target element, we store its index. This will indicate the first occurrence position of the target element. Then, we break out of the loop and stop traversing.
  • Now, to get the last index, we will start traversing from the end index of the array and as soon as we get the target element, we store its index. This will indicate the last occurrence of the element. Then, we simply print those indices.

Let us look at the code for this method:

Output:

Time Complexity: Here we perform a Linear Search to get the indexes if the the first occurrence is at second last element then we have to traverse the whole array. So, the overall runtime is O(n).

Approach 2 (Using Modified Binary Search-Optimal)

The idea or purpose of this approach is to minimize the runtime of the above method by using and modifying the Binary Search Algorithm. The breakdown of this approach is shown below:

  • Basically, We implement two functions:
    1. findStartingIndex(Array,target) -> To get the Starting Index or First Occurrence of Target element.
    2. findEndingIndex(Array,target) -> To get the Ending Index or Last Occurrence of Target element.
  • Now, for findStartingIndex() method, we will search the target by performing a modified binary search. We calculate mid = (low + high) / 2 (low =0 and high = Array_Size – 1). As the array is sorted, for each value of mid we need to perform operations based on three conditions.
    1. If(Arr[mid] >= target) -> This means if the element at index mid is greater than target element, then to get closer to target we need to update high = mid - 1 and search in the left half of the array. If the element is equal to target then also we need to update high, this will ensure we get as close as possible to the First Occurrence of the target.
    2. If the first condition does not hold true, it means the element is smaller than target, so we update low = mid + 1 and expand our search to the right half of the array.
    3. If(Arr[mid] == target) -> If we get the element at index mid equal to target, we store its index as a possible solution and continue our search until low<=high.
  • Similarly for findEndingIndex() method, we search the target by making some changes. The algorithm remains the same as the method discussed above only the conditions need to be changed.
    1. If(Arr[mid] <= target) -> If the element at index mid is smaller than target, then to get closer to target we update low = mid + 1, instead of high and continue searching in the right half of array. If the element is equal then also we update low and get close to the Last occurrence of the target.
    2. If the first condition is not true, we update high = mid -1 and search in the left half of array as element at mid is greater than the target.
    3. If(Arr[mid] == target) -> If the element is equal, we store its index and continue these steps until low<=high.

Let us look at the implementation of above approach:

Output:

Time complexity: We used Binary Search to get the first and last occurrence of the target element. We know binary search has runtime O(log n). Henceforth, the calls for findStartingIndex() and findEndingIndex() methods take O(log n) time each. So, the overall complexity is O(log n + log n) = O(log n). This is an optimal approach for this problem.

That’s all about Search for a range Leetcode – Find First and Last Position of Element in Sorted Array.


import_contacts

You may also like:

Related Posts

  • 28 March

    Sort an array of 0s, 1s and 2s

    Table of ContentsProblemSolution If you want to practice data structure and algorithm programs, you can go through Java coding interview questions. In this post, we will see how to sort an array of 0s, 1s and 2s.We have already seen a post on sort 0s and 1s in an array. Problem Given an array containing zeroes, […]

  • 04 March

    Check if it is possible to reach end of given Array by Jumping

    Table of ContentsProblemSolution If you want to practice data structure and algorithm programs, you can go through Java coding interview questions.   Problem Given an array with positive integers as elements indicating the maximum length of a jump which can be made from any position in the array. Check if it is possible to have […]

  • 17 February

    Check if Array Elements are Consecutive

    Table of ContentsProblemSolutionProgram to check if Array Elements are Consecutive If you want to practice data structure and algorithm programs, you can go through 100+ data structure and algorithm programs. In this post, we will see how to check if array elements are consecutive. Problem Given an array, we need to check if array contains […]

  • 01 November

    Find the local minima in array

    Table of ContentsProblemSolutionNaive approachEfficient approach If you want to practice data structure and algorithm programs, you can go through Java coding interview questions. In this post, we will see how to find the local minima in the array. Problem An element is local minima if it is less than its neighbors. int [] arr = {10, […]

  • 22 October

    Sliding Window Maximum in java

    Table of ContentsProblemSolution If you want to practice data structure and algorithm programs, you can go through Java coding interview questions. In this post, we will see about Sliding Window Maximum in java Problem Given an Array of integers and an Integer k, Find the maximum element of from all the contiguous subarrays of size K. […]

  • 20 October

    Count number of occurrences (or frequency) of each element in a sorted array

    Table of ContentsProblemSolution If you want to practice data structure and algorithm programs, you can go through Java coding interview questions. In this post, we will see how to count number of occurrences (or frequency) of each element in a sorted array Problem Given a Sorted Array of integers containing duplicates. Find the frequency of every […]

Leave a Reply

Your email address will not be published. Required fields are marked *

Subscribe to our newletter

Get quality tutorials to your inbox. Subscribe now.