Number of occurrences of element

Tags: , , , ,

Number of occurrences of element

Given a sorted array and a key, find the number of occurrences of a key in that array. For example, in the below array, the number of occurrences of 3 is 3.

number of occurrences of element

Brute force method will be to scan through the array, find the first instance of an element and then find the last instance, then do the math. The complexity of that method is O(N). Can we do better than that?

Did you get some hint when brute force method was described? Yes,we have already cracked the problem to find first occurrence and last occurrence in O(log n) complexity earlier. We will be using those two methods, all we need to do know is math.

occurrences = lastInstance - firstInstance + 1

Number of occurrences of element : Implementation.

package com.company;

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

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

        return false;
    }

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

        return false;
    }

    private int findFirstOccurance(int[] nums, int target){
        int start = 0;
        int end = nums.length-1;
        
        while(start<end){
            int mid =  start + (end-start)/2;
            
            if(if(isGreaterThanEqualTo(nums, mid, target)){){
                end = mid;
            }
            else{
                start = mid+1;
            }
        }
        return start < nums.length && nums[start] == target ? start : -1;
    }
    
    private int findLastOccurance(int[] nums, int target){
        int start = 0;
        int end = nums.length-1;
        
        while(start<=end){
            int mid =  start + (end-start)/2;
        
            if(isLessThanEqualTo(nums, mid, target)){
                start = mid+1;
            }
            else if(nums[mid] > target){
                end = mid-1;
            }
        }
        return end >= 0 && nums[end] == target ? end : -1;
    }

    public  static  int numberOfOccurrences(int[] a, int key){
        int firstInstance = findFirstOccurance(a, key);
        int lastInstance = findLastOccurance(a, key);

        return (firstInstance != -1) ? lastInstance-firstInstance + 1 : 0;
    }

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

        int index = numberOfOccurrences(input,3);
        System.out.print(index == -1 ? "Element not found" : "Element found at : " + index);

    }
}

The worst case time complexity of the algorithm to find the number of occurrences of an element in a sorted array is O(log n). We are using the iterative method to find the first and last instances, therefore, there is no hidden space complexity of the algorithm.

You can test the code at leetcode
Please share if there is something wrong or missing. Also if you want to contribute to algorithms and me, please drop an email at communications@algorithmsandme.com