Last occurrence element in array

Tags: , , , ,

Finding the last occurrence of an element in a list of numbers is very similar to the First occurrence of an element with binary search. Given a sorted array and an element, find the last occurrence of a given element.  As the array can contain duplicate values, there can be multiple occurrences of the same element, the problem is to find the last index. For example, in the given array, the last occurrence of 4 is at index 4. Can you guess what is the last occurrence of element 6?

last occurrence of element

The brute force solution would be to scan the entire array and compare each A[i] with the given key element. If A[i] is equal to key and the next element is not equal to the key then return the index i. The worst-case time complexity of brute force method is O(N). Can we do better than?

Last occurrence of element: thought process

One property of input array we did not use in brute force solution is the array being sorted. The de facto for searching in a sorted array is, of course, binary search algorithm. If there are no duplicates in the array it will be super easy to find the last occurrence using binary search, how can we modify it to solve a problem with duplicates.
The first question you should ask yourself is: What is the candidate solution set? In simple terms, what can be a valid answer if the key is a part of the input array? Also, think about the case when a key is not present at all.

If the key is present, the candidate answer will be one of the indices. Range of indices is from 0 to array.length -1. We learned a concept when solving to find a greater or equal number or ceiling in a sorted array. The concept was: we can apply binary search to any set of inputs where the following condition is met :

Binary search can be used if and only if for all x in candidate Set Spredicate(x) implies predicate(y) for all y > x or for all y < x

If A[i] is less than or equal to the key, then all the A[y] will be less than or equal to A[i] where y < i, which satisfies our condition to apply binary search.
This means that when predicate returns true, which is: element equal or less than the key, there is no point looking into left subarray, as all elements will be less than or equal to key. The last occurrence of the key can not be less than the current index. Hence, discard Array[start, i-1] and look in the right side of array, Array[i, end].
What should the start point be for index u? Obviously, it will be the middle index in the left part of the array. Based on if predicate(mid) is true or false, we discard left or right half of array.

When to stop? When only one element is left in the array, at that point check if that element is key, if yes return index else return -1.

Last occurrence of element in a sorted array: Example

Let’s take an example and see how it works? Take an array as shown below and find the last occurrence of element 2.

 

Start with mid-index and see if it is less than or equal to key, it is, so discards the left subarray excluding mid.

 

The new array to be searched is from index 3 to 7. Find new mid, the element at new mid is less than or equal to key, in that case, discard left subarray.

Search space is reduced from index 5 to 7. Mid is 6 and Array[6] is greater than the key, so again discard right subarray.

At this point, there is only one element left in the candidate set. Is it equal to the key? If yes, return the index.

last occurrence of element

Can you please draw the execution flow to find 1 and say 10 (which does not exist in the array)? Does the algorithm work for those cases?

Last occurrence of element in a sorted array: Implementation

package com.company;

/**
 * Created by sangar on 25.3.18.
 */
public class BinarySearcchAlgorithm {

    private static boolean isLessThanEqualTo(int[] a, int index, int key){
        if(a[index] <= key) return true;

        return false;
    }

    public static int findLastOccurrence (int[] a, int start, int end, int key){

        while(start < end){
            int mid = start + ((end - start) +1) / 2;

            if(isLessThanEqualTo(a, mid, key)){
                start = mid;
            }
            else{
                end= mid-1;
            }
        }
        return (end >=0 && a[end] == key) ? end : -1;
    }

    public static void main(String[] args) {
        int[] input = {3,10,11,15,17,17,17,20};

        int index = findLastInstance(input,0, input.length-1, 20);
        System.out.print(index == -1 ? "Element not found" : "Element found at : " + index);
    }
}

The same method can be implemented recursively as follow

public static int findLastOccurrence Recursive(int[] a, int start, int end, int key){

    if(start < end){
        int mid = start + ((end - start) +1) / 2;

        if(isLessThanEqualTo(a, mid, key)){
            return findLastOccurrenceRecursive(a,mid,end, key);
        }
        else{
            return findLastOccurrenceRecursive(a,start,mid-1, key);
        }
    }
    return (end >=0 && a[end] == key) ? end: -1;
}

Worst-case complexity to find the last occurrence of element in a sorted array using binary search algorithm is O(log n).

What did we learn from this problem? First, how to identify if a problem can be solved using a binary search. We learned how a solution depends on the candidate solution set. How can we discard some parts of that set based on constraints in the problem? For example, in this problem, candidate set was all indices of an array, but based on constraint that element should be equal to key, half of those indices were discarded.
Remember to check the last element for constraints of the problem, if matches, then it is a solution, else there is no solution.

I hope, this article helps you to prepare better for your interviews. If you find anything missing or wrong, please reach out to us through comments, email at communications@algorithmsandme.com